1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
91 #include "tree-pass.h"
94 #include "optabs-query.h"
95 #include "gimple-pretty-print.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
99 #include "gimple-fold.h"
100 #include "gimplify.h"
101 #include "gimple-iterator.h"
102 #include "gimplify-me.h"
103 #include "tree-cfg.h"
104 #include "tree-into-ssa.h"
105 #include "tree-ssa.h"
107 #include "tree-data-ref.h"
108 #include "tree-scalar-evolution.h"
109 #include "tree-ssa-loop-ivopts.h"
110 #include "tree-ssa-address.h"
112 #include "tree-hash-traits.h"
114 #include "builtins.h"
117 /* List of basic blocks in if-conversion-suitable order. */
118 static basic_block
*ifc_bbs
;
120 /* Apply more aggressive (extended) if-conversion if true. */
121 static bool aggressive_if_conv
;
123 /* Hash table to store references, DR pairs. */
124 static hash_map
<tree_operand_hash
, data_reference_p
> *ref_DR_map
;
126 /* Hash table to store base reference, DR pairs. */
127 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
129 /* Structure used to predicate basic blocks. This is attached to the
130 ->aux field of the BBs in the loop to be if-converted. */
131 struct bb_predicate
{
133 /* The condition under which this basic block is executed. */
136 /* PREDICATE is gimplified, and the sequence of statements is
137 recorded here, in order to avoid the duplication of computations
138 that occur in previous conditions. See PR44483. */
139 gimple_seq predicate_gimplified_stmts
;
142 /* Returns true when the basic block BB has a predicate. */
145 bb_has_predicate (basic_block bb
)
147 return bb
->aux
!= NULL
;
150 /* Returns the gimplified predicate for basic block BB. */
153 bb_predicate (basic_block bb
)
155 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
158 /* Sets the gimplified predicate COND for basic block BB. */
161 set_bb_predicate (basic_block bb
, tree cond
)
163 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
164 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
165 || is_gimple_condexpr (cond
));
166 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
169 /* Returns the sequence of statements of the gimplification of the
170 predicate for basic block BB. */
172 static inline gimple_seq
173 bb_predicate_gimplified_stmts (basic_block bb
)
175 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
178 /* Sets the sequence of statements STMTS of the gimplification of the
179 predicate for basic block BB. */
182 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
184 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
187 /* Adds the sequence of statements STMTS to the sequence of statements
188 of the predicate for basic block BB. */
191 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
194 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
197 /* Initializes to TRUE the predicate of basic block BB. */
200 init_bb_predicate (basic_block bb
)
202 bb
->aux
= XNEW (struct bb_predicate
);
203 set_bb_predicate_gimplified_stmts (bb
, NULL
);
204 set_bb_predicate (bb
, boolean_true_node
);
207 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
208 but don't actually free it. */
211 release_bb_predicate (basic_block bb
)
213 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
216 gimple_stmt_iterator i
;
218 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
219 free_stmt_operands (cfun
, gsi_stmt (i
));
220 set_bb_predicate_gimplified_stmts (bb
, NULL
);
224 /* Free the predicate of basic block BB. */
227 free_bb_predicate (basic_block bb
)
229 if (!bb_has_predicate (bb
))
232 release_bb_predicate (bb
);
237 /* Reinitialize predicate of BB with the true predicate. */
240 reset_bb_predicate (basic_block bb
)
242 if (!bb_has_predicate (bb
))
243 init_bb_predicate (bb
);
246 release_bb_predicate (bb
);
247 set_bb_predicate (bb
, boolean_true_node
);
251 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
252 the expression EXPR. Inserts the statement created for this
253 computation before GSI and leaves the iterator GSI at the same
257 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
259 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
260 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
261 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
265 /* Return true when COND is a false predicate. */
268 is_false_predicate (tree cond
)
270 return (cond
!= NULL_TREE
271 && (cond
== boolean_false_node
272 || integer_zerop (cond
)));
275 /* Return true when COND is a true predicate. */
278 is_true_predicate (tree cond
)
280 return (cond
== NULL_TREE
281 || cond
== boolean_true_node
282 || integer_onep (cond
));
285 /* Returns true when BB has a predicate that is not trivial: true or
289 is_predicated (basic_block bb
)
291 return !is_true_predicate (bb_predicate (bb
));
294 /* Parses the predicate COND and returns its comparison code and
295 operands OP0 and OP1. */
297 static enum tree_code
298 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
302 if (TREE_CODE (cond
) == SSA_NAME
303 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
305 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
307 *op0
= gimple_assign_rhs1 (s
);
308 *op1
= gimple_assign_rhs2 (s
);
309 return gimple_assign_rhs_code (s
);
312 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
314 tree op
= gimple_assign_rhs1 (s
);
315 tree type
= TREE_TYPE (op
);
316 enum tree_code code
= parse_predicate (op
, op0
, op1
);
318 return code
== ERROR_MARK
? ERROR_MARK
319 : invert_tree_comparison (code
, HONOR_NANS (type
));
325 if (COMPARISON_CLASS_P (cond
))
327 *op0
= TREE_OPERAND (cond
, 0);
328 *op1
= TREE_OPERAND (cond
, 1);
329 return TREE_CODE (cond
);
335 /* Returns the fold of predicate C1 OR C2 at location LOC. */
338 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
340 tree op1a
, op1b
, op2a
, op2b
;
341 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
342 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
344 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
346 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
352 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
355 /* Returns true if N is either a constant or a SSA_NAME. */
358 constant_or_ssa_name (tree n
)
360 switch (TREE_CODE (n
))
373 /* Returns either a COND_EXPR or the folded expression if the folded
374 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
375 a constant or a SSA_NAME. */
378 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
380 tree rhs1
, lhs1
, cond_expr
;
382 /* If COND is comparison r != 0 and r has boolean type, convert COND
383 to SSA_NAME to accept by vect bool pattern. */
384 if (TREE_CODE (cond
) == NE_EXPR
)
386 tree op0
= TREE_OPERAND (cond
, 0);
387 tree op1
= TREE_OPERAND (cond
, 1);
388 if (TREE_CODE (op0
) == SSA_NAME
389 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
390 && (integer_zerop (op1
)))
393 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
396 if (cond_expr
== NULL_TREE
)
397 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
399 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
401 if (constant_or_ssa_name (cond_expr
))
404 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
406 rhs1
= TREE_OPERAND (cond_expr
, 1);
407 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
408 if (constant_or_ssa_name (rhs1
))
409 return build1 (ABS_EXPR
, type
, rhs1
);
412 if (TREE_CODE (cond_expr
) == MIN_EXPR
413 || TREE_CODE (cond_expr
) == MAX_EXPR
)
415 lhs1
= TREE_OPERAND (cond_expr
, 0);
416 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
417 rhs1
= TREE_OPERAND (cond_expr
, 1);
418 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
419 if (constant_or_ssa_name (rhs1
)
420 && constant_or_ssa_name (lhs1
))
421 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
423 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
426 /* Add condition NC to the predicate list of basic block BB. LOOP is
427 the loop to be if-converted. Use predicate of cd-equivalent block
428 for join bb if it exists: we call basic blocks bb1 and bb2
429 cd-equivalent if they are executed under the same condition. */
432 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
437 if (is_true_predicate (nc
))
440 /* If dominance tells us this basic block is always executed,
441 don't record any predicates for it. */
442 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
445 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
446 /* We use notion of cd equivalence to get simpler predicate for
447 join block, e.g. if join block has 2 predecessors with predicates
448 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
449 p1 & p2 | p1 & !p2. */
450 if (dom_bb
!= loop
->header
451 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
453 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
454 bc
= bb_predicate (dom_bb
);
455 if (!is_true_predicate (bc
))
456 set_bb_predicate (bb
, bc
);
458 gcc_assert (is_true_predicate (bb_predicate (bb
)));
459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
460 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
461 dom_bb
->index
, bb
->index
);
465 if (!is_predicated (bb
))
469 bc
= bb_predicate (bb
);
470 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
471 if (is_true_predicate (bc
))
473 reset_bb_predicate (bb
);
478 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
479 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
480 tp
= &TREE_OPERAND (bc
, 0);
483 if (!is_gimple_condexpr (*tp
))
486 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
487 add_bb_predicate_gimplified_stmts (bb
, stmts
);
489 set_bb_predicate (bb
, bc
);
492 /* Add the condition COND to the previous condition PREV_COND, and add
493 this to the predicate list of the destination of edge E. LOOP is
494 the loop to be if-converted. */
497 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
498 tree prev_cond
, tree cond
)
500 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
503 if (!is_true_predicate (prev_cond
))
504 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
507 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
508 add_to_predicate_list (loop
, e
->dest
, cond
);
511 /* Return true if one of the successor edges of BB exits LOOP. */
514 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
519 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
520 if (loop_exit_edge_p (loop
, e
))
526 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
527 and it belongs to basic block BB.
529 PHI is not if-convertible if:
530 - it has more than 2 arguments.
532 When we didn't see if-convertible stores, PHI is not
534 - a virtual PHI is immediately used in another PHI node,
535 - there is a virtual PHI in a BB other than the loop->header.
536 When the aggressive_if_conv is set, PHI can have more than
540 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
541 bool any_mask_load_store
)
543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
545 fprintf (dump_file
, "-------------------------\n");
546 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
549 if (bb
!= loop
->header
)
551 if (gimple_phi_num_args (phi
) != 2
552 && !aggressive_if_conv
)
554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
555 fprintf (dump_file
, "More than two phi node args.\n");
560 if (any_mask_load_store
)
563 /* When there were no if-convertible stores, check
564 that there are no memory writes in the branches of the loop to be
566 if (virtual_operand_p (gimple_phi_result (phi
)))
568 imm_use_iterator imm_iter
;
571 if (bb
!= loop
->header
)
573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
574 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
578 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
580 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
581 && USE_STMT (use_p
) != phi
)
583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
584 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
593 /* Records the status of a data reference. This struct is attached to
594 each DR->aux field. */
597 bool rw_unconditionally
;
598 bool w_unconditionally
;
599 bool written_at_least_once
;
603 tree base_w_predicate
;
606 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
607 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
608 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
609 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
611 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
612 HASH tables. While storing them in HASH table, it checks if the
613 reference is unconditionally read or written and stores that as a flag
614 information. For base reference it checks if it is written atlest once
615 unconditionally and stores it as flag information along with DR.
616 In other words for every data reference A in STMT there exist other
617 accesses to a data reference with the same base with predicates that
618 add up (OR-up) to the true predicate: this ensures that the data
619 reference A is touched (read or written) on every iteration of the
620 if-converted loop. */
622 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
625 data_reference_p
*master_dr
, *base_master_dr
;
626 tree ref
= DR_REF (a
);
627 tree base_ref
= DR_BASE_OBJECT (a
);
628 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
631 while (TREE_CODE (ref
) == COMPONENT_REF
632 || TREE_CODE (ref
) == IMAGPART_EXPR
633 || TREE_CODE (ref
) == REALPART_EXPR
)
634 ref
= TREE_OPERAND (ref
, 0);
636 master_dr
= &ref_DR_map
->get_or_insert (ref
, &exist1
);
642 IFC_DR (*master_dr
)->w_predicate
643 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
644 IFC_DR (*master_dr
)->w_predicate
);
645 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
646 DR_W_UNCONDITIONALLY (*master_dr
) = true;
648 IFC_DR (*master_dr
)->rw_predicate
649 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
650 IFC_DR (*master_dr
)->rw_predicate
);
651 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
652 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
656 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
659 IFC_DR (*base_master_dr
)->base_w_predicate
660 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
661 IFC_DR (*base_master_dr
)->base_w_predicate
);
662 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
663 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
667 /* Return true when the memory references of STMT won't trap in the
668 if-converted code. There are two things that we have to check for:
670 - writes to memory occur to writable memory: if-conversion of
671 memory writes transforms the conditional memory writes into
672 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
673 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
674 be executed at all in the original code, it may be a readonly
675 memory. To check that A is not const-qualified, we check that
676 there exists at least an unconditional write to A in the current
679 - reads or writes to memory are valid memory accesses for every
680 iteration. To check that the memory accesses are correctly formed
681 and that we are allowed to read and write in these locations, we
682 check that the memory accesses to be if-converted occur at every
683 iteration unconditionally.
685 Returns true for the memory reference in STMT, same memory reference
686 is read or written unconditionally atleast once and the base memory
687 reference is written unconditionally once. This is to check reference
688 will not write fault. Also retuns true if the memory reference is
689 unconditionally read once then we are conditionally writing to memory
690 which is defined as read and write and is bound to the definition
693 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
695 data_reference_p
*master_dr
, *base_master_dr
;
696 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
698 tree ref_base_a
= DR_REF (a
);
699 tree base
= DR_BASE_OBJECT (a
);
701 gcc_assert (DR_STMT (a
) == stmt
);
703 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
704 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
705 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
706 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
708 master_dr
= ref_DR_map
->get (ref_base_a
);
709 base_master_dr
= baseref_DR_map
->get (base
);
711 gcc_assert (master_dr
!= NULL
);
713 /* If a is unconditionally written to it doesn't trap. */
714 if (DR_W_UNCONDITIONALLY (*master_dr
))
717 /* If a is unconditionally accessed then ... */
718 if (DR_RW_UNCONDITIONALLY (*master_dr
))
720 /* an unconditional read won't trap. */
724 /* an unconditionaly write won't trap if the base is written
725 to unconditionally. */
727 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
728 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
731 /* or the base is know to be not readonly. */
732 tree base_tree
= get_base_address (DR_REF (a
));
733 if (DECL_P (base_tree
)
734 && decl_binds_to_current_def_p (base_tree
)
735 && ! TREE_READONLY (base_tree
))
736 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
742 /* Return true if STMT could be converted into a masked load or store
743 (conditional load or store based on a mask computed from bb predicate). */
746 ifcvt_can_use_mask_load_store (gimple
*stmt
)
750 basic_block bb
= gimple_bb (stmt
);
753 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
754 || bb
->loop_father
->dont_vectorize
755 || !gimple_assign_single_p (stmt
)
756 || gimple_has_volatile_ops (stmt
))
759 /* Check whether this is a load or store. */
760 lhs
= gimple_assign_lhs (stmt
);
761 if (gimple_store_p (stmt
))
763 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
768 else if (gimple_assign_load_p (stmt
))
771 ref
= gimple_assign_rhs1 (stmt
);
776 if (may_be_nonaddressable_p (ref
))
779 /* Mask should be integer mode of the same size as the load/store
781 mode
= TYPE_MODE (TREE_TYPE (lhs
));
782 if (int_mode_for_mode (mode
) == BLKmode
783 || VECTOR_MODE_P (mode
))
786 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
792 /* Return true when STMT is if-convertible.
794 GIMPLE_ASSIGN statement is not if-convertible if,
797 - LHS is not var decl. */
800 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
801 vec
<data_reference_p
> refs
,
802 bool *any_mask_load_store
)
804 tree lhs
= gimple_assign_lhs (stmt
);
806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
808 fprintf (dump_file
, "-------------------------\n");
809 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
812 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
815 /* Some of these constrains might be too conservative. */
816 if (stmt_ends_bb_p (stmt
)
817 || gimple_has_volatile_ops (stmt
)
818 || (TREE_CODE (lhs
) == SSA_NAME
819 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
820 || gimple_has_side_effects (stmt
))
822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
823 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
827 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
828 in between if_convertible_loop_p and combine_blocks
829 we can perform loop versioning. */
830 gimple_set_plf (stmt
, GF_PLF_2
, false);
832 if ((! gimple_vuse (stmt
)
833 || gimple_could_trap_p_1 (stmt
, false, false)
834 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
835 && gimple_could_trap_p (stmt
))
837 if (ifcvt_can_use_mask_load_store (stmt
))
839 gimple_set_plf (stmt
, GF_PLF_2
, true);
840 *any_mask_load_store
= true;
843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
844 fprintf (dump_file
, "tree could trap...\n");
848 /* When if-converting stores force versioning, likewise if we
849 ended up generating store data races. */
850 if (gimple_vdef (stmt
))
851 *any_mask_load_store
= true;
856 /* Return true when STMT is if-convertible.
858 A statement is if-convertible if:
859 - it is an if-convertible GIMPLE_ASSIGN,
860 - it is a GIMPLE_LABEL or a GIMPLE_COND,
861 - it is builtins call. */
864 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
865 bool *any_mask_load_store
)
867 switch (gimple_code (stmt
))
875 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
876 any_mask_load_store
);
880 tree fndecl
= gimple_call_fndecl (stmt
);
883 int flags
= gimple_call_flags (stmt
);
884 if ((flags
& ECF_CONST
)
885 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
886 /* We can only vectorize some builtins at the moment,
887 so restrict if-conversion to those. */
888 && DECL_BUILT_IN (fndecl
))
895 /* Don't know what to do with 'em so don't do anything. */
896 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
898 fprintf (dump_file
, "don't know what to do\n");
899 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
908 /* Assumes that BB has more than 1 predecessors.
909 Returns false if at least one successor is not on critical edge
910 and true otherwise. */
913 all_preds_critical_p (basic_block bb
)
918 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
919 if (EDGE_COUNT (e
->src
->succs
) == 1)
924 /* Returns true if at least one successor in on critical edge. */
926 has_pred_critical_p (basic_block bb
)
931 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
932 if (EDGE_COUNT (e
->src
->succs
) > 1)
937 /* Return true when BB is if-convertible. This routine does not check
938 basic block's statements and phis.
940 A basic block is not if-convertible if:
941 - it is non-empty and it is after the exit block (in BFS order),
942 - it is after the exit block but before the latch,
943 - its edges are not normal.
945 Last restriction is valid if aggressive_if_conv is false.
947 EXIT_BB is the basic block containing the exit of the LOOP. BB is
951 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
956 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
957 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
959 if (EDGE_COUNT (bb
->succs
) > 2)
962 if (EDGE_COUNT (bb
->preds
) > 2
963 && !aggressive_if_conv
)
968 if (bb
!= loop
->latch
)
970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
971 fprintf (dump_file
, "basic block after exit bb but before latch\n");
974 else if (!empty_block_p (bb
))
976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
977 fprintf (dump_file
, "non empty basic block after exit bb\n");
980 else if (bb
== loop
->latch
982 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "latch is not dominated by exit_block\n");
990 /* Be less adventurous and handle only normal edges. */
991 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
992 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
995 fprintf (dump_file
, "Difficult to handle edges\n");
999 /* At least one incoming edge has to be non-critical as otherwise edge
1000 predicates are not equal to basic-block predicates of the edge
1001 source. This check is skipped if aggressive_if_conv is true. */
1002 if (!aggressive_if_conv
1003 && EDGE_COUNT (bb
->preds
) > 1
1004 && bb
!= loop
->header
1005 && all_preds_critical_p (bb
))
1007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1008 fprintf (dump_file
, "only critical predecessors\n");
1015 /* Return true when all predecessor blocks of BB are visited. The
1016 VISITED bitmap keeps track of the visited blocks. */
1019 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1023 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1024 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1030 /* Get body of a LOOP in suitable order for if-conversion. It is
1031 caller's responsibility to deallocate basic block list.
1032 If-conversion suitable order is, breadth first sort (BFS) order
1033 with an additional constraint: select a block only if all its
1034 predecessors are already selected. */
1036 static basic_block
*
1037 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1039 basic_block
*blocks
, *blocks_in_bfs_order
;
1042 unsigned int index
= 0;
1043 unsigned int visited_count
= 0;
1045 gcc_assert (loop
->num_nodes
);
1046 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1048 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1049 visited
= BITMAP_ALLOC (NULL
);
1051 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1054 while (index
< loop
->num_nodes
)
1056 bb
= blocks_in_bfs_order
[index
];
1058 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1060 free (blocks_in_bfs_order
);
1061 BITMAP_FREE (visited
);
1066 if (!bitmap_bit_p (visited
, bb
->index
))
1068 if (pred_blocks_visited_p (bb
, &visited
)
1069 || bb
== loop
->header
)
1071 /* This block is now visited. */
1072 bitmap_set_bit (visited
, bb
->index
);
1073 blocks
[visited_count
++] = bb
;
1079 if (index
== loop
->num_nodes
1080 && visited_count
!= loop
->num_nodes
)
1084 free (blocks_in_bfs_order
);
1085 BITMAP_FREE (visited
);
1089 /* Returns true when the analysis of the predicates for all the basic
1090 blocks in LOOP succeeded.
1092 predicate_bbs first allocates the predicates of the basic blocks.
1093 These fields are then initialized with the tree expressions
1094 representing the predicates under which a basic block is executed
1095 in the LOOP. As the loop->header is executed at each iteration, it
1096 has the "true" predicate. Other statements executed under a
1097 condition are predicated with that condition, for example
1104 S1 will be predicated with "x", and
1105 S2 will be predicated with "!x". */
1108 predicate_bbs (loop_p loop
)
1112 for (i
= 0; i
< loop
->num_nodes
; i
++)
1113 init_bb_predicate (ifc_bbs
[i
]);
1115 for (i
= 0; i
< loop
->num_nodes
; i
++)
1117 basic_block bb
= ifc_bbs
[i
];
1121 /* The loop latch and loop exit block are always executed and
1122 have no extra conditions to be processed: skip them. */
1123 if (bb
== loop
->latch
1124 || bb_with_exit_edge_p (loop
, bb
))
1126 reset_bb_predicate (bb
);
1130 cond
= bb_predicate (bb
);
1131 stmt
= last_stmt (bb
);
1132 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1135 edge true_edge
, false_edge
;
1136 location_t loc
= gimple_location (stmt
);
1137 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1139 gimple_cond_lhs (stmt
),
1140 gimple_cond_rhs (stmt
));
1142 /* Add new condition into destination's predicate list. */
1143 extract_true_false_edges_from_block (gimple_bb (stmt
),
1144 &true_edge
, &false_edge
);
1146 /* If C is true, then TRUE_EDGE is taken. */
1147 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1150 /* If C is false, then FALSE_EDGE is taken. */
1151 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1153 add_to_dst_predicate_list (loop
, false_edge
,
1154 unshare_expr (cond
), c2
);
1159 /* If current bb has only one successor, then consider it as an
1160 unconditional goto. */
1161 if (single_succ_p (bb
))
1163 basic_block bb_n
= single_succ (bb
);
1165 /* The successor bb inherits the predicate of its
1166 predecessor. If there is no predicate in the predecessor
1167 bb, then consider the successor bb as always executed. */
1168 if (cond
== NULL_TREE
)
1169 cond
= boolean_true_node
;
1171 add_to_predicate_list (loop
, bb_n
, cond
);
1175 /* The loop header is always executed. */
1176 reset_bb_predicate (loop
->header
);
1177 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1178 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1181 /* Return true when LOOP is if-convertible. This is a helper function
1182 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1183 in if_convertible_loop_p. */
1186 if_convertible_loop_p_1 (struct loop
*loop
,
1187 vec
<data_reference_p
> *refs
,
1188 bool *any_mask_load_store
)
1191 basic_block exit_bb
= NULL
;
1193 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1196 calculate_dominance_info (CDI_DOMINATORS
);
1197 calculate_dominance_info (CDI_POST_DOMINATORS
);
1199 /* Allow statements that can be handled during if-conversion. */
1200 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 fprintf (dump_file
, "Irreducible loop\n");
1208 for (i
= 0; i
< loop
->num_nodes
; i
++)
1210 basic_block bb
= ifc_bbs
[i
];
1212 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1215 if (bb_with_exit_edge_p (loop
, bb
))
1219 for (i
= 0; i
< loop
->num_nodes
; i
++)
1221 basic_block bb
= ifc_bbs
[i
];
1222 gimple_stmt_iterator gsi
;
1224 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1225 switch (gimple_code (gsi_stmt (gsi
)))
1232 gimple_set_uid (gsi_stmt (gsi
), 0);
1239 data_reference_p dr
;
1241 ref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1242 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1244 predicate_bbs (loop
);
1246 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1248 dr
->aux
= XNEW (struct ifc_dr
);
1249 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1250 DR_RW_UNCONDITIONALLY (dr
) = false;
1251 DR_W_UNCONDITIONALLY (dr
) = false;
1252 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1253 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1254 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1255 if (gimple_uid (DR_STMT (dr
)) == 0)
1256 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1257 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1260 for (i
= 0; i
< loop
->num_nodes
; i
++)
1262 basic_block bb
= ifc_bbs
[i
];
1263 gimple_stmt_iterator itr
;
1265 /* Check the if-convertibility of statements in predicated BBs. */
1266 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1267 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1268 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1269 any_mask_load_store
))
1273 for (i
= 0; i
< loop
->num_nodes
; i
++)
1274 free_bb_predicate (ifc_bbs
[i
]);
1276 /* Checking PHIs needs to be done after stmts, as the fact whether there
1277 are any masked loads or stores affects the tests. */
1278 for (i
= 0; i
< loop
->num_nodes
; i
++)
1280 basic_block bb
= ifc_bbs
[i
];
1283 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1284 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1285 *any_mask_load_store
))
1290 fprintf (dump_file
, "Applying if-conversion\n");
1295 /* Return true when LOOP is if-convertible.
1296 LOOP is if-convertible if:
1298 - it has two or more basic blocks,
1299 - it has only one exit,
1300 - loop header is not the exit edge,
1301 - if its basic blocks and phi nodes are if convertible. */
1304 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1309 vec
<data_reference_p
> refs
;
1311 /* Handle only innermost loop. */
1312 if (!loop
|| loop
->inner
)
1314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1315 fprintf (dump_file
, "not innermost loop\n");
1319 /* If only one block, no need for if-conversion. */
1320 if (loop
->num_nodes
<= 2)
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1323 fprintf (dump_file
, "less than 2 basic blocks\n");
1327 /* More than one loop exit is too much to handle. */
1328 if (!single_exit (loop
))
1330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1331 fprintf (dump_file
, "multiple exits\n");
1335 /* If one of the loop header's edge is an exit edge then do not
1336 apply if-conversion. */
1337 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1338 if (loop_exit_edge_p (loop
, e
))
1342 res
= if_convertible_loop_p_1 (loop
, &refs
, any_mask_load_store
);
1344 data_reference_p dr
;
1346 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1349 free_data_refs (refs
);
1354 delete baseref_DR_map
;
1355 baseref_DR_map
= NULL
;
1360 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1361 which is in predicated basic block.
1362 In fact, the following PHI pattern is searching:
1364 reduc_1 = PHI <..., reduc_2>
1368 reduc_2 = PHI <reduc_1, reduc_3>
1370 ARG_0 and ARG_1 are correspondent PHI arguments.
1371 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1372 EXTENDED is true if PHI has > 2 arguments. */
1375 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1376 tree
*op0
, tree
*op1
, bool extended
)
1378 tree lhs
, r_op1
, r_op2
;
1380 gimple
*header_phi
= NULL
;
1381 enum tree_code reduction_op
;
1382 basic_block bb
= gimple_bb (phi
);
1383 struct loop
*loop
= bb
->loop_father
;
1384 edge latch_e
= loop_latch_edge (loop
);
1385 imm_use_iterator imm_iter
;
1386 use_operand_p use_p
;
1389 bool result
= false;
1390 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1393 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1396 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1397 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1399 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1402 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1403 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1407 if (gimple_bb (header_phi
) != loop
->header
)
1410 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1413 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1414 || gimple_has_volatile_ops (stmt
))
1417 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1420 if (!is_predicated (gimple_bb (stmt
)))
1423 /* Check that stmt-block is predecessor of phi-block. */
1424 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1433 if (!has_single_use (lhs
))
1436 reduction_op
= gimple_assign_rhs_code (stmt
);
1437 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1439 r_op1
= gimple_assign_rhs1 (stmt
);
1440 r_op2
= gimple_assign_rhs2 (stmt
);
1442 /* Make R_OP1 to hold reduction variable. */
1443 if (r_op2
== PHI_RESULT (header_phi
)
1444 && reduction_op
== PLUS_EXPR
)
1445 std::swap (r_op1
, r_op2
);
1446 else if (r_op1
!= PHI_RESULT (header_phi
))
1449 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1450 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1452 gimple
*use_stmt
= USE_STMT (use_p
);
1453 if (is_gimple_debug (use_stmt
))
1455 if (use_stmt
== stmt
)
1457 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1461 *op0
= r_op1
; *op1
= r_op2
;
1466 /* Converts conditional scalar reduction into unconditional form, e.g.
1468 if (_5 != 0) goto bb_5 else goto bb_6
1474 # res_2 = PHI <res_13(4), res_6(5)>
1477 will be converted into sequence
1478 _ifc__1 = _5 != 0 ? 1 : 0;
1479 res_2 = res_13 + _ifc__1;
1480 Argument SWAP tells that arguments of conditional expression should be
1482 Returns rhs of resulting PHI assignment. */
1485 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1486 tree cond
, tree op0
, tree op1
, bool swap
)
1488 gimple_stmt_iterator stmt_it
;
1491 tree rhs1
= gimple_assign_rhs1 (reduc
);
1492 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1494 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1498 fprintf (dump_file
, "Found cond scalar reduction.\n");
1499 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1502 /* Build cond expression using COND and constant operand
1503 of reduction rhs. */
1504 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1505 unshare_expr (cond
),
1509 /* Create assignment stmt and insert it at GSI. */
1510 new_assign
= gimple_build_assign (tmp
, c
);
1511 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1512 /* Build rhs for unconditional increment/decrement. */
1513 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1514 TREE_TYPE (rhs1
), op0
, tmp
);
1516 /* Delete original reduction stmt. */
1517 stmt_it
= gsi_for_stmt (reduc
);
1518 gsi_remove (&stmt_it
, true);
1519 release_defs (reduc
);
1523 /* Produce condition for all occurrences of ARG in PHI node. */
1526 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1527 gimple_stmt_iterator
*gsi
)
1531 tree cond
= NULL_TREE
;
1535 len
= occur
->length ();
1536 gcc_assert (len
> 0);
1537 for (i
= 0; i
< len
; i
++)
1539 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1540 c
= bb_predicate (e
->src
);
1541 if (is_true_predicate (c
))
1543 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1544 is_gimple_condexpr
, NULL_TREE
,
1545 true, GSI_SAME_STMT
);
1546 if (cond
!= NULL_TREE
)
1548 /* Must build OR expression. */
1549 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1550 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1551 is_gimple_condexpr
, NULL_TREE
,
1552 true, GSI_SAME_STMT
);
1557 gcc_assert (cond
!= NULL_TREE
);
1561 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1562 This routine can handle PHI nodes with more than two arguments.
1565 S1: A = PHI <x1(1), x2(5)>
1567 S2: A = cond ? x1 : x2;
1569 The generated code is inserted at GSI that points to the top of
1570 basic block's statement list.
1571 If PHI node has more than two arguments a chain of conditional
1572 expression is produced. */
1576 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1578 gimple
*new_stmt
= NULL
, *reduc
;
1579 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1581 unsigned int index0
;
1582 unsigned int max
, args_len
;
1587 res
= gimple_phi_result (phi
);
1588 if (virtual_operand_p (res
))
1591 if ((rhs
= degenerate_phi_result (phi
))
1592 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1594 && !chrec_contains_undetermined (scev
)
1596 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1600 fprintf (dump_file
, "Degenerate phi!\n");
1601 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1603 new_stmt
= gimple_build_assign (res
, rhs
);
1604 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1605 update_stmt (new_stmt
);
1609 bb
= gimple_bb (phi
);
1610 if (EDGE_COUNT (bb
->preds
) == 2)
1612 /* Predicate ordinary PHI node with 2 arguments. */
1613 edge first_edge
, second_edge
;
1614 basic_block true_bb
;
1615 first_edge
= EDGE_PRED (bb
, 0);
1616 second_edge
= EDGE_PRED (bb
, 1);
1617 cond
= bb_predicate (first_edge
->src
);
1618 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1619 std::swap (first_edge
, second_edge
);
1620 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1622 cond
= bb_predicate (second_edge
->src
);
1623 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1624 cond
= TREE_OPERAND (cond
, 0);
1626 first_edge
= second_edge
;
1629 cond
= bb_predicate (first_edge
->src
);
1630 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1631 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1632 is_gimple_condexpr
, NULL_TREE
,
1633 true, GSI_SAME_STMT
);
1634 true_bb
= first_edge
->src
;
1635 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1637 arg0
= gimple_phi_arg_def (phi
, 1);
1638 arg1
= gimple_phi_arg_def (phi
, 0);
1642 arg0
= gimple_phi_arg_def (phi
, 0);
1643 arg1
= gimple_phi_arg_def (phi
, 1);
1645 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1647 /* Convert reduction stmt into vectorizable form. */
1648 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1649 true_bb
!= gimple_bb (reduc
));
1651 /* Build new RHS using selected condition and arguments. */
1652 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1654 new_stmt
= gimple_build_assign (res
, rhs
);
1655 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1656 update_stmt (new_stmt
);
1658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1660 fprintf (dump_file
, "new phi replacement stmt\n");
1661 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1666 /* Create hashmap for PHI node which contain vector of argument indexes
1667 having the same value. */
1669 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1670 unsigned int num_args
= gimple_phi_num_args (phi
);
1672 /* Vector of different PHI argument values. */
1673 auto_vec
<tree
> args (num_args
);
1675 /* Compute phi_arg_map. */
1676 for (i
= 0; i
< num_args
; i
++)
1680 arg
= gimple_phi_arg_def (phi
, i
);
1681 if (!phi_arg_map
.get (arg
))
1682 args
.quick_push (arg
);
1683 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1686 /* Determine element with max number of occurrences. */
1689 args_len
= args
.length ();
1690 for (i
= 0; i
< args_len
; i
++)
1693 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1700 /* Put element with max number of occurences to the end of ARGS. */
1701 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1702 std::swap (args
[args_len
- 1], args
[max_ind
]);
1704 /* Handle one special case when number of arguments with different values
1705 is equal 2 and one argument has the only occurrence. Such PHI can be
1706 handled as if would have only 2 arguments. */
1707 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1710 indexes
= phi_arg_map
.get (args
[0]);
1711 index0
= (*indexes
)[0];
1714 e
= gimple_phi_arg_edge (phi
, index0
);
1715 cond
= bb_predicate (e
->src
);
1716 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1719 cond
= TREE_OPERAND (cond
, 0);
1721 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1722 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1723 is_gimple_condexpr
, NULL_TREE
,
1724 true, GSI_SAME_STMT
);
1725 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1727 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1731 /* Convert reduction stmt into vectorizable form. */
1732 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1734 new_stmt
= gimple_build_assign (res
, rhs
);
1735 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1736 update_stmt (new_stmt
);
1742 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1745 for (i
= 0; i
< args_len
; i
++)
1748 indexes
= phi_arg_map
.get (args
[i
]);
1749 if (i
!= args_len
- 1)
1750 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1753 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1754 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1756 new_stmt
= gimple_build_assign (lhs
, rhs
);
1757 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1758 update_stmt (new_stmt
);
1763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1765 fprintf (dump_file
, "new extended phi replacement stmt\n");
1766 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1770 /* Replaces in LOOP all the scalar phi nodes other than those in the
1771 LOOP->header block with conditional modify expressions. */
1774 predicate_all_scalar_phis (struct loop
*loop
)
1777 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1780 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1783 gimple_stmt_iterator gsi
;
1784 gphi_iterator phi_gsi
;
1787 if (bb
== loop
->header
)
1790 if (EDGE_COUNT (bb
->preds
) == 1)
1793 phi_gsi
= gsi_start_phis (bb
);
1794 if (gsi_end_p (phi_gsi
))
1797 gsi
= gsi_after_labels (bb
);
1798 while (!gsi_end_p (phi_gsi
))
1800 phi
= phi_gsi
.phi ();
1801 predicate_scalar_phi (phi
, &gsi
);
1802 release_phi_node (phi
);
1803 gsi_next (&phi_gsi
);
1806 set_phi_nodes (bb
, NULL
);
1810 /* Insert in each basic block of LOOP the statements produced by the
1811 gimplification of the predicates. */
1814 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1818 for (i
= 0; i
< loop
->num_nodes
; i
++)
1820 basic_block bb
= ifc_bbs
[i
];
1822 if (!is_predicated (bb
))
1823 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1824 if (!is_predicated (bb
))
1826 /* Do not insert statements for a basic block that is not
1827 predicated. Also make sure that the predicate of the
1828 basic block is set to true. */
1829 reset_bb_predicate (bb
);
1833 stmts
= bb_predicate_gimplified_stmts (bb
);
1836 if (any_mask_load_store
)
1838 /* Insert the predicate of the BB just after the label,
1839 as the if-conversion of memory writes will use this
1841 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1842 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1846 /* Insert the predicate of the BB at the end of the BB
1847 as this would reduce the register pressure: the only
1848 use of this predicate will be in successor BBs. */
1849 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1852 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1853 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1855 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1858 /* Once the sequence is code generated, set it to NULL. */
1859 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1864 /* Helper function for predicate_mem_writes. Returns index of existent
1865 mask if it was created for given SIZE and -1 otherwise. */
1868 mask_exists (int size
, vec
<int> vec
)
1872 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1878 /* Predicate each write to memory in LOOP.
1880 This function transforms control flow constructs containing memory
1883 | for (i = 0; i < N; i++)
1887 into the following form that does not contain control flow:
1889 | for (i = 0; i < N; i++)
1890 | A[i] = cond ? expr : A[i];
1892 The original CFG looks like this:
1899 | if (i < N) goto bb_5 else goto bb_2
1903 | cond = some_computation;
1904 | if (cond) goto bb_3 else goto bb_4
1916 insert_gimplified_predicates inserts the computation of the COND
1917 expression at the beginning of the destination basic block:
1924 | if (i < N) goto bb_5 else goto bb_2
1928 | cond = some_computation;
1929 | if (cond) goto bb_3 else goto bb_4
1933 | cond = some_computation;
1942 predicate_mem_writes is then predicating the memory write as follows:
1949 | if (i < N) goto bb_5 else goto bb_2
1953 | if (cond) goto bb_3 else goto bb_4
1957 | cond = some_computation;
1958 | A[i] = cond ? expr : A[i];
1966 and finally combine_blocks removes the basic block boundaries making
1967 the loop vectorizable:
1971 | if (i < N) goto bb_5 else goto bb_1
1975 | cond = some_computation;
1976 | A[i] = cond ? expr : A[i];
1977 | if (i < N) goto bb_5 else goto bb_4
1986 predicate_mem_writes (loop_p loop
)
1988 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1989 auto_vec
<int, 1> vect_sizes
;
1990 auto_vec
<tree
, 1> vect_masks
;
1992 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1994 gimple_stmt_iterator gsi
;
1995 basic_block bb
= ifc_bbs
[i
];
1996 tree cond
= bb_predicate (bb
);
2001 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2005 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2008 cond
= TREE_OPERAND (cond
, 0);
2011 vect_sizes
.truncate (0);
2012 vect_masks
.truncate (0);
2014 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2015 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2017 else if (gimple_plf (stmt
, GF_PLF_2
))
2019 tree lhs
= gimple_assign_lhs (stmt
);
2020 tree rhs
= gimple_assign_rhs1 (stmt
);
2021 tree ref
, addr
, ptr
, mask
;
2023 gimple_seq stmts
= NULL
;
2024 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2025 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2026 mark_addressable (ref
);
2027 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2028 true, NULL_TREE
, true,
2030 if (!vect_sizes
.is_empty ()
2031 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2032 /* Use created mask. */
2033 mask
= vect_masks
[index
];
2036 if (COMPARISON_CLASS_P (cond
))
2037 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2039 TREE_OPERAND (cond
, 0),
2040 TREE_OPERAND (cond
, 1));
2043 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2050 = constant_boolean_node (true, TREE_TYPE (mask
));
2051 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2052 TREE_TYPE (mask
), mask
, true_val
);
2054 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2056 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2057 /* Save mask and its size for further use. */
2058 vect_sizes
.safe_push (bitsize
);
2059 vect_masks
.safe_push (mask
);
2061 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2062 get_object_alignment (ref
));
2063 /* Copy points-to info if possible. */
2064 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2065 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2067 if (TREE_CODE (lhs
) == SSA_NAME
)
2070 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2072 gimple_call_set_lhs (new_stmt
, lhs
);
2076 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2078 gsi_replace (&gsi
, new_stmt
, true);
2080 else if (gimple_vdef (stmt
))
2082 tree lhs
= gimple_assign_lhs (stmt
);
2083 tree rhs
= gimple_assign_rhs1 (stmt
);
2084 tree type
= TREE_TYPE (lhs
);
2086 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2087 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2089 std::swap (lhs
, rhs
);
2090 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2091 is_gimple_condexpr
, NULL_TREE
,
2092 true, GSI_SAME_STMT
);
2093 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2094 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2100 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2101 other than the exit and latch of the LOOP. Also resets the
2102 GIMPLE_DEBUG information. */
2105 remove_conditions_and_labels (loop_p loop
)
2107 gimple_stmt_iterator gsi
;
2110 for (i
= 0; i
< loop
->num_nodes
; i
++)
2112 basic_block bb
= ifc_bbs
[i
];
2114 if (bb_with_exit_edge_p (loop
, bb
)
2115 || bb
== loop
->latch
)
2118 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2119 switch (gimple_code (gsi_stmt (gsi
)))
2123 gsi_remove (&gsi
, true);
2127 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2128 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2130 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2131 update_stmt (gsi_stmt (gsi
));
2142 /* Combine all the basic blocks from LOOP into one or two super basic
2143 blocks. Replace PHI nodes with conditional modify expressions. */
2146 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2148 basic_block bb
, exit_bb
, merge_target_bb
;
2149 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2154 predicate_bbs (loop
);
2155 remove_conditions_and_labels (loop
);
2156 insert_gimplified_predicates (loop
, any_mask_load_store
);
2157 predicate_all_scalar_phis (loop
);
2159 if (any_mask_load_store
)
2160 predicate_mem_writes (loop
);
2162 /* Merge basic blocks: first remove all the edges in the loop,
2163 except for those from the exit block. */
2165 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2166 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2169 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2170 free_bb_predicate (bb
);
2171 if (bb_with_exit_edge_p (loop
, bb
))
2173 gcc_assert (exit_bb
== NULL
);
2177 gcc_assert (exit_bb
!= loop
->latch
);
2179 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2183 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2185 if (e
->src
== exit_bb
)
2192 if (exit_bb
!= NULL
)
2194 if (exit_bb
!= loop
->header
)
2196 /* Connect this node to loop header. */
2197 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2198 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2201 /* Redirect non-exit edges to loop->latch. */
2202 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2204 if (!loop_exit_edge_p (loop
, e
))
2205 redirect_edge_and_branch (e
, loop
->latch
);
2207 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2211 /* If the loop does not have an exit, reconnect header and latch. */
2212 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2213 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2216 merge_target_bb
= loop
->header
;
2217 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2219 gimple_stmt_iterator gsi
;
2220 gimple_stmt_iterator last
;
2224 if (bb
== exit_bb
|| bb
== loop
->latch
)
2227 /* Make stmts member of loop->header and clear range info from all stmts
2228 in BB which is now no longer executed conditional on a predicate we
2229 could have derived it from. */
2230 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2232 gimple
*stmt
= gsi_stmt (gsi
);
2233 gimple_set_bb (stmt
, merge_target_bb
);
2238 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2239 reset_flow_sensitive_info (op
);
2243 /* Update stmt list. */
2244 last
= gsi_last_bb (merge_target_bb
);
2245 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2246 set_bb_seq (bb
, NULL
);
2248 delete_basic_block (bb
);
2251 /* If possible, merge loop header to the block with the exit edge.
2252 This reduces the number of basic blocks to two, to please the
2253 vectorizer that handles only loops with two nodes. */
2255 && exit_bb
!= loop
->header
2256 && can_merge_blocks_p (loop
->header
, exit_bb
))
2257 merge_blocks (loop
->header
, exit_bb
);
2264 /* Version LOOP before if-converting it; the original loop
2265 will be if-converted, the new copy of the loop will not,
2266 and the LOOP_VECTORIZED internal call will be guarding which
2267 loop to execute. The vectorizer pass will fold this
2268 internal call into either true or false. */
2271 version_loop_for_if_conversion (struct loop
*loop
)
2273 basic_block cond_bb
;
2274 tree cond
= make_ssa_name (boolean_type_node
);
2275 struct loop
*new_loop
;
2277 gimple_stmt_iterator gsi
;
2279 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2280 build_int_cst (integer_type_node
, loop
->num
),
2282 gimple_call_set_lhs (g
, cond
);
2284 initialize_original_copy_tables ();
2285 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2286 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2287 REG_BR_PROB_BASE
, true);
2288 free_original_copy_tables ();
2289 if (new_loop
== NULL
)
2291 new_loop
->dont_vectorize
= true;
2292 new_loop
->force_vectorize
= false;
2293 gsi
= gsi_last_bb (cond_bb
);
2294 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2295 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2296 update_ssa (TODO_update_ssa
);
2300 /* Performs splitting of critical edges if aggressive_if_conv is true.
2301 Returns false if loop won't be if converted and true otherwise. */
2304 ifcvt_split_critical_edges (struct loop
*loop
)
2308 unsigned int num
= loop
->num_nodes
;
2318 if (!single_exit (loop
))
2321 body
= get_loop_body (loop
);
2322 for (i
= 0; i
< num
; i
++)
2325 if (bb
== loop
->latch
2326 || bb_with_exit_edge_p (loop
, bb
))
2328 stmt
= last_stmt (bb
);
2329 /* Skip basic blocks not ending with conditional branch. */
2330 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2332 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2333 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2340 /* Assumes that lhs of DEF_STMT have multiple uses.
2341 Delete one use by (1) creation of copy DEF_STMT with
2342 unique lhs; (2) change original use of lhs in one
2343 use statement with newly created lhs. */
2346 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2351 gimple_stmt_iterator gsi
;
2352 use_operand_p use_p
;
2353 imm_use_iterator imm_iter
;
2355 var
= gimple_assign_lhs (def_stmt
);
2356 copy_stmt
= gimple_copy (def_stmt
);
2357 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2358 gimple_assign_set_lhs (copy_stmt
, lhs
);
2359 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2360 /* Insert copy of DEF_STMT. */
2361 gsi
= gsi_for_stmt (def_stmt
);
2362 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2363 /* Change use of var to lhs in use_stmt. */
2364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2366 fprintf (dump_file
, "Change use of var ");
2367 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2368 fprintf (dump_file
, " to ");
2369 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2370 fprintf (dump_file
, "\n");
2372 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2374 if (USE_STMT (use_p
) != use_stmt
)
2376 SET_USE (use_p
, lhs
);
2381 /* Traverse bool pattern recursively starting from VAR.
2382 Save its def and use statements to defuse_list if VAR does
2383 not have single use. */
2386 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2390 enum tree_code code
;
2393 def_stmt
= SSA_NAME_DEF_STMT (var
);
2394 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2396 if (!has_single_use (var
))
2398 /* Put def and use stmts into defuse_list. */
2399 defuse_list
->safe_push (def_stmt
);
2400 defuse_list
->safe_push (use_stmt
);
2401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2403 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2404 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2407 rhs1
= gimple_assign_rhs1 (def_stmt
);
2408 code
= gimple_assign_rhs_code (def_stmt
);
2412 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2415 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2416 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2417 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2419 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2422 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2427 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2428 rhs2
= gimple_assign_rhs2 (def_stmt
);
2429 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2437 /* Returns true if STMT can be a root of bool pattern applied
2441 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2443 enum tree_code code
;
2446 code
= gimple_assign_rhs_code (stmt
);
2447 if (CONVERT_EXPR_CODE_P (code
))
2449 lhs
= gimple_assign_lhs (stmt
);
2450 rhs
= gimple_assign_rhs1 (stmt
);
2451 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2453 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2457 else if (code
== COND_EXPR
)
2459 rhs
= gimple_assign_rhs1 (stmt
);
2460 if (TREE_CODE (rhs
) != SSA_NAME
)
2467 /* Traverse all statements in BB which correspond to loop header to
2468 find out all statements which can start bool pattern applied by
2469 vectorizer and convert multiple uses in it to conform pattern
2470 restrictions. Such case can occur if the same predicate is used both
2471 for phi node conversion and load/store mask. */
2474 ifcvt_repair_bool_pattern (basic_block bb
)
2478 gimple_stmt_iterator gsi
;
2479 vec
<gimple
*> defuse_list
= vNULL
;
2480 vec
<gimple
*> pattern_roots
= vNULL
;
2485 /* Collect all root pattern statements. */
2486 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2488 stmt
= gsi_stmt (gsi
);
2489 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2491 if (!stmt_is_root_of_bool_pattern (stmt
))
2493 pattern_roots
.safe_push (stmt
);
2496 if (pattern_roots
.is_empty ())
2499 /* Split all statements with multiple uses iteratively since splitting
2500 may create new multiple uses. */
2505 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2507 rhs
= gimple_assign_rhs1 (stmt
);
2508 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2509 while (defuse_list
.length () > 0)
2512 gimple
*def_stmt
, *use_stmt
;
2513 use_stmt
= defuse_list
.pop ();
2514 def_stmt
= defuse_list
.pop ();
2515 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2521 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2525 /* Delete redundant statements produced by predication which prevents
2526 loop vectorization. */
2529 ifcvt_local_dce (basic_block bb
)
2534 gimple_stmt_iterator gsi
;
2535 auto_vec
<gimple
*> worklist
;
2536 enum gimple_code code
;
2537 use_operand_p use_p
;
2538 imm_use_iterator imm_iter
;
2540 worklist
.create (64);
2541 /* Consider all phi as live statements. */
2542 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2544 phi
= gsi_stmt (gsi
);
2545 gimple_set_plf (phi
, GF_PLF_2
, true);
2546 worklist
.safe_push (phi
);
2548 /* Consider load/store statements, CALL and COND as live. */
2549 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2551 stmt
= gsi_stmt (gsi
);
2552 if (gimple_store_p (stmt
)
2553 || gimple_assign_load_p (stmt
)
2554 || is_gimple_debug (stmt
))
2556 gimple_set_plf (stmt
, GF_PLF_2
, true);
2557 worklist
.safe_push (stmt
);
2560 code
= gimple_code (stmt
);
2561 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2563 gimple_set_plf (stmt
, GF_PLF_2
, true);
2564 worklist
.safe_push (stmt
);
2567 gimple_set_plf (stmt
, GF_PLF_2
, false);
2569 if (code
== GIMPLE_ASSIGN
)
2571 tree lhs
= gimple_assign_lhs (stmt
);
2572 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2574 stmt1
= USE_STMT (use_p
);
2575 if (gimple_bb (stmt1
) != bb
)
2577 gimple_set_plf (stmt
, GF_PLF_2
, true);
2578 worklist
.safe_push (stmt
);
2584 /* Propagate liveness through arguments of live stmt. */
2585 while (worklist
.length () > 0)
2588 use_operand_p use_p
;
2591 stmt
= worklist
.pop ();
2592 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2594 use
= USE_FROM_PTR (use_p
);
2595 if (TREE_CODE (use
) != SSA_NAME
)
2597 stmt1
= SSA_NAME_DEF_STMT (use
);
2598 if (gimple_bb (stmt1
) != bb
2599 || gimple_plf (stmt1
, GF_PLF_2
))
2601 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2602 worklist
.safe_push (stmt1
);
2605 /* Delete dead statements. */
2606 gsi
= gsi_start_bb (bb
);
2607 while (!gsi_end_p (gsi
))
2609 stmt
= gsi_stmt (gsi
);
2610 if (gimple_plf (stmt
, GF_PLF_2
))
2615 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2617 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2618 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2620 gsi_remove (&gsi
, true);
2621 release_defs (stmt
);
2625 /* If-convert LOOP when it is legal. For the moment this pass has no
2626 profitability analysis. Returns non-zero todo flags when something
2630 tree_if_conversion (struct loop
*loop
)
2632 unsigned int todo
= 0;
2634 bool any_mask_load_store
= false;
2636 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2637 aggressive_if_conv
= loop
->force_vectorize
;
2638 /* Check either outer loop was marked with simd pragma. */
2639 if (!aggressive_if_conv
)
2641 struct loop
*outer_loop
= loop_outer (loop
);
2642 if (outer_loop
&& outer_loop
->force_vectorize
)
2643 aggressive_if_conv
= true;
2646 if (aggressive_if_conv
)
2647 if (!ifcvt_split_critical_edges (loop
))
2650 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2651 || !dbg_cnt (if_conversion_tree
))
2654 if (any_mask_load_store
2655 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2656 || loop
->dont_vectorize
))
2659 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2662 /* Now all statements are if-convertible. Combine all the basic
2663 blocks into one huge basic block doing the if-conversion
2665 combine_blocks (loop
, any_mask_load_store
);
2667 /* Delete dead predicate computations and repair tree correspondent
2668 to bool pattern to delete multiple uses of predicates. */
2669 if (aggressive_if_conv
)
2671 ifcvt_local_dce (loop
->header
);
2672 ifcvt_repair_bool_pattern (loop
->header
);
2675 todo
|= TODO_cleanup_cfg
;
2676 if (any_mask_load_store
)
2678 mark_virtual_operands_for_renaming (cfun
);
2679 todo
|= TODO_update_ssa_only_virtuals
;
2687 for (i
= 0; i
< loop
->num_nodes
; i
++)
2688 free_bb_predicate (ifc_bbs
[i
]);
2693 free_dominance_info (CDI_POST_DOMINATORS
);
2698 /* Tree if-conversion pass management. */
2702 const pass_data pass_data_if_conversion
=
2704 GIMPLE_PASS
, /* type */
2706 OPTGROUP_NONE
, /* optinfo_flags */
2707 TV_NONE
, /* tv_id */
2708 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2709 0, /* properties_provided */
2710 0, /* properties_destroyed */
2711 0, /* todo_flags_start */
2712 0, /* todo_flags_finish */
2715 class pass_if_conversion
: public gimple_opt_pass
2718 pass_if_conversion (gcc::context
*ctxt
)
2719 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2722 /* opt_pass methods: */
2723 virtual bool gate (function
*);
2724 virtual unsigned int execute (function
*);
2726 }; // class pass_if_conversion
2729 pass_if_conversion::gate (function
*fun
)
2731 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2732 && flag_tree_loop_if_convert
!= 0)
2733 || flag_tree_loop_if_convert
== 1
2734 || flag_tree_loop_if_convert_stores
== 1);
2738 pass_if_conversion::execute (function
*fun
)
2743 if (number_of_loops (fun
) <= 1)
2746 FOR_EACH_LOOP (loop
, 0)
2747 if (flag_tree_loop_if_convert
== 1
2748 || flag_tree_loop_if_convert_stores
== 1
2749 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2750 && !loop
->dont_vectorize
))
2751 todo
|= tree_if_conversion (loop
);
2756 FOR_EACH_BB_FN (bb
, fun
)
2757 gcc_assert (!bb
->aux
);
2766 make_pass_if_conversion (gcc::context
*ctxt
)
2768 return new pass_if_conversion (ctxt
);