1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2015 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"
116 /* List of basic blocks in if-conversion-suitable order. */
117 static basic_block
*ifc_bbs
;
119 /* Apply more aggressive (extended) if-conversion if true. */
120 static bool aggressive_if_conv
;
122 /* Hash table to store references, DR pairs. */
123 static hash_map
<tree_operand_hash
, data_reference_p
> *ref_DR_map
;
125 /* Hash table to store base reference, DR pairs. */
126 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
128 /* Structure used to predicate basic blocks. This is attached to the
129 ->aux field of the BBs in the loop to be if-converted. */
130 struct bb_predicate
{
132 /* The condition under which this basic block is executed. */
135 /* PREDICATE is gimplified, and the sequence of statements is
136 recorded here, in order to avoid the duplication of computations
137 that occur in previous conditions. See PR44483. */
138 gimple_seq predicate_gimplified_stmts
;
141 /* Returns true when the basic block BB has a predicate. */
144 bb_has_predicate (basic_block bb
)
146 return bb
->aux
!= NULL
;
149 /* Returns the gimplified predicate for basic block BB. */
152 bb_predicate (basic_block bb
)
154 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
157 /* Sets the gimplified predicate COND for basic block BB. */
160 set_bb_predicate (basic_block bb
, tree cond
)
162 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
163 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
164 || is_gimple_condexpr (cond
));
165 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
168 /* Returns the sequence of statements of the gimplification of the
169 predicate for basic block BB. */
171 static inline gimple_seq
172 bb_predicate_gimplified_stmts (basic_block bb
)
174 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
177 /* Sets the sequence of statements STMTS of the gimplification of the
178 predicate for basic block BB. */
181 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
183 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
186 /* Adds the sequence of statements STMTS to the sequence of statements
187 of the predicate for basic block BB. */
190 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
193 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
196 /* Initializes to TRUE the predicate of basic block BB. */
199 init_bb_predicate (basic_block bb
)
201 bb
->aux
= XNEW (struct bb_predicate
);
202 set_bb_predicate_gimplified_stmts (bb
, NULL
);
203 set_bb_predicate (bb
, boolean_true_node
);
206 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
207 but don't actually free it. */
210 release_bb_predicate (basic_block bb
)
212 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
215 gimple_stmt_iterator i
;
217 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
218 free_stmt_operands (cfun
, gsi_stmt (i
));
219 set_bb_predicate_gimplified_stmts (bb
, NULL
);
223 /* Free the predicate of basic block BB. */
226 free_bb_predicate (basic_block bb
)
228 if (!bb_has_predicate (bb
))
231 release_bb_predicate (bb
);
236 /* Reinitialize predicate of BB with the true predicate. */
239 reset_bb_predicate (basic_block bb
)
241 if (!bb_has_predicate (bb
))
242 init_bb_predicate (bb
);
245 release_bb_predicate (bb
);
246 set_bb_predicate (bb
, boolean_true_node
);
250 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
251 the expression EXPR. Inserts the statement created for this
252 computation before GSI and leaves the iterator GSI at the same
256 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
258 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
259 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
260 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
264 /* Return true when COND is a true predicate. */
267 is_true_predicate (tree cond
)
269 return (cond
== NULL_TREE
270 || cond
== boolean_true_node
271 || integer_onep (cond
));
274 /* Returns true when BB has a predicate that is not trivial: true or
278 is_predicated (basic_block bb
)
280 return !is_true_predicate (bb_predicate (bb
));
283 /* Parses the predicate COND and returns its comparison code and
284 operands OP0 and OP1. */
286 static enum tree_code
287 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
291 if (TREE_CODE (cond
) == SSA_NAME
292 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
294 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
296 *op0
= gimple_assign_rhs1 (s
);
297 *op1
= gimple_assign_rhs2 (s
);
298 return gimple_assign_rhs_code (s
);
301 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
303 tree op
= gimple_assign_rhs1 (s
);
304 tree type
= TREE_TYPE (op
);
305 enum tree_code code
= parse_predicate (op
, op0
, op1
);
307 return code
== ERROR_MARK
? ERROR_MARK
308 : invert_tree_comparison (code
, HONOR_NANS (type
));
314 if (COMPARISON_CLASS_P (cond
))
316 *op0
= TREE_OPERAND (cond
, 0);
317 *op1
= TREE_OPERAND (cond
, 1);
318 return TREE_CODE (cond
);
324 /* Returns the fold of predicate C1 OR C2 at location LOC. */
327 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
329 tree op1a
, op1b
, op2a
, op2b
;
330 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
331 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
333 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
335 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
341 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
344 /* Returns true if N is either a constant or a SSA_NAME. */
347 constant_or_ssa_name (tree n
)
349 switch (TREE_CODE (n
))
362 /* Returns either a COND_EXPR or the folded expression if the folded
363 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
364 a constant or a SSA_NAME. */
367 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
369 tree rhs1
, lhs1
, cond_expr
;
371 /* If COND is comparison r != 0 and r has boolean type, convert COND
372 to SSA_NAME to accept by vect bool pattern. */
373 if (TREE_CODE (cond
) == NE_EXPR
)
375 tree op0
= TREE_OPERAND (cond
, 0);
376 tree op1
= TREE_OPERAND (cond
, 1);
377 if (TREE_CODE (op0
) == SSA_NAME
378 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
379 && (integer_zerop (op1
)))
382 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
385 if (cond_expr
== NULL_TREE
)
386 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
388 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
390 if (constant_or_ssa_name (cond_expr
))
393 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
395 rhs1
= TREE_OPERAND (cond_expr
, 1);
396 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
397 if (constant_or_ssa_name (rhs1
))
398 return build1 (ABS_EXPR
, type
, rhs1
);
401 if (TREE_CODE (cond_expr
) == MIN_EXPR
402 || TREE_CODE (cond_expr
) == MAX_EXPR
)
404 lhs1
= TREE_OPERAND (cond_expr
, 0);
405 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
406 rhs1
= TREE_OPERAND (cond_expr
, 1);
407 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
408 if (constant_or_ssa_name (rhs1
)
409 && constant_or_ssa_name (lhs1
))
410 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
412 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
415 /* Add condition NC to the predicate list of basic block BB. LOOP is
416 the loop to be if-converted. Use predicate of cd-equivalent block
417 for join bb if it exists: we call basic blocks bb1 and bb2
418 cd-equivalent if they are executed under the same condition. */
421 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
426 if (is_true_predicate (nc
))
429 /* If dominance tells us this basic block is always executed,
430 don't record any predicates for it. */
431 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
434 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
435 /* We use notion of cd equivalence to get simpler predicate for
436 join block, e.g. if join block has 2 predecessors with predicates
437 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
438 p1 & p2 | p1 & !p2. */
439 if (dom_bb
!= loop
->header
440 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
442 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
443 bc
= bb_predicate (dom_bb
);
444 if (!is_true_predicate (bc
))
445 set_bb_predicate (bb
, bc
);
447 gcc_assert (is_true_predicate (bb_predicate (bb
)));
448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
449 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
450 dom_bb
->index
, bb
->index
);
454 if (!is_predicated (bb
))
458 bc
= bb_predicate (bb
);
459 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
460 if (is_true_predicate (bc
))
462 reset_bb_predicate (bb
);
467 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
468 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
469 tp
= &TREE_OPERAND (bc
, 0);
472 if (!is_gimple_condexpr (*tp
))
475 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
476 add_bb_predicate_gimplified_stmts (bb
, stmts
);
478 set_bb_predicate (bb
, bc
);
481 /* Add the condition COND to the previous condition PREV_COND, and add
482 this to the predicate list of the destination of edge E. LOOP is
483 the loop to be if-converted. */
486 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
487 tree prev_cond
, tree cond
)
489 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
492 if (!is_true_predicate (prev_cond
))
493 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
496 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
497 add_to_predicate_list (loop
, e
->dest
, cond
);
500 /* Return true if one of the successor edges of BB exits LOOP. */
503 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
508 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
509 if (loop_exit_edge_p (loop
, e
))
515 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
516 and it belongs to basic block BB.
518 PHI is not if-convertible if:
519 - it has more than 2 arguments.
521 When we didn't see if-convertible stores, PHI is not
523 - a virtual PHI is immediately used in another PHI node,
524 - there is a virtual PHI in a BB other than the loop->header.
525 When the aggressive_if_conv is set, PHI can have more than
529 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
530 bool any_mask_load_store
)
532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
534 fprintf (dump_file
, "-------------------------\n");
535 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
538 if (bb
!= loop
->header
)
540 if (gimple_phi_num_args (phi
) != 2
541 && !aggressive_if_conv
)
543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
544 fprintf (dump_file
, "More than two phi node args.\n");
549 if (any_mask_load_store
)
552 /* When there were no if-convertible stores, check
553 that there are no memory writes in the branches of the loop to be
555 if (virtual_operand_p (gimple_phi_result (phi
)))
557 imm_use_iterator imm_iter
;
560 if (bb
!= loop
->header
)
562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
563 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
567 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
569 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
570 && USE_STMT (use_p
) != phi
)
572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
582 /* Records the status of a data reference. This struct is attached to
583 each DR->aux field. */
586 bool rw_unconditionally
;
587 bool w_unconditionally
;
588 bool written_at_least_once
;
592 tree base_w_predicate
;
595 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
596 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
597 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
598 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
600 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
601 HASH tables. While storing them in HASH table, it checks if the
602 reference is unconditionally read or written and stores that as a flag
603 information. For base reference it checks if it is written atlest once
604 unconditionally and stores it as flag information along with DR.
605 In other words for every data reference A in STMT there exist other
606 accesses to a data reference with the same base with predicates that
607 add up (OR-up) to the true predicate: this ensures that the data
608 reference A is touched (read or written) on every iteration of the
609 if-converted loop. */
611 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
614 data_reference_p
*master_dr
, *base_master_dr
;
615 tree ref
= DR_REF (a
);
616 tree base_ref
= DR_BASE_OBJECT (a
);
617 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
620 while (TREE_CODE (ref
) == COMPONENT_REF
621 || TREE_CODE (ref
) == IMAGPART_EXPR
622 || TREE_CODE (ref
) == REALPART_EXPR
)
623 ref
= TREE_OPERAND (ref
, 0);
625 master_dr
= &ref_DR_map
->get_or_insert (ref
, &exist1
);
631 IFC_DR (*master_dr
)->w_predicate
632 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
633 IFC_DR (*master_dr
)->w_predicate
);
634 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
635 DR_W_UNCONDITIONALLY (*master_dr
) = true;
637 IFC_DR (*master_dr
)->rw_predicate
638 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
639 IFC_DR (*master_dr
)->rw_predicate
);
640 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
641 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
645 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
648 IFC_DR (*base_master_dr
)->base_w_predicate
649 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
650 IFC_DR (*base_master_dr
)->base_w_predicate
);
651 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
652 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
656 /* Return true when the memory references of STMT won't trap in the
657 if-converted code. There are two things that we have to check for:
659 - writes to memory occur to writable memory: if-conversion of
660 memory writes transforms the conditional memory writes into
661 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
662 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
663 be executed at all in the original code, it may be a readonly
664 memory. To check that A is not const-qualified, we check that
665 there exists at least an unconditional write to A in the current
668 - reads or writes to memory are valid memory accesses for every
669 iteration. To check that the memory accesses are correctly formed
670 and that we are allowed to read and write in these locations, we
671 check that the memory accesses to be if-converted occur at every
672 iteration unconditionally.
674 Returns true for the memory reference in STMT, same memory reference
675 is read or written unconditionally atleast once and the base memory
676 reference is written unconditionally once. This is to check reference
677 will not write fault. Also retuns true if the memory reference is
678 unconditionally read once then we are conditionally writing to memory
679 which is defined as read and write and is bound to the definition
682 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
684 data_reference_p
*master_dr
, *base_master_dr
;
685 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
687 tree ref_base_a
= DR_REF (a
);
688 tree base
= DR_BASE_OBJECT (a
);
690 gcc_assert (DR_STMT (a
) == stmt
);
692 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
693 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
694 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
695 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
697 master_dr
= ref_DR_map
->get (ref_base_a
);
698 base_master_dr
= baseref_DR_map
->get (base
);
700 gcc_assert (master_dr
!= NULL
);
702 /* If a is unconditionally written to it doesn't trap. */
703 if (DR_W_UNCONDITIONALLY (*master_dr
))
706 /* If a is unconditionally accessed then ... */
707 if (DR_RW_UNCONDITIONALLY (*master_dr
))
709 /* an unconditional read won't trap. */
713 /* an unconditionaly write won't trap if the base is written
714 to unconditionally. */
716 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
717 return flag_tree_loop_if_convert_stores
;
720 /* or the base is know to be not readonly. */
721 tree base_tree
= get_base_address (DR_REF (a
));
722 if (DECL_P (base_tree
)
723 && decl_binds_to_current_def_p (base_tree
)
724 && ! TREE_READONLY (base_tree
))
725 return flag_tree_loop_if_convert_stores
;
731 /* Return true if STMT could be converted into a masked load or store
732 (conditional load or store based on a mask computed from bb predicate). */
735 ifcvt_can_use_mask_load_store (gimple
*stmt
)
739 basic_block bb
= gimple_bb (stmt
);
742 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
743 || bb
->loop_father
->dont_vectorize
744 || !gimple_assign_single_p (stmt
)
745 || gimple_has_volatile_ops (stmt
))
748 /* Check whether this is a load or store. */
749 lhs
= gimple_assign_lhs (stmt
);
750 if (gimple_store_p (stmt
))
752 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
757 else if (gimple_assign_load_p (stmt
))
760 ref
= gimple_assign_rhs1 (stmt
);
765 if (may_be_nonaddressable_p (ref
))
768 /* Mask should be integer mode of the same size as the load/store
770 mode
= TYPE_MODE (TREE_TYPE (lhs
));
771 if (int_mode_for_mode (mode
) == BLKmode
772 || VECTOR_MODE_P (mode
))
775 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
781 /* Return true when STMT is if-convertible.
783 GIMPLE_ASSIGN statement is not if-convertible if,
786 - LHS is not var decl. */
789 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
790 vec
<data_reference_p
> refs
,
791 bool *any_mask_load_store
)
793 tree lhs
= gimple_assign_lhs (stmt
);
795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
797 fprintf (dump_file
, "-------------------------\n");
798 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
801 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
804 /* Some of these constrains might be too conservative. */
805 if (stmt_ends_bb_p (stmt
)
806 || gimple_has_volatile_ops (stmt
)
807 || (TREE_CODE (lhs
) == SSA_NAME
808 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
809 || gimple_has_side_effects (stmt
))
811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
812 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
816 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
817 in between if_convertible_loop_p and combine_blocks
818 we can perform loop versioning. */
819 gimple_set_plf (stmt
, GF_PLF_2
, false);
821 if ((! gimple_vuse (stmt
)
822 || gimple_could_trap_p_1 (stmt
, false, false)
823 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
824 && gimple_could_trap_p (stmt
))
826 if (ifcvt_can_use_mask_load_store (stmt
))
828 gimple_set_plf (stmt
, GF_PLF_2
, true);
829 *any_mask_load_store
= true;
832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 fprintf (dump_file
, "tree could trap...\n");
837 /* When if-converting stores force versioning, likewise if we
838 ended up generating store data races. */
839 if (gimple_vdef (stmt
))
840 *any_mask_load_store
= true;
845 /* Return true when STMT is if-convertible.
847 A statement is if-convertible if:
848 - it is an if-convertible GIMPLE_ASSIGN,
849 - it is a GIMPLE_LABEL or a GIMPLE_COND,
850 - it is builtins call. */
853 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
854 bool *any_mask_load_store
)
856 switch (gimple_code (stmt
))
864 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
865 any_mask_load_store
);
869 tree fndecl
= gimple_call_fndecl (stmt
);
872 int flags
= gimple_call_flags (stmt
);
873 if ((flags
& ECF_CONST
)
874 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
875 /* We can only vectorize some builtins at the moment,
876 so restrict if-conversion to those. */
877 && DECL_BUILT_IN (fndecl
))
884 /* Don't know what to do with 'em so don't do anything. */
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 fprintf (dump_file
, "don't know what to do\n");
888 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
897 /* Assumes that BB has more than 1 predecessors.
898 Returns false if at least one successor is not on critical edge
899 and true otherwise. */
902 all_preds_critical_p (basic_block bb
)
907 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
908 if (EDGE_COUNT (e
->src
->succs
) == 1)
913 /* Returns true if at least one successor in on critical edge. */
915 has_pred_critical_p (basic_block bb
)
920 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
921 if (EDGE_COUNT (e
->src
->succs
) > 1)
926 /* Return true when BB is if-convertible. This routine does not check
927 basic block's statements and phis.
929 A basic block is not if-convertible if:
930 - it is non-empty and it is after the exit block (in BFS order),
931 - it is after the exit block but before the latch,
932 - its edges are not normal.
934 Last restriction is valid if aggressive_if_conv is false.
936 EXIT_BB is the basic block containing the exit of the LOOP. BB is
940 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
948 if (EDGE_COUNT (bb
->succs
) > 2)
951 if (EDGE_COUNT (bb
->preds
) > 2
952 && !aggressive_if_conv
)
957 if (bb
!= loop
->latch
)
959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
960 fprintf (dump_file
, "basic block after exit bb but before latch\n");
963 else if (!empty_block_p (bb
))
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "non empty basic block after exit bb\n");
969 else if (bb
== loop
->latch
971 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
974 fprintf (dump_file
, "latch is not dominated by exit_block\n");
979 /* Be less adventurous and handle only normal edges. */
980 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
981 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
984 fprintf (dump_file
, "Difficult to handle edges\n");
988 /* At least one incoming edge has to be non-critical as otherwise edge
989 predicates are not equal to basic-block predicates of the edge
990 source. This check is skipped if aggressive_if_conv is true. */
991 if (!aggressive_if_conv
992 && EDGE_COUNT (bb
->preds
) > 1
993 && bb
!= loop
->header
994 && all_preds_critical_p (bb
))
996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
997 fprintf (dump_file
, "only critical predecessors\n");
1004 /* Return true when all predecessor blocks of BB are visited. The
1005 VISITED bitmap keeps track of the visited blocks. */
1008 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1012 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1013 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1019 /* Get body of a LOOP in suitable order for if-conversion. It is
1020 caller's responsibility to deallocate basic block list.
1021 If-conversion suitable order is, breadth first sort (BFS) order
1022 with an additional constraint: select a block only if all its
1023 predecessors are already selected. */
1025 static basic_block
*
1026 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1028 basic_block
*blocks
, *blocks_in_bfs_order
;
1031 unsigned int index
= 0;
1032 unsigned int visited_count
= 0;
1034 gcc_assert (loop
->num_nodes
);
1035 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1037 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1038 visited
= BITMAP_ALLOC (NULL
);
1040 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1043 while (index
< loop
->num_nodes
)
1045 bb
= blocks_in_bfs_order
[index
];
1047 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1049 free (blocks_in_bfs_order
);
1050 BITMAP_FREE (visited
);
1055 if (!bitmap_bit_p (visited
, bb
->index
))
1057 if (pred_blocks_visited_p (bb
, &visited
)
1058 || bb
== loop
->header
)
1060 /* This block is now visited. */
1061 bitmap_set_bit (visited
, bb
->index
);
1062 blocks
[visited_count
++] = bb
;
1068 if (index
== loop
->num_nodes
1069 && visited_count
!= loop
->num_nodes
)
1073 free (blocks_in_bfs_order
);
1074 BITMAP_FREE (visited
);
1078 /* Returns true when the analysis of the predicates for all the basic
1079 blocks in LOOP succeeded.
1081 predicate_bbs first allocates the predicates of the basic blocks.
1082 These fields are then initialized with the tree expressions
1083 representing the predicates under which a basic block is executed
1084 in the LOOP. As the loop->header is executed at each iteration, it
1085 has the "true" predicate. Other statements executed under a
1086 condition are predicated with that condition, for example
1093 S1 will be predicated with "x", and
1094 S2 will be predicated with "!x". */
1097 predicate_bbs (loop_p loop
)
1101 for (i
= 0; i
< loop
->num_nodes
; i
++)
1102 init_bb_predicate (ifc_bbs
[i
]);
1104 for (i
= 0; i
< loop
->num_nodes
; i
++)
1106 basic_block bb
= ifc_bbs
[i
];
1110 /* The loop latch and loop exit block are always executed and
1111 have no extra conditions to be processed: skip them. */
1112 if (bb
== loop
->latch
1113 || bb_with_exit_edge_p (loop
, bb
))
1115 reset_bb_predicate (bb
);
1119 cond
= bb_predicate (bb
);
1120 stmt
= last_stmt (bb
);
1121 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1124 edge true_edge
, false_edge
;
1125 location_t loc
= gimple_location (stmt
);
1126 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1128 gimple_cond_lhs (stmt
),
1129 gimple_cond_rhs (stmt
));
1131 /* Add new condition into destination's predicate list. */
1132 extract_true_false_edges_from_block (gimple_bb (stmt
),
1133 &true_edge
, &false_edge
);
1135 /* If C is true, then TRUE_EDGE is taken. */
1136 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1139 /* If C is false, then FALSE_EDGE is taken. */
1140 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1142 add_to_dst_predicate_list (loop
, false_edge
,
1143 unshare_expr (cond
), c2
);
1148 /* If current bb has only one successor, then consider it as an
1149 unconditional goto. */
1150 if (single_succ_p (bb
))
1152 basic_block bb_n
= single_succ (bb
);
1154 /* The successor bb inherits the predicate of its
1155 predecessor. If there is no predicate in the predecessor
1156 bb, then consider the successor bb as always executed. */
1157 if (cond
== NULL_TREE
)
1158 cond
= boolean_true_node
;
1160 add_to_predicate_list (loop
, bb_n
, cond
);
1164 /* The loop header is always executed. */
1165 reset_bb_predicate (loop
->header
);
1166 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1167 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1170 /* Return true when LOOP is if-convertible. This is a helper function
1171 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1172 in if_convertible_loop_p. */
1175 if_convertible_loop_p_1 (struct loop
*loop
,
1176 vec
<loop_p
> *loop_nest
,
1177 vec
<data_reference_p
> *refs
,
1178 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1182 basic_block exit_bb
= NULL
;
1184 /* Don't if-convert the loop when the data dependences cannot be
1185 computed: the loop won't be vectorized in that case. */
1186 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1190 calculate_dominance_info (CDI_DOMINATORS
);
1191 calculate_dominance_info (CDI_POST_DOMINATORS
);
1193 /* Allow statements that can be handled during if-conversion. */
1194 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1198 fprintf (dump_file
, "Irreducible loop\n");
1202 for (i
= 0; i
< loop
->num_nodes
; i
++)
1204 basic_block bb
= ifc_bbs
[i
];
1206 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1209 if (bb_with_exit_edge_p (loop
, bb
))
1213 for (i
= 0; i
< loop
->num_nodes
; i
++)
1215 basic_block bb
= ifc_bbs
[i
];
1216 gimple_stmt_iterator gsi
;
1218 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1219 switch (gimple_code (gsi_stmt (gsi
)))
1226 gimple_set_uid (gsi_stmt (gsi
), 0);
1233 data_reference_p dr
;
1235 ref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1236 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1238 predicate_bbs (loop
);
1240 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1242 dr
->aux
= XNEW (struct ifc_dr
);
1243 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1244 DR_RW_UNCONDITIONALLY (dr
) = false;
1245 DR_W_UNCONDITIONALLY (dr
) = false;
1246 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1247 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1248 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1249 if (gimple_uid (DR_STMT (dr
)) == 0)
1250 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1251 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1254 for (i
= 0; i
< loop
->num_nodes
; i
++)
1256 basic_block bb
= ifc_bbs
[i
];
1257 gimple_stmt_iterator itr
;
1259 /* Check the if-convertibility of statements in predicated BBs. */
1260 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1261 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1262 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1263 any_mask_load_store
))
1267 for (i
= 0; i
< loop
->num_nodes
; i
++)
1268 free_bb_predicate (ifc_bbs
[i
]);
1270 /* Checking PHIs needs to be done after stmts, as the fact whether there
1271 are any masked loads or stores affects the tests. */
1272 for (i
= 0; i
< loop
->num_nodes
; i
++)
1274 basic_block bb
= ifc_bbs
[i
];
1277 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1278 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1279 *any_mask_load_store
))
1284 fprintf (dump_file
, "Applying if-conversion\n");
1289 /* Return true when LOOP is if-convertible.
1290 LOOP is if-convertible if:
1292 - it has two or more basic blocks,
1293 - it has only one exit,
1294 - loop header is not the exit edge,
1295 - if its basic blocks and phi nodes are if convertible. */
1298 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1303 vec
<data_reference_p
> refs
;
1306 /* Handle only innermost loop. */
1307 if (!loop
|| loop
->inner
)
1309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1310 fprintf (dump_file
, "not innermost loop\n");
1314 /* If only one block, no need for if-conversion. */
1315 if (loop
->num_nodes
<= 2)
1317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1318 fprintf (dump_file
, "less than 2 basic blocks\n");
1322 /* More than one loop exit is too much to handle. */
1323 if (!single_exit (loop
))
1325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1326 fprintf (dump_file
, "multiple exits\n");
1330 /* If one of the loop header's edge is an exit edge then do not
1331 apply if-conversion. */
1332 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1333 if (loop_exit_edge_p (loop
, e
))
1338 auto_vec
<loop_p
, 3> loop_nest
;
1339 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1340 any_mask_load_store
);
1342 data_reference_p dr
;
1344 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1347 free_data_refs (refs
);
1348 free_dependence_relations (ddrs
);
1353 delete baseref_DR_map
;
1354 baseref_DR_map
= NULL
;
1359 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1360 which is in predicated basic block.
1361 In fact, the following PHI pattern is searching:
1363 reduc_1 = PHI <..., reduc_2>
1367 reduc_2 = PHI <reduc_1, reduc_3>
1369 ARG_0 and ARG_1 are correspondent PHI arguments.
1370 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1371 EXTENDED is true if PHI has > 2 arguments. */
1374 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1375 tree
*op0
, tree
*op1
, bool extended
)
1377 tree lhs
, r_op1
, r_op2
;
1379 gimple
*header_phi
= NULL
;
1380 enum tree_code reduction_op
;
1381 basic_block bb
= gimple_bb (phi
);
1382 struct loop
*loop
= bb
->loop_father
;
1383 edge latch_e
= loop_latch_edge (loop
);
1384 imm_use_iterator imm_iter
;
1385 use_operand_p use_p
;
1388 bool result
= false;
1389 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1392 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1395 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1396 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1398 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1401 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1402 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1406 if (gimple_bb (header_phi
) != loop
->header
)
1409 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1412 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1413 || gimple_has_volatile_ops (stmt
))
1416 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1419 if (!is_predicated (gimple_bb (stmt
)))
1422 /* Check that stmt-block is predecessor of phi-block. */
1423 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1432 if (!has_single_use (lhs
))
1435 reduction_op
= gimple_assign_rhs_code (stmt
);
1436 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1438 r_op1
= gimple_assign_rhs1 (stmt
);
1439 r_op2
= gimple_assign_rhs2 (stmt
);
1441 /* Make R_OP1 to hold reduction variable. */
1442 if (r_op2
== PHI_RESULT (header_phi
)
1443 && reduction_op
== PLUS_EXPR
)
1444 std::swap (r_op1
, r_op2
);
1445 else if (r_op1
!= PHI_RESULT (header_phi
))
1448 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1449 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1451 gimple
*use_stmt
= USE_STMT (use_p
);
1452 if (is_gimple_debug (use_stmt
))
1454 if (use_stmt
== stmt
)
1456 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1460 *op0
= r_op1
; *op1
= r_op2
;
1465 /* Converts conditional scalar reduction into unconditional form, e.g.
1467 if (_5 != 0) goto bb_5 else goto bb_6
1473 # res_2 = PHI <res_13(4), res_6(5)>
1476 will be converted into sequence
1477 _ifc__1 = _5 != 0 ? 1 : 0;
1478 res_2 = res_13 + _ifc__1;
1479 Argument SWAP tells that arguments of conditional expression should be
1481 Returns rhs of resulting PHI assignment. */
1484 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1485 tree cond
, tree op0
, tree op1
, bool swap
)
1487 gimple_stmt_iterator stmt_it
;
1490 tree rhs1
= gimple_assign_rhs1 (reduc
);
1491 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1493 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1495 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1497 fprintf (dump_file
, "Found cond scalar reduction.\n");
1498 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1501 /* Build cond expression using COND and constant operand
1502 of reduction rhs. */
1503 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1504 unshare_expr (cond
),
1508 /* Create assignment stmt and insert it at GSI. */
1509 new_assign
= gimple_build_assign (tmp
, c
);
1510 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1511 /* Build rhs for unconditional increment/decrement. */
1512 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1513 TREE_TYPE (rhs1
), op0
, tmp
);
1515 /* Delete original reduction stmt. */
1516 stmt_it
= gsi_for_stmt (reduc
);
1517 gsi_remove (&stmt_it
, true);
1518 release_defs (reduc
);
1522 /* Produce condition for all occurrences of ARG in PHI node. */
1525 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1526 gimple_stmt_iterator
*gsi
)
1530 tree cond
= NULL_TREE
;
1534 len
= occur
->length ();
1535 gcc_assert (len
> 0);
1536 for (i
= 0; i
< len
; i
++)
1538 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1539 c
= bb_predicate (e
->src
);
1540 if (is_true_predicate (c
))
1542 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1543 is_gimple_condexpr
, NULL_TREE
,
1544 true, GSI_SAME_STMT
);
1545 if (cond
!= NULL_TREE
)
1547 /* Must build OR expression. */
1548 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1549 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1550 is_gimple_condexpr
, NULL_TREE
,
1551 true, GSI_SAME_STMT
);
1556 gcc_assert (cond
!= NULL_TREE
);
1560 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1561 This routine can handle PHI nodes with more than two arguments.
1564 S1: A = PHI <x1(1), x2(5)>
1566 S2: A = cond ? x1 : x2;
1568 The generated code is inserted at GSI that points to the top of
1569 basic block's statement list.
1570 If PHI node has more than two arguments a chain of conditional
1571 expression is produced. */
1575 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1577 gimple
*new_stmt
= NULL
, *reduc
;
1578 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1580 unsigned int index0
;
1581 unsigned int max
, args_len
;
1586 res
= gimple_phi_result (phi
);
1587 if (virtual_operand_p (res
))
1590 if ((rhs
= degenerate_phi_result (phi
))
1591 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1593 && !chrec_contains_undetermined (scev
)
1595 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1599 fprintf (dump_file
, "Degenerate phi!\n");
1600 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1602 new_stmt
= gimple_build_assign (res
, rhs
);
1603 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1604 update_stmt (new_stmt
);
1608 bb
= gimple_bb (phi
);
1609 if (EDGE_COUNT (bb
->preds
) == 2)
1611 /* Predicate ordinary PHI node with 2 arguments. */
1612 edge first_edge
, second_edge
;
1613 basic_block true_bb
;
1614 first_edge
= EDGE_PRED (bb
, 0);
1615 second_edge
= EDGE_PRED (bb
, 1);
1616 cond
= bb_predicate (first_edge
->src
);
1617 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1618 std::swap (first_edge
, second_edge
);
1619 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1621 cond
= bb_predicate (second_edge
->src
);
1622 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1623 cond
= TREE_OPERAND (cond
, 0);
1625 first_edge
= second_edge
;
1628 cond
= bb_predicate (first_edge
->src
);
1629 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1630 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1631 is_gimple_condexpr
, NULL_TREE
,
1632 true, GSI_SAME_STMT
);
1633 true_bb
= first_edge
->src
;
1634 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1636 arg0
= gimple_phi_arg_def (phi
, 1);
1637 arg1
= gimple_phi_arg_def (phi
, 0);
1641 arg0
= gimple_phi_arg_def (phi
, 0);
1642 arg1
= gimple_phi_arg_def (phi
, 1);
1644 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1646 /* Convert reduction stmt into vectorizable form. */
1647 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1648 true_bb
!= gimple_bb (reduc
));
1650 /* Build new RHS using selected condition and arguments. */
1651 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1653 new_stmt
= gimple_build_assign (res
, rhs
);
1654 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1655 update_stmt (new_stmt
);
1657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1659 fprintf (dump_file
, "new phi replacement stmt\n");
1660 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1665 /* Create hashmap for PHI node which contain vector of argument indexes
1666 having the same value. */
1668 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1669 unsigned int num_args
= gimple_phi_num_args (phi
);
1671 /* Vector of different PHI argument values. */
1672 auto_vec
<tree
> args (num_args
);
1674 /* Compute phi_arg_map. */
1675 for (i
= 0; i
< num_args
; i
++)
1679 arg
= gimple_phi_arg_def (phi
, i
);
1680 if (!phi_arg_map
.get (arg
))
1681 args
.quick_push (arg
);
1682 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1685 /* Determine element with max number of occurrences. */
1688 args_len
= args
.length ();
1689 for (i
= 0; i
< args_len
; i
++)
1692 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1699 /* Put element with max number of occurences to the end of ARGS. */
1700 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1701 std::swap (args
[args_len
- 1], args
[max_ind
]);
1703 /* Handle one special case when number of arguments with different values
1704 is equal 2 and one argument has the only occurrence. Such PHI can be
1705 handled as if would have only 2 arguments. */
1706 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1709 indexes
= phi_arg_map
.get (args
[0]);
1710 index0
= (*indexes
)[0];
1713 e
= gimple_phi_arg_edge (phi
, index0
);
1714 cond
= bb_predicate (e
->src
);
1715 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1718 cond
= TREE_OPERAND (cond
, 0);
1720 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1721 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1722 is_gimple_condexpr
, NULL_TREE
,
1723 true, GSI_SAME_STMT
);
1724 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1726 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1730 /* Convert reduction stmt into vectorizable form. */
1731 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1733 new_stmt
= gimple_build_assign (res
, rhs
);
1734 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1735 update_stmt (new_stmt
);
1741 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1744 for (i
= 0; i
< args_len
; i
++)
1747 indexes
= phi_arg_map
.get (args
[i
]);
1748 if (i
!= args_len
- 1)
1749 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1752 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1753 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1755 new_stmt
= gimple_build_assign (lhs
, rhs
);
1756 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1757 update_stmt (new_stmt
);
1762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1764 fprintf (dump_file
, "new extended phi replacement stmt\n");
1765 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1769 /* Replaces in LOOP all the scalar phi nodes other than those in the
1770 LOOP->header block with conditional modify expressions. */
1773 predicate_all_scalar_phis (struct loop
*loop
)
1776 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1779 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1782 gimple_stmt_iterator gsi
;
1783 gphi_iterator phi_gsi
;
1786 if (bb
== loop
->header
)
1789 if (EDGE_COUNT (bb
->preds
) == 1)
1792 phi_gsi
= gsi_start_phis (bb
);
1793 if (gsi_end_p (phi_gsi
))
1796 gsi
= gsi_after_labels (bb
);
1797 while (!gsi_end_p (phi_gsi
))
1799 phi
= phi_gsi
.phi ();
1800 predicate_scalar_phi (phi
, &gsi
);
1801 release_phi_node (phi
);
1802 gsi_next (&phi_gsi
);
1805 set_phi_nodes (bb
, NULL
);
1809 /* Insert in each basic block of LOOP the statements produced by the
1810 gimplification of the predicates. */
1813 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1817 for (i
= 0; i
< loop
->num_nodes
; i
++)
1819 basic_block bb
= ifc_bbs
[i
];
1821 if (!is_predicated (bb
))
1822 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1823 if (!is_predicated (bb
))
1825 /* Do not insert statements for a basic block that is not
1826 predicated. Also make sure that the predicate of the
1827 basic block is set to true. */
1828 reset_bb_predicate (bb
);
1832 stmts
= bb_predicate_gimplified_stmts (bb
);
1835 if (any_mask_load_store
)
1837 /* Insert the predicate of the BB just after the label,
1838 as the if-conversion of memory writes will use this
1840 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1841 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1845 /* Insert the predicate of the BB at the end of the BB
1846 as this would reduce the register pressure: the only
1847 use of this predicate will be in successor BBs. */
1848 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1851 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1852 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1854 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1857 /* Once the sequence is code generated, set it to NULL. */
1858 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1863 /* Helper function for predicate_mem_writes. Returns index of existent
1864 mask if it was created for given SIZE and -1 otherwise. */
1867 mask_exists (int size
, vec
<int> vec
)
1871 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1877 /* Predicate each write to memory in LOOP.
1879 This function transforms control flow constructs containing memory
1882 | for (i = 0; i < N; i++)
1886 into the following form that does not contain control flow:
1888 | for (i = 0; i < N; i++)
1889 | A[i] = cond ? expr : A[i];
1891 The original CFG looks like this:
1898 | if (i < N) goto bb_5 else goto bb_2
1902 | cond = some_computation;
1903 | if (cond) goto bb_3 else goto bb_4
1915 insert_gimplified_predicates inserts the computation of the COND
1916 expression at the beginning of the destination basic block:
1923 | if (i < N) goto bb_5 else goto bb_2
1927 | cond = some_computation;
1928 | if (cond) goto bb_3 else goto bb_4
1932 | cond = some_computation;
1941 predicate_mem_writes is then predicating the memory write as follows:
1948 | if (i < N) goto bb_5 else goto bb_2
1952 | if (cond) goto bb_3 else goto bb_4
1956 | cond = some_computation;
1957 | A[i] = cond ? expr : A[i];
1965 and finally combine_blocks removes the basic block boundaries making
1966 the loop vectorizable:
1970 | if (i < N) goto bb_5 else goto bb_1
1974 | cond = some_computation;
1975 | A[i] = cond ? expr : A[i];
1976 | if (i < N) goto bb_5 else goto bb_4
1985 predicate_mem_writes (loop_p loop
)
1987 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1988 auto_vec
<int, 1> vect_sizes
;
1989 auto_vec
<tree
, 1> vect_masks
;
1991 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1993 gimple_stmt_iterator gsi
;
1994 basic_block bb
= ifc_bbs
[i
];
1995 tree cond
= bb_predicate (bb
);
2000 if (is_true_predicate (cond
))
2004 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2007 cond
= TREE_OPERAND (cond
, 0);
2010 vect_sizes
.truncate (0);
2011 vect_masks
.truncate (0);
2013 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2014 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2016 else if (gimple_plf (stmt
, GF_PLF_2
))
2018 tree lhs
= gimple_assign_lhs (stmt
);
2019 tree rhs
= gimple_assign_rhs1 (stmt
);
2020 tree ref
, addr
, ptr
, mask
;
2022 gimple_seq stmts
= NULL
;
2023 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2024 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2025 mark_addressable (ref
);
2026 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2027 true, NULL_TREE
, true,
2029 if (!vect_sizes
.is_empty ()
2030 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2031 /* Use created mask. */
2032 mask
= vect_masks
[index
];
2035 if (COMPARISON_CLASS_P (cond
))
2036 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2038 TREE_OPERAND (cond
, 0),
2039 TREE_OPERAND (cond
, 1));
2042 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2049 = constant_boolean_node (true, TREE_TYPE (mask
));
2050 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2051 TREE_TYPE (mask
), mask
, true_val
);
2053 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2055 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2056 /* Save mask and its size for further use. */
2057 vect_sizes
.safe_push (bitsize
);
2058 vect_masks
.safe_push (mask
);
2060 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2061 get_object_alignment (ref
));
2062 /* Copy points-to info if possible. */
2063 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2064 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2066 if (TREE_CODE (lhs
) == SSA_NAME
)
2069 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2071 gimple_call_set_lhs (new_stmt
, lhs
);
2075 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2077 gsi_replace (&gsi
, new_stmt
, true);
2079 else if (gimple_vdef (stmt
))
2081 tree lhs
= gimple_assign_lhs (stmt
);
2082 tree rhs
= gimple_assign_rhs1 (stmt
);
2083 tree type
= TREE_TYPE (lhs
);
2085 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2086 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2088 std::swap (lhs
, rhs
);
2089 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2090 is_gimple_condexpr
, NULL_TREE
,
2091 true, GSI_SAME_STMT
);
2092 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2093 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2099 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2100 other than the exit and latch of the LOOP. Also resets the
2101 GIMPLE_DEBUG information. */
2104 remove_conditions_and_labels (loop_p loop
)
2106 gimple_stmt_iterator gsi
;
2109 for (i
= 0; i
< loop
->num_nodes
; i
++)
2111 basic_block bb
= ifc_bbs
[i
];
2113 if (bb_with_exit_edge_p (loop
, bb
)
2114 || bb
== loop
->latch
)
2117 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2118 switch (gimple_code (gsi_stmt (gsi
)))
2122 gsi_remove (&gsi
, true);
2126 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2127 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2129 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2130 update_stmt (gsi_stmt (gsi
));
2141 /* Combine all the basic blocks from LOOP into one or two super basic
2142 blocks. Replace PHI nodes with conditional modify expressions. */
2145 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2147 basic_block bb
, exit_bb
, merge_target_bb
;
2148 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2153 predicate_bbs (loop
);
2154 remove_conditions_and_labels (loop
);
2155 insert_gimplified_predicates (loop
, any_mask_load_store
);
2156 predicate_all_scalar_phis (loop
);
2158 if (any_mask_load_store
)
2159 predicate_mem_writes (loop
);
2161 /* Merge basic blocks: first remove all the edges in the loop,
2162 except for those from the exit block. */
2164 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2165 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2168 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2169 free_bb_predicate (bb
);
2170 if (bb_with_exit_edge_p (loop
, bb
))
2172 gcc_assert (exit_bb
== NULL
);
2176 gcc_assert (exit_bb
!= loop
->latch
);
2178 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2182 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2184 if (e
->src
== exit_bb
)
2191 if (exit_bb
!= NULL
)
2193 if (exit_bb
!= loop
->header
)
2195 /* Connect this node to loop header. */
2196 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2197 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2200 /* Redirect non-exit edges to loop->latch. */
2201 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2203 if (!loop_exit_edge_p (loop
, e
))
2204 redirect_edge_and_branch (e
, loop
->latch
);
2206 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2210 /* If the loop does not have an exit, reconnect header and latch. */
2211 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2212 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2215 merge_target_bb
= loop
->header
;
2216 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2218 gimple_stmt_iterator gsi
;
2219 gimple_stmt_iterator last
;
2223 if (bb
== exit_bb
|| bb
== loop
->latch
)
2226 /* Make stmts member of loop->header and clear range info from all stmts
2227 in BB which is now no longer executed conditional on a predicate we
2228 could have derived it from. */
2229 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2231 gimple
*stmt
= gsi_stmt (gsi
);
2232 gimple_set_bb (stmt
, merge_target_bb
);
2237 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2238 reset_flow_sensitive_info (op
);
2242 /* Update stmt list. */
2243 last
= gsi_last_bb (merge_target_bb
);
2244 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2245 set_bb_seq (bb
, NULL
);
2247 delete_basic_block (bb
);
2250 /* If possible, merge loop header to the block with the exit edge.
2251 This reduces the number of basic blocks to two, to please the
2252 vectorizer that handles only loops with two nodes. */
2254 && exit_bb
!= loop
->header
2255 && can_merge_blocks_p (loop
->header
, exit_bb
))
2256 merge_blocks (loop
->header
, exit_bb
);
2263 /* Version LOOP before if-converting it; the original loop
2264 will be if-converted, the new copy of the loop will not,
2265 and the LOOP_VECTORIZED internal call will be guarding which
2266 loop to execute. The vectorizer pass will fold this
2267 internal call into either true or false. */
2270 version_loop_for_if_conversion (struct loop
*loop
)
2272 basic_block cond_bb
;
2273 tree cond
= make_ssa_name (boolean_type_node
);
2274 struct loop
*new_loop
;
2276 gimple_stmt_iterator gsi
;
2278 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2279 build_int_cst (integer_type_node
, loop
->num
),
2281 gimple_call_set_lhs (g
, cond
);
2283 initialize_original_copy_tables ();
2284 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2285 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2286 REG_BR_PROB_BASE
, true);
2287 free_original_copy_tables ();
2288 if (new_loop
== NULL
)
2290 new_loop
->dont_vectorize
= true;
2291 new_loop
->force_vectorize
= false;
2292 gsi
= gsi_last_bb (cond_bb
);
2293 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2294 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2295 update_ssa (TODO_update_ssa
);
2299 /* Performs splitting of critical edges if aggressive_if_conv is true.
2300 Returns false if loop won't be if converted and true otherwise. */
2303 ifcvt_split_critical_edges (struct loop
*loop
)
2307 unsigned int num
= loop
->num_nodes
;
2317 if (!single_exit (loop
))
2320 body
= get_loop_body (loop
);
2321 for (i
= 0; i
< num
; i
++)
2324 if (bb
== loop
->latch
2325 || bb_with_exit_edge_p (loop
, bb
))
2327 stmt
= last_stmt (bb
);
2328 /* Skip basic blocks not ending with conditional branch. */
2329 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2331 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2332 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2339 /* Assumes that lhs of DEF_STMT have multiple uses.
2340 Delete one use by (1) creation of copy DEF_STMT with
2341 unique lhs; (2) change original use of lhs in one
2342 use statement with newly created lhs. */
2345 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2350 gimple_stmt_iterator gsi
;
2351 use_operand_p use_p
;
2352 imm_use_iterator imm_iter
;
2354 var
= gimple_assign_lhs (def_stmt
);
2355 copy_stmt
= gimple_copy (def_stmt
);
2356 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2357 gimple_assign_set_lhs (copy_stmt
, lhs
);
2358 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2359 /* Insert copy of DEF_STMT. */
2360 gsi
= gsi_for_stmt (def_stmt
);
2361 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2362 /* Change use of var to lhs in use_stmt. */
2363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2365 fprintf (dump_file
, "Change use of var ");
2366 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2367 fprintf (dump_file
, " to ");
2368 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2369 fprintf (dump_file
, "\n");
2371 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2373 if (USE_STMT (use_p
) != use_stmt
)
2375 SET_USE (use_p
, lhs
);
2380 /* Traverse bool pattern recursively starting from VAR.
2381 Save its def and use statements to defuse_list if VAR does
2382 not have single use. */
2385 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2389 enum tree_code code
;
2392 def_stmt
= SSA_NAME_DEF_STMT (var
);
2393 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2395 if (!has_single_use (var
))
2397 /* Put def and use stmts into defuse_list. */
2398 defuse_list
->safe_push (def_stmt
);
2399 defuse_list
->safe_push (use_stmt
);
2400 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2402 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2403 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2406 rhs1
= gimple_assign_rhs1 (def_stmt
);
2407 code
= gimple_assign_rhs_code (def_stmt
);
2411 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2414 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2415 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2416 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2418 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2421 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2426 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2427 rhs2
= gimple_assign_rhs2 (def_stmt
);
2428 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2436 /* Returns true if STMT can be a root of bool pattern applied
2440 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2442 enum tree_code code
;
2445 code
= gimple_assign_rhs_code (stmt
);
2446 if (CONVERT_EXPR_CODE_P (code
))
2448 lhs
= gimple_assign_lhs (stmt
);
2449 rhs
= gimple_assign_rhs1 (stmt
);
2450 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2452 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2456 else if (code
== COND_EXPR
)
2458 rhs
= gimple_assign_rhs1 (stmt
);
2459 if (TREE_CODE (rhs
) != SSA_NAME
)
2466 /* Traverse all statements in BB which correspond to loop header to
2467 find out all statements which can start bool pattern applied by
2468 vectorizer and convert multiple uses in it to conform pattern
2469 restrictions. Such case can occur if the same predicate is used both
2470 for phi node conversion and load/store mask. */
2473 ifcvt_repair_bool_pattern (basic_block bb
)
2477 gimple_stmt_iterator gsi
;
2478 vec
<gimple
*> defuse_list
= vNULL
;
2479 vec
<gimple
*> pattern_roots
= vNULL
;
2484 /* Collect all root pattern statements. */
2485 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2487 stmt
= gsi_stmt (gsi
);
2488 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2490 if (!stmt_is_root_of_bool_pattern (stmt
))
2492 pattern_roots
.safe_push (stmt
);
2495 if (pattern_roots
.is_empty ())
2498 /* Split all statements with multiple uses iteratively since splitting
2499 may create new multiple uses. */
2504 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2506 rhs
= gimple_assign_rhs1 (stmt
);
2507 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2508 while (defuse_list
.length () > 0)
2511 gimple
*def_stmt
, *use_stmt
;
2512 use_stmt
= defuse_list
.pop ();
2513 def_stmt
= defuse_list
.pop ();
2514 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2520 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2524 /* Delete redundant statements produced by predication which prevents
2525 loop vectorization. */
2528 ifcvt_local_dce (basic_block bb
)
2533 gimple_stmt_iterator gsi
;
2534 auto_vec
<gimple
*> worklist
;
2535 enum gimple_code code
;
2536 use_operand_p use_p
;
2537 imm_use_iterator imm_iter
;
2539 worklist
.create (64);
2540 /* Consider all phi as live statements. */
2541 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2543 phi
= gsi_stmt (gsi
);
2544 gimple_set_plf (phi
, GF_PLF_2
, true);
2545 worklist
.safe_push (phi
);
2547 /* Consider load/store statements, CALL and COND as live. */
2548 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2550 stmt
= gsi_stmt (gsi
);
2551 if (gimple_store_p (stmt
)
2552 || gimple_assign_load_p (stmt
)
2553 || is_gimple_debug (stmt
))
2555 gimple_set_plf (stmt
, GF_PLF_2
, true);
2556 worklist
.safe_push (stmt
);
2559 code
= gimple_code (stmt
);
2560 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2562 gimple_set_plf (stmt
, GF_PLF_2
, true);
2563 worklist
.safe_push (stmt
);
2566 gimple_set_plf (stmt
, GF_PLF_2
, false);
2568 if (code
== GIMPLE_ASSIGN
)
2570 tree lhs
= gimple_assign_lhs (stmt
);
2571 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2573 stmt1
= USE_STMT (use_p
);
2574 if (gimple_bb (stmt1
) != bb
)
2576 gimple_set_plf (stmt
, GF_PLF_2
, true);
2577 worklist
.safe_push (stmt
);
2583 /* Propagate liveness through arguments of live stmt. */
2584 while (worklist
.length () > 0)
2587 use_operand_p use_p
;
2590 stmt
= worklist
.pop ();
2591 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2593 use
= USE_FROM_PTR (use_p
);
2594 if (TREE_CODE (use
) != SSA_NAME
)
2596 stmt1
= SSA_NAME_DEF_STMT (use
);
2597 if (gimple_bb (stmt1
) != bb
2598 || gimple_plf (stmt1
, GF_PLF_2
))
2600 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2601 worklist
.safe_push (stmt1
);
2604 /* Delete dead statements. */
2605 gsi
= gsi_start_bb (bb
);
2606 while (!gsi_end_p (gsi
))
2608 stmt
= gsi_stmt (gsi
);
2609 if (gimple_plf (stmt
, GF_PLF_2
))
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2616 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2617 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2619 gsi_remove (&gsi
, true);
2620 release_defs (stmt
);
2624 /* If-convert LOOP when it is legal. For the moment this pass has no
2625 profitability analysis. Returns non-zero todo flags when something
2629 tree_if_conversion (struct loop
*loop
)
2631 unsigned int todo
= 0;
2633 bool any_mask_load_store
= false;
2635 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2636 aggressive_if_conv
= loop
->force_vectorize
;
2637 /* Check either outer loop was marked with simd pragma. */
2638 if (!aggressive_if_conv
)
2640 struct loop
*outer_loop
= loop_outer (loop
);
2641 if (outer_loop
&& outer_loop
->force_vectorize
)
2642 aggressive_if_conv
= true;
2645 if (aggressive_if_conv
)
2646 if (!ifcvt_split_critical_edges (loop
))
2649 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2650 || !dbg_cnt (if_conversion_tree
))
2653 if (any_mask_load_store
2654 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2655 || loop
->dont_vectorize
))
2658 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2661 /* Now all statements are if-convertible. Combine all the basic
2662 blocks into one huge basic block doing the if-conversion
2664 combine_blocks (loop
, any_mask_load_store
);
2666 /* Delete dead predicate computations and repair tree correspondent
2667 to bool pattern to delete multiple uses of predicates. */
2668 if (aggressive_if_conv
)
2670 ifcvt_local_dce (loop
->header
);
2671 ifcvt_repair_bool_pattern (loop
->header
);
2674 todo
|= TODO_cleanup_cfg
;
2675 if (any_mask_load_store
)
2677 mark_virtual_operands_for_renaming (cfun
);
2678 todo
|= TODO_update_ssa_only_virtuals
;
2686 for (i
= 0; i
< loop
->num_nodes
; i
++)
2687 free_bb_predicate (ifc_bbs
[i
]);
2692 free_dominance_info (CDI_POST_DOMINATORS
);
2697 /* Tree if-conversion pass management. */
2701 const pass_data pass_data_if_conversion
=
2703 GIMPLE_PASS
, /* type */
2705 OPTGROUP_NONE
, /* optinfo_flags */
2706 TV_NONE
, /* tv_id */
2707 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2708 0, /* properties_provided */
2709 0, /* properties_destroyed */
2710 0, /* todo_flags_start */
2711 0, /* todo_flags_finish */
2714 class pass_if_conversion
: public gimple_opt_pass
2717 pass_if_conversion (gcc::context
*ctxt
)
2718 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2721 /* opt_pass methods: */
2722 virtual bool gate (function
*);
2723 virtual unsigned int execute (function
*);
2725 }; // class pass_if_conversion
2728 pass_if_conversion::gate (function
*fun
)
2730 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2731 && flag_tree_loop_if_convert
!= 0)
2732 || flag_tree_loop_if_convert
== 1
2733 || flag_tree_loop_if_convert_stores
== 1);
2737 pass_if_conversion::execute (function
*fun
)
2742 if (number_of_loops (fun
) <= 1)
2745 FOR_EACH_LOOP (loop
, 0)
2746 if (flag_tree_loop_if_convert
== 1
2747 || flag_tree_loop_if_convert_stores
== 1
2748 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2749 && !loop
->dont_vectorize
))
2750 todo
|= tree_if_conversion (loop
);
2755 FOR_EACH_BB_FN (bb
, fun
)
2756 gcc_assert (!bb
->aux
);
2765 make_pass_if_conversion (gcc::context
*ctxt
)
2767 return new pass_if_conversion (ctxt
);