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"
115 /* List of basic blocks in if-conversion-suitable order. */
116 static basic_block
*ifc_bbs
;
118 /* Apply more aggressive (extended) if-conversion if true. */
119 static bool aggressive_if_conv
;
121 /* Hash table to store references, DR pairs. */
122 static hash_map
<tree_operand_hash
, data_reference_p
> *ref_DR_map
;
124 /* Hash table to store base reference, DR pairs. */
125 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
127 /* Structure used to predicate basic blocks. This is attached to the
128 ->aux field of the BBs in the loop to be if-converted. */
129 struct bb_predicate
{
131 /* The condition under which this basic block is executed. */
134 /* PREDICATE is gimplified, and the sequence of statements is
135 recorded here, in order to avoid the duplication of computations
136 that occur in previous conditions. See PR44483. */
137 gimple_seq predicate_gimplified_stmts
;
140 /* Returns true when the basic block BB has a predicate. */
143 bb_has_predicate (basic_block bb
)
145 return bb
->aux
!= NULL
;
148 /* Returns the gimplified predicate for basic block BB. */
151 bb_predicate (basic_block bb
)
153 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
156 /* Sets the gimplified predicate COND for basic block BB. */
159 set_bb_predicate (basic_block bb
, tree cond
)
161 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
162 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
163 || is_gimple_condexpr (cond
));
164 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
167 /* Returns the sequence of statements of the gimplification of the
168 predicate for basic block BB. */
170 static inline gimple_seq
171 bb_predicate_gimplified_stmts (basic_block bb
)
173 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
176 /* Sets the sequence of statements STMTS of the gimplification of the
177 predicate for basic block BB. */
180 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
182 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
185 /* Adds the sequence of statements STMTS to the sequence of statements
186 of the predicate for basic block BB. */
189 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
192 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
195 /* Initializes to TRUE the predicate of basic block BB. */
198 init_bb_predicate (basic_block bb
)
200 bb
->aux
= XNEW (struct bb_predicate
);
201 set_bb_predicate_gimplified_stmts (bb
, NULL
);
202 set_bb_predicate (bb
, boolean_true_node
);
205 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
206 but don't actually free it. */
209 release_bb_predicate (basic_block bb
)
211 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
214 gimple_stmt_iterator i
;
216 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
217 free_stmt_operands (cfun
, gsi_stmt (i
));
218 set_bb_predicate_gimplified_stmts (bb
, NULL
);
222 /* Free the predicate of basic block BB. */
225 free_bb_predicate (basic_block bb
)
227 if (!bb_has_predicate (bb
))
230 release_bb_predicate (bb
);
235 /* Reinitialize predicate of BB with the true predicate. */
238 reset_bb_predicate (basic_block bb
)
240 if (!bb_has_predicate (bb
))
241 init_bb_predicate (bb
);
244 release_bb_predicate (bb
);
245 set_bb_predicate (bb
, boolean_true_node
);
249 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
250 the expression EXPR. Inserts the statement created for this
251 computation before GSI and leaves the iterator GSI at the same
255 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
257 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
258 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
259 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
263 /* Return true when COND is a true predicate. */
266 is_true_predicate (tree cond
)
268 return (cond
== NULL_TREE
269 || cond
== boolean_true_node
270 || integer_onep (cond
));
273 /* Returns true when BB has a predicate that is not trivial: true or
277 is_predicated (basic_block bb
)
279 return !is_true_predicate (bb_predicate (bb
));
282 /* Parses the predicate COND and returns its comparison code and
283 operands OP0 and OP1. */
285 static enum tree_code
286 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
290 if (TREE_CODE (cond
) == SSA_NAME
291 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
293 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
295 *op0
= gimple_assign_rhs1 (s
);
296 *op1
= gimple_assign_rhs2 (s
);
297 return gimple_assign_rhs_code (s
);
300 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
302 tree op
= gimple_assign_rhs1 (s
);
303 tree type
= TREE_TYPE (op
);
304 enum tree_code code
= parse_predicate (op
, op0
, op1
);
306 return code
== ERROR_MARK
? ERROR_MARK
307 : invert_tree_comparison (code
, HONOR_NANS (type
));
313 if (COMPARISON_CLASS_P (cond
))
315 *op0
= TREE_OPERAND (cond
, 0);
316 *op1
= TREE_OPERAND (cond
, 1);
317 return TREE_CODE (cond
);
323 /* Returns the fold of predicate C1 OR C2 at location LOC. */
326 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
328 tree op1a
, op1b
, op2a
, op2b
;
329 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
330 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
332 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
334 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
340 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
343 /* Returns true if N is either a constant or a SSA_NAME. */
346 constant_or_ssa_name (tree n
)
348 switch (TREE_CODE (n
))
361 /* Returns either a COND_EXPR or the folded expression if the folded
362 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
363 a constant or a SSA_NAME. */
366 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
368 tree rhs1
, lhs1
, cond_expr
;
370 /* If COND is comparison r != 0 and r has boolean type, convert COND
371 to SSA_NAME to accept by vect bool pattern. */
372 if (TREE_CODE (cond
) == NE_EXPR
)
374 tree op0
= TREE_OPERAND (cond
, 0);
375 tree op1
= TREE_OPERAND (cond
, 1);
376 if (TREE_CODE (op0
) == SSA_NAME
377 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
378 && (integer_zerop (op1
)))
381 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
384 if (cond_expr
== NULL_TREE
)
385 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
387 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
389 if (constant_or_ssa_name (cond_expr
))
392 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
394 rhs1
= TREE_OPERAND (cond_expr
, 1);
395 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
396 if (constant_or_ssa_name (rhs1
))
397 return build1 (ABS_EXPR
, type
, rhs1
);
400 if (TREE_CODE (cond_expr
) == MIN_EXPR
401 || TREE_CODE (cond_expr
) == MAX_EXPR
)
403 lhs1
= TREE_OPERAND (cond_expr
, 0);
404 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
405 rhs1
= TREE_OPERAND (cond_expr
, 1);
406 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
407 if (constant_or_ssa_name (rhs1
)
408 && constant_or_ssa_name (lhs1
))
409 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
411 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
414 /* Add condition NC to the predicate list of basic block BB. LOOP is
415 the loop to be if-converted. Use predicate of cd-equivalent block
416 for join bb if it exists: we call basic blocks bb1 and bb2
417 cd-equivalent if they are executed under the same condition. */
420 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
425 if (is_true_predicate (nc
))
428 /* If dominance tells us this basic block is always executed,
429 don't record any predicates for it. */
430 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
433 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
434 /* We use notion of cd equivalence to get simpler predicate for
435 join block, e.g. if join block has 2 predecessors with predicates
436 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
437 p1 & p2 | p1 & !p2. */
438 if (dom_bb
!= loop
->header
439 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
441 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
442 bc
= bb_predicate (dom_bb
);
443 if (!is_true_predicate (bc
))
444 set_bb_predicate (bb
, bc
);
446 gcc_assert (is_true_predicate (bb_predicate (bb
)));
447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
448 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
449 dom_bb
->index
, bb
->index
);
453 if (!is_predicated (bb
))
457 bc
= bb_predicate (bb
);
458 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
459 if (is_true_predicate (bc
))
461 reset_bb_predicate (bb
);
466 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
467 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
468 tp
= &TREE_OPERAND (bc
, 0);
471 if (!is_gimple_condexpr (*tp
))
474 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
475 add_bb_predicate_gimplified_stmts (bb
, stmts
);
477 set_bb_predicate (bb
, bc
);
480 /* Add the condition COND to the previous condition PREV_COND, and add
481 this to the predicate list of the destination of edge E. LOOP is
482 the loop to be if-converted. */
485 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
486 tree prev_cond
, tree cond
)
488 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
491 if (!is_true_predicate (prev_cond
))
492 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
495 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
496 add_to_predicate_list (loop
, e
->dest
, cond
);
499 /* Return true if one of the successor edges of BB exits LOOP. */
502 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
507 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
508 if (loop_exit_edge_p (loop
, e
))
514 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
515 and it belongs to basic block BB.
517 PHI is not if-convertible if:
518 - it has more than 2 arguments.
520 When the flag_tree_loop_if_convert_stores is not set, PHI is not
522 - a virtual PHI is immediately used in another PHI node,
523 - there is a virtual PHI in a BB other than the loop->header.
524 When the aggressive_if_conv is set, PHI can have more than
528 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
529 bool any_mask_load_store
)
531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
533 fprintf (dump_file
, "-------------------------\n");
534 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
537 if (bb
!= loop
->header
)
539 if (gimple_phi_num_args (phi
) != 2
540 && !aggressive_if_conv
)
542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
543 fprintf (dump_file
, "More than two phi node args.\n");
548 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
551 /* When the flag_tree_loop_if_convert_stores is not set, check
552 that there are no memory writes in the branches of the loop to be
554 if (virtual_operand_p (gimple_phi_result (phi
)))
556 imm_use_iterator imm_iter
;
559 if (bb
!= loop
->header
)
561 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
562 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
566 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
568 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
569 && USE_STMT (use_p
) != phi
)
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
572 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
581 /* Records the status of a data reference. This struct is attached to
582 each DR->aux field. */
585 bool rw_unconditionally
;
586 bool w_unconditionally
;
587 bool written_at_least_once
;
591 tree base_w_predicate
;
594 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
595 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
596 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
597 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
599 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
600 HASH tables. While storing them in HASH table, it checks if the
601 reference is unconditionally read or written and stores that as a flag
602 information. For base reference it checks if it is written atlest once
603 unconditionally and stores it as flag information along with DR.
604 In other words for every data reference A in STMT there exist other
605 accesses to a data reference with the same base with predicates that
606 add up (OR-up) to the true predicate: this ensures that the data
607 reference A is touched (read or written) on every iteration of the
608 if-converted loop. */
610 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
613 data_reference_p
*master_dr
, *base_master_dr
;
614 tree ref
= DR_REF (a
);
615 tree base_ref
= DR_BASE_OBJECT (a
);
616 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
619 while (TREE_CODE (ref
) == COMPONENT_REF
620 || TREE_CODE (ref
) == IMAGPART_EXPR
621 || TREE_CODE (ref
) == REALPART_EXPR
)
622 ref
= TREE_OPERAND (ref
, 0);
624 master_dr
= &ref_DR_map
->get_or_insert (ref
, &exist1
);
630 IFC_DR (*master_dr
)->w_predicate
631 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
632 IFC_DR (*master_dr
)->w_predicate
);
633 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
634 DR_W_UNCONDITIONALLY (*master_dr
) = true;
636 IFC_DR (*master_dr
)->rw_predicate
637 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
638 IFC_DR (*master_dr
)->rw_predicate
);
639 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
640 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
644 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
647 IFC_DR (*base_master_dr
)->base_w_predicate
648 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
649 IFC_DR (*base_master_dr
)->base_w_predicate
);
650 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
651 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
655 /* Return true when the memory references of STMT won't trap in the
656 if-converted code. There are two things that we have to check for:
658 - writes to memory occur to writable memory: if-conversion of
659 memory writes transforms the conditional memory writes into
660 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
661 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
662 be executed at all in the original code, it may be a readonly
663 memory. To check that A is not const-qualified, we check that
664 there exists at least an unconditional write to A in the current
667 - reads or writes to memory are valid memory accesses for every
668 iteration. To check that the memory accesses are correctly formed
669 and that we are allowed to read and write in these locations, we
670 check that the memory accesses to be if-converted occur at every
671 iteration unconditionally.
673 Returns true for the memory reference in STMT, same memory reference
674 is read or written unconditionally atleast once and the base memory
675 reference is written unconditionally once. This is to check reference
676 will not write fault. Also retuns true if the memory reference is
677 unconditionally read once then we are conditionally writing to memory
678 which is defined as read and write and is bound to the definition
681 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
683 data_reference_p
*master_dr
, *base_master_dr
;
684 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
686 tree ref_base_a
= DR_REF (a
);
687 tree base
= DR_BASE_OBJECT (a
);
689 gcc_assert (DR_STMT (a
) == stmt
);
691 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
692 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
693 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
694 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
696 master_dr
= ref_DR_map
->get (ref_base_a
);
697 base_master_dr
= baseref_DR_map
->get (base
);
699 gcc_assert (master_dr
!= NULL
);
701 /* If a is unconditionally written to it doesn't trap. */
702 if (DR_W_UNCONDITIONALLY (*master_dr
))
705 /* If a is unconditionally accessed then ... */
706 if (DR_RW_UNCONDITIONALLY (*master_dr
))
708 /* an unconditional read won't trap. */
712 /* an unconditionaly write won't trap if the base is written
713 to unconditionally. */
715 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
719 /* or the base is know to be not readonly. */
720 tree base_tree
= get_base_address (DR_REF (a
));
721 if (DECL_P (base_tree
)
722 && decl_binds_to_current_def_p (base_tree
)
723 && flag_tree_loop_if_convert_stores
724 && !TREE_READONLY (base_tree
))
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
);
796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
798 fprintf (dump_file
, "-------------------------\n");
799 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
802 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
805 /* Some of these constrains might be too conservative. */
806 if (stmt_ends_bb_p (stmt
)
807 || gimple_has_volatile_ops (stmt
)
808 || (TREE_CODE (lhs
) == SSA_NAME
809 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
810 || gimple_has_side_effects (stmt
))
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
813 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
817 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
818 in between if_convertible_loop_p and combine_blocks
819 we can perform loop versioning. */
820 gimple_set_plf (stmt
, GF_PLF_2
, false);
822 if ((! gimple_vuse (stmt
)
823 || gimple_could_trap_p_1 (stmt
, false, false)
824 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
825 && gimple_could_trap_p (stmt
))
827 if (ifcvt_can_use_mask_load_store (stmt
))
829 gimple_set_plf (stmt
, GF_PLF_2
, true);
830 *any_mask_load_store
= true;
833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
834 fprintf (dump_file
, "tree could trap...\n");
838 if (flag_tree_loop_if_convert_stores
)
841 bb
= gimple_bb (stmt
);
843 if (TREE_CODE (lhs
) != SSA_NAME
844 && bb
!= bb
->loop_father
->header
845 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
847 if (ifcvt_can_use_mask_load_store (stmt
))
849 gimple_set_plf (stmt
, GF_PLF_2
, true);
850 *any_mask_load_store
= true;
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
855 fprintf (dump_file
, "LHS is not var\n");
856 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
864 /* Return true when STMT is if-convertible.
866 A statement is if-convertible if:
867 - it is an if-convertible GIMPLE_ASSIGN,
868 - it is a GIMPLE_LABEL or a GIMPLE_COND,
869 - it is builtins call. */
872 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
873 bool *any_mask_load_store
)
875 switch (gimple_code (stmt
))
883 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
884 any_mask_load_store
);
888 tree fndecl
= gimple_call_fndecl (stmt
);
891 int flags
= gimple_call_flags (stmt
);
892 if ((flags
& ECF_CONST
)
893 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
894 /* We can only vectorize some builtins at the moment,
895 so restrict if-conversion to those. */
896 && DECL_BUILT_IN (fndecl
))
903 /* Don't know what to do with 'em so don't do anything. */
904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
906 fprintf (dump_file
, "don't know what to do\n");
907 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
916 /* Assumes that BB has more than 1 predecessors.
917 Returns false if at least one successor is not on critical edge
918 and true otherwise. */
921 all_preds_critical_p (basic_block bb
)
926 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
927 if (EDGE_COUNT (e
->src
->succs
) == 1)
932 /* Returns true if at least one successor in on critical edge. */
934 has_pred_critical_p (basic_block bb
)
939 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
940 if (EDGE_COUNT (e
->src
->succs
) > 1)
945 /* Return true when BB is if-convertible. This routine does not check
946 basic block's statements and phis.
948 A basic block is not if-convertible if:
949 - it is non-empty and it is after the exit block (in BFS order),
950 - it is after the exit block but before the latch,
951 - its edges are not normal.
953 Last restriction is valid if aggressive_if_conv is false.
955 EXIT_BB is the basic block containing the exit of the LOOP. BB is
959 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
965 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
967 if (EDGE_COUNT (bb
->succs
) > 2)
970 if (EDGE_COUNT (bb
->preds
) > 2
971 && !aggressive_if_conv
)
976 if (bb
!= loop
->latch
)
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
979 fprintf (dump_file
, "basic block after exit bb but before latch\n");
982 else if (!empty_block_p (bb
))
984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "non empty basic block after exit bb\n");
988 else if (bb
== loop
->latch
990 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
993 fprintf (dump_file
, "latch is not dominated by exit_block\n");
998 /* Be less adventurous and handle only normal edges. */
999 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1000 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1003 fprintf (dump_file
, "Difficult to handle edges\n");
1007 /* At least one incoming edge has to be non-critical as otherwise edge
1008 predicates are not equal to basic-block predicates of the edge
1009 source. This check is skipped if aggressive_if_conv is true. */
1010 if (!aggressive_if_conv
1011 && EDGE_COUNT (bb
->preds
) > 1
1012 && bb
!= loop
->header
1013 && all_preds_critical_p (bb
))
1015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1016 fprintf (dump_file
, "only critical predecessors\n");
1023 /* Return true when all predecessor blocks of BB are visited. The
1024 VISITED bitmap keeps track of the visited blocks. */
1027 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1031 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1032 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1038 /* Get body of a LOOP in suitable order for if-conversion. It is
1039 caller's responsibility to deallocate basic block list.
1040 If-conversion suitable order is, breadth first sort (BFS) order
1041 with an additional constraint: select a block only if all its
1042 predecessors are already selected. */
1044 static basic_block
*
1045 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1047 basic_block
*blocks
, *blocks_in_bfs_order
;
1050 unsigned int index
= 0;
1051 unsigned int visited_count
= 0;
1053 gcc_assert (loop
->num_nodes
);
1054 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1056 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1057 visited
= BITMAP_ALLOC (NULL
);
1059 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1062 while (index
< loop
->num_nodes
)
1064 bb
= blocks_in_bfs_order
[index
];
1066 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1068 free (blocks_in_bfs_order
);
1069 BITMAP_FREE (visited
);
1074 if (!bitmap_bit_p (visited
, bb
->index
))
1076 if (pred_blocks_visited_p (bb
, &visited
)
1077 || bb
== loop
->header
)
1079 /* This block is now visited. */
1080 bitmap_set_bit (visited
, bb
->index
);
1081 blocks
[visited_count
++] = bb
;
1087 if (index
== loop
->num_nodes
1088 && visited_count
!= loop
->num_nodes
)
1092 free (blocks_in_bfs_order
);
1093 BITMAP_FREE (visited
);
1097 /* Returns true when the analysis of the predicates for all the basic
1098 blocks in LOOP succeeded.
1100 predicate_bbs first allocates the predicates of the basic blocks.
1101 These fields are then initialized with the tree expressions
1102 representing the predicates under which a basic block is executed
1103 in the LOOP. As the loop->header is executed at each iteration, it
1104 has the "true" predicate. Other statements executed under a
1105 condition are predicated with that condition, for example
1112 S1 will be predicated with "x", and
1113 S2 will be predicated with "!x". */
1116 predicate_bbs (loop_p loop
)
1120 for (i
= 0; i
< loop
->num_nodes
; i
++)
1121 init_bb_predicate (ifc_bbs
[i
]);
1123 for (i
= 0; i
< loop
->num_nodes
; i
++)
1125 basic_block bb
= ifc_bbs
[i
];
1129 /* The loop latch and loop exit block are always executed and
1130 have no extra conditions to be processed: skip them. */
1131 if (bb
== loop
->latch
1132 || bb_with_exit_edge_p (loop
, bb
))
1134 reset_bb_predicate (bb
);
1138 cond
= bb_predicate (bb
);
1139 stmt
= last_stmt (bb
);
1140 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1143 edge true_edge
, false_edge
;
1144 location_t loc
= gimple_location (stmt
);
1145 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1147 gimple_cond_lhs (stmt
),
1148 gimple_cond_rhs (stmt
));
1150 /* Add new condition into destination's predicate list. */
1151 extract_true_false_edges_from_block (gimple_bb (stmt
),
1152 &true_edge
, &false_edge
);
1154 /* If C is true, then TRUE_EDGE is taken. */
1155 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1158 /* If C is false, then FALSE_EDGE is taken. */
1159 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1161 add_to_dst_predicate_list (loop
, false_edge
,
1162 unshare_expr (cond
), c2
);
1167 /* If current bb has only one successor, then consider it as an
1168 unconditional goto. */
1169 if (single_succ_p (bb
))
1171 basic_block bb_n
= single_succ (bb
);
1173 /* The successor bb inherits the predicate of its
1174 predecessor. If there is no predicate in the predecessor
1175 bb, then consider the successor bb as always executed. */
1176 if (cond
== NULL_TREE
)
1177 cond
= boolean_true_node
;
1179 add_to_predicate_list (loop
, bb_n
, cond
);
1183 /* The loop header is always executed. */
1184 reset_bb_predicate (loop
->header
);
1185 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1186 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1189 /* Return true when LOOP is if-convertible. This is a helper function
1190 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1191 in if_convertible_loop_p. */
1194 if_convertible_loop_p_1 (struct loop
*loop
,
1195 vec
<loop_p
> *loop_nest
,
1196 vec
<data_reference_p
> *refs
,
1197 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1201 basic_block exit_bb
= NULL
;
1203 /* Don't if-convert the loop when the data dependences cannot be
1204 computed: the loop won't be vectorized in that case. */
1205 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1209 calculate_dominance_info (CDI_DOMINATORS
);
1210 calculate_dominance_info (CDI_POST_DOMINATORS
);
1212 /* Allow statements that can be handled during if-conversion. */
1213 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1216 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1217 fprintf (dump_file
, "Irreducible loop\n");
1221 for (i
= 0; i
< loop
->num_nodes
; i
++)
1223 basic_block bb
= ifc_bbs
[i
];
1225 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1228 if (bb_with_exit_edge_p (loop
, bb
))
1232 for (i
= 0; i
< loop
->num_nodes
; i
++)
1234 basic_block bb
= ifc_bbs
[i
];
1235 gimple_stmt_iterator gsi
;
1237 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1238 switch (gimple_code (gsi_stmt (gsi
)))
1245 gimple_set_uid (gsi_stmt (gsi
), 0);
1252 data_reference_p dr
;
1254 ref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1255 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1257 predicate_bbs (loop
);
1259 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1261 dr
->aux
= XNEW (struct ifc_dr
);
1262 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1263 DR_RW_UNCONDITIONALLY (dr
) = false;
1264 DR_W_UNCONDITIONALLY (dr
) = false;
1265 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1266 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1267 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1268 if (gimple_uid (DR_STMT (dr
)) == 0)
1269 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1270 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1273 for (i
= 0; i
< loop
->num_nodes
; i
++)
1275 basic_block bb
= ifc_bbs
[i
];
1276 gimple_stmt_iterator itr
;
1278 /* Check the if-convertibility of statements in predicated BBs. */
1279 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1280 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1281 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1282 any_mask_load_store
))
1286 for (i
= 0; i
< loop
->num_nodes
; i
++)
1287 free_bb_predicate (ifc_bbs
[i
]);
1289 /* Checking PHIs needs to be done after stmts, as the fact whether there
1290 are any masked loads or stores affects the tests. */
1291 for (i
= 0; i
< loop
->num_nodes
; i
++)
1293 basic_block bb
= ifc_bbs
[i
];
1296 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1297 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1298 *any_mask_load_store
))
1303 fprintf (dump_file
, "Applying if-conversion\n");
1308 /* Return true when LOOP is if-convertible.
1309 LOOP is if-convertible if:
1311 - it has two or more basic blocks,
1312 - it has only one exit,
1313 - loop header is not the exit edge,
1314 - if its basic blocks and phi nodes are if convertible. */
1317 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1322 vec
<data_reference_p
> refs
;
1325 /* Handle only innermost loop. */
1326 if (!loop
|| loop
->inner
)
1328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1329 fprintf (dump_file
, "not innermost loop\n");
1333 /* If only one block, no need for if-conversion. */
1334 if (loop
->num_nodes
<= 2)
1336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1337 fprintf (dump_file
, "less than 2 basic blocks\n");
1341 /* More than one loop exit is too much to handle. */
1342 if (!single_exit (loop
))
1344 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1345 fprintf (dump_file
, "multiple exits\n");
1349 /* If one of the loop header's edge is an exit edge then do not
1350 apply if-conversion. */
1351 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1352 if (loop_exit_edge_p (loop
, e
))
1357 auto_vec
<loop_p
, 3> loop_nest
;
1358 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1359 any_mask_load_store
);
1361 data_reference_p dr
;
1363 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1366 free_data_refs (refs
);
1367 free_dependence_relations (ddrs
);
1372 delete baseref_DR_map
;
1373 baseref_DR_map
= NULL
;
1378 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1379 which is in predicated basic block.
1380 In fact, the following PHI pattern is searching:
1382 reduc_1 = PHI <..., reduc_2>
1386 reduc_2 = PHI <reduc_1, reduc_3>
1388 ARG_0 and ARG_1 are correspondent PHI arguments.
1389 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1390 EXTENDED is true if PHI has > 2 arguments. */
1393 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1394 tree
*op0
, tree
*op1
, bool extended
)
1396 tree lhs
, r_op1
, r_op2
;
1398 gimple
*header_phi
= NULL
;
1399 enum tree_code reduction_op
;
1400 basic_block bb
= gimple_bb (phi
);
1401 struct loop
*loop
= bb
->loop_father
;
1402 edge latch_e
= loop_latch_edge (loop
);
1403 imm_use_iterator imm_iter
;
1404 use_operand_p use_p
;
1407 bool result
= false;
1408 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1411 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1414 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1415 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1417 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1420 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1421 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1425 if (gimple_bb (header_phi
) != loop
->header
)
1428 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1431 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1432 || gimple_has_volatile_ops (stmt
))
1435 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1438 if (!is_predicated (gimple_bb (stmt
)))
1441 /* Check that stmt-block is predecessor of phi-block. */
1442 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1451 if (!has_single_use (lhs
))
1454 reduction_op
= gimple_assign_rhs_code (stmt
);
1455 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1457 r_op1
= gimple_assign_rhs1 (stmt
);
1458 r_op2
= gimple_assign_rhs2 (stmt
);
1460 /* Make R_OP1 to hold reduction variable. */
1461 if (r_op2
== PHI_RESULT (header_phi
)
1462 && reduction_op
== PLUS_EXPR
)
1463 std::swap (r_op1
, r_op2
);
1464 else if (r_op1
!= PHI_RESULT (header_phi
))
1467 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1468 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1470 gimple
*use_stmt
= USE_STMT (use_p
);
1471 if (is_gimple_debug (use_stmt
))
1473 if (use_stmt
== stmt
)
1475 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1479 *op0
= r_op1
; *op1
= r_op2
;
1484 /* Converts conditional scalar reduction into unconditional form, e.g.
1486 if (_5 != 0) goto bb_5 else goto bb_6
1492 # res_2 = PHI <res_13(4), res_6(5)>
1495 will be converted into sequence
1496 _ifc__1 = _5 != 0 ? 1 : 0;
1497 res_2 = res_13 + _ifc__1;
1498 Argument SWAP tells that arguments of conditional expression should be
1500 Returns rhs of resulting PHI assignment. */
1503 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1504 tree cond
, tree op0
, tree op1
, bool swap
)
1506 gimple_stmt_iterator stmt_it
;
1509 tree rhs1
= gimple_assign_rhs1 (reduc
);
1510 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1512 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1514 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1516 fprintf (dump_file
, "Found cond scalar reduction.\n");
1517 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1520 /* Build cond expression using COND and constant operand
1521 of reduction rhs. */
1522 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1523 unshare_expr (cond
),
1527 /* Create assignment stmt and insert it at GSI. */
1528 new_assign
= gimple_build_assign (tmp
, c
);
1529 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1530 /* Build rhs for unconditional increment/decrement. */
1531 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1532 TREE_TYPE (rhs1
), op0
, tmp
);
1534 /* Delete original reduction stmt. */
1535 stmt_it
= gsi_for_stmt (reduc
);
1536 gsi_remove (&stmt_it
, true);
1537 release_defs (reduc
);
1541 /* Produce condition for all occurrences of ARG in PHI node. */
1544 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1545 gimple_stmt_iterator
*gsi
)
1549 tree cond
= NULL_TREE
;
1553 len
= occur
->length ();
1554 gcc_assert (len
> 0);
1555 for (i
= 0; i
< len
; i
++)
1557 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1558 c
= bb_predicate (e
->src
);
1559 if (is_true_predicate (c
))
1561 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1562 is_gimple_condexpr
, NULL_TREE
,
1563 true, GSI_SAME_STMT
);
1564 if (cond
!= NULL_TREE
)
1566 /* Must build OR expression. */
1567 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1568 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1569 is_gimple_condexpr
, NULL_TREE
,
1570 true, GSI_SAME_STMT
);
1575 gcc_assert (cond
!= NULL_TREE
);
1579 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1580 This routine can handle PHI nodes with more than two arguments.
1583 S1: A = PHI <x1(1), x2(5)>
1585 S2: A = cond ? x1 : x2;
1587 The generated code is inserted at GSI that points to the top of
1588 basic block's statement list.
1589 If PHI node has more than two arguments a chain of conditional
1590 expression is produced. */
1594 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1596 gimple
*new_stmt
= NULL
, *reduc
;
1597 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1599 unsigned int index0
;
1600 unsigned int max
, args_len
;
1605 res
= gimple_phi_result (phi
);
1606 if (virtual_operand_p (res
))
1609 if ((rhs
= degenerate_phi_result (phi
))
1610 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1612 && !chrec_contains_undetermined (scev
)
1614 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1618 fprintf (dump_file
, "Degenerate phi!\n");
1619 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1621 new_stmt
= gimple_build_assign (res
, rhs
);
1622 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1623 update_stmt (new_stmt
);
1627 bb
= gimple_bb (phi
);
1628 if (EDGE_COUNT (bb
->preds
) == 2)
1630 /* Predicate ordinary PHI node with 2 arguments. */
1631 edge first_edge
, second_edge
;
1632 basic_block true_bb
;
1633 first_edge
= EDGE_PRED (bb
, 0);
1634 second_edge
= EDGE_PRED (bb
, 1);
1635 cond
= bb_predicate (first_edge
->src
);
1636 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1637 std::swap (first_edge
, second_edge
);
1638 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1640 cond
= bb_predicate (second_edge
->src
);
1641 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1642 cond
= TREE_OPERAND (cond
, 0);
1644 first_edge
= second_edge
;
1647 cond
= bb_predicate (first_edge
->src
);
1648 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1649 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1650 is_gimple_condexpr
, NULL_TREE
,
1651 true, GSI_SAME_STMT
);
1652 true_bb
= first_edge
->src
;
1653 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1655 arg0
= gimple_phi_arg_def (phi
, 1);
1656 arg1
= gimple_phi_arg_def (phi
, 0);
1660 arg0
= gimple_phi_arg_def (phi
, 0);
1661 arg1
= gimple_phi_arg_def (phi
, 1);
1663 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1665 /* Convert reduction stmt into vectorizable form. */
1666 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1667 true_bb
!= gimple_bb (reduc
));
1669 /* Build new RHS using selected condition and arguments. */
1670 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1672 new_stmt
= gimple_build_assign (res
, rhs
);
1673 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1674 update_stmt (new_stmt
);
1676 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1678 fprintf (dump_file
, "new phi replacement stmt\n");
1679 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1684 /* Create hashmap for PHI node which contain vector of argument indexes
1685 having the same value. */
1687 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1688 unsigned int num_args
= gimple_phi_num_args (phi
);
1690 /* Vector of different PHI argument values. */
1691 auto_vec
<tree
> args (num_args
);
1693 /* Compute phi_arg_map. */
1694 for (i
= 0; i
< num_args
; i
++)
1698 arg
= gimple_phi_arg_def (phi
, i
);
1699 if (!phi_arg_map
.get (arg
))
1700 args
.quick_push (arg
);
1701 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1704 /* Determine element with max number of occurrences. */
1707 args_len
= args
.length ();
1708 for (i
= 0; i
< args_len
; i
++)
1711 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1718 /* Put element with max number of occurences to the end of ARGS. */
1719 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1720 std::swap (args
[args_len
- 1], args
[max_ind
]);
1722 /* Handle one special case when number of arguments with different values
1723 is equal 2 and one argument has the only occurrence. Such PHI can be
1724 handled as if would have only 2 arguments. */
1725 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1728 indexes
= phi_arg_map
.get (args
[0]);
1729 index0
= (*indexes
)[0];
1732 e
= gimple_phi_arg_edge (phi
, index0
);
1733 cond
= bb_predicate (e
->src
);
1734 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1737 cond
= TREE_OPERAND (cond
, 0);
1739 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1740 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1741 is_gimple_condexpr
, NULL_TREE
,
1742 true, GSI_SAME_STMT
);
1743 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1745 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1749 /* Convert reduction stmt into vectorizable form. */
1750 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1752 new_stmt
= gimple_build_assign (res
, rhs
);
1753 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1754 update_stmt (new_stmt
);
1760 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1763 for (i
= 0; i
< args_len
; i
++)
1766 indexes
= phi_arg_map
.get (args
[i
]);
1767 if (i
!= args_len
- 1)
1768 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1771 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1772 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1774 new_stmt
= gimple_build_assign (lhs
, rhs
);
1775 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1776 update_stmt (new_stmt
);
1781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1783 fprintf (dump_file
, "new extended phi replacement stmt\n");
1784 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1788 /* Replaces in LOOP all the scalar phi nodes other than those in the
1789 LOOP->header block with conditional modify expressions. */
1792 predicate_all_scalar_phis (struct loop
*loop
)
1795 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1798 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1801 gimple_stmt_iterator gsi
;
1802 gphi_iterator phi_gsi
;
1805 if (bb
== loop
->header
)
1808 if (EDGE_COUNT (bb
->preds
) == 1)
1811 phi_gsi
= gsi_start_phis (bb
);
1812 if (gsi_end_p (phi_gsi
))
1815 gsi
= gsi_after_labels (bb
);
1816 while (!gsi_end_p (phi_gsi
))
1818 phi
= phi_gsi
.phi ();
1819 predicate_scalar_phi (phi
, &gsi
);
1820 release_phi_node (phi
);
1821 gsi_next (&phi_gsi
);
1824 set_phi_nodes (bb
, NULL
);
1828 /* Insert in each basic block of LOOP the statements produced by the
1829 gimplification of the predicates. */
1832 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1836 for (i
= 0; i
< loop
->num_nodes
; i
++)
1838 basic_block bb
= ifc_bbs
[i
];
1840 if (!is_predicated (bb
))
1841 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1842 if (!is_predicated (bb
))
1844 /* Do not insert statements for a basic block that is not
1845 predicated. Also make sure that the predicate of the
1846 basic block is set to true. */
1847 reset_bb_predicate (bb
);
1851 stmts
= bb_predicate_gimplified_stmts (bb
);
1854 if (flag_tree_loop_if_convert_stores
1855 || any_mask_load_store
)
1857 /* Insert the predicate of the BB just after the label,
1858 as the if-conversion of memory writes will use this
1860 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1861 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1865 /* Insert the predicate of the BB at the end of the BB
1866 as this would reduce the register pressure: the only
1867 use of this predicate will be in successor BBs. */
1868 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1871 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1872 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1874 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1877 /* Once the sequence is code generated, set it to NULL. */
1878 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1883 /* Helper function for predicate_mem_writes. Returns index of existent
1884 mask if it was created for given SIZE and -1 otherwise. */
1887 mask_exists (int size
, vec
<int> vec
)
1891 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1897 /* Predicate each write to memory in LOOP.
1899 This function transforms control flow constructs containing memory
1902 | for (i = 0; i < N; i++)
1906 into the following form that does not contain control flow:
1908 | for (i = 0; i < N; i++)
1909 | A[i] = cond ? expr : A[i];
1911 The original CFG looks like this:
1918 | if (i < N) goto bb_5 else goto bb_2
1922 | cond = some_computation;
1923 | if (cond) goto bb_3 else goto bb_4
1935 insert_gimplified_predicates inserts the computation of the COND
1936 expression at the beginning of the destination basic block:
1943 | if (i < N) goto bb_5 else goto bb_2
1947 | cond = some_computation;
1948 | if (cond) goto bb_3 else goto bb_4
1952 | cond = some_computation;
1961 predicate_mem_writes is then predicating the memory write as follows:
1968 | if (i < N) goto bb_5 else goto bb_2
1972 | if (cond) goto bb_3 else goto bb_4
1976 | cond = some_computation;
1977 | A[i] = cond ? expr : A[i];
1985 and finally combine_blocks removes the basic block boundaries making
1986 the loop vectorizable:
1990 | if (i < N) goto bb_5 else goto bb_1
1994 | cond = some_computation;
1995 | A[i] = cond ? expr : A[i];
1996 | if (i < N) goto bb_5 else goto bb_4
2005 predicate_mem_writes (loop_p loop
)
2007 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2008 auto_vec
<int, 1> vect_sizes
;
2009 auto_vec
<tree
, 1> vect_masks
;
2011 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2013 gimple_stmt_iterator gsi
;
2014 basic_block bb
= ifc_bbs
[i
];
2015 tree cond
= bb_predicate (bb
);
2020 if (is_true_predicate (cond
))
2024 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2027 cond
= TREE_OPERAND (cond
, 0);
2030 vect_sizes
.truncate (0);
2031 vect_masks
.truncate (0);
2033 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2034 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2036 else if (gimple_plf (stmt
, GF_PLF_2
))
2038 tree lhs
= gimple_assign_lhs (stmt
);
2039 tree rhs
= gimple_assign_rhs1 (stmt
);
2040 tree ref
, addr
, ptr
, mask
;
2042 gimple_seq stmts
= NULL
;
2043 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2044 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2045 mark_addressable (ref
);
2046 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2047 true, NULL_TREE
, true,
2049 if (!vect_sizes
.is_empty ()
2050 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2051 /* Use created mask. */
2052 mask
= vect_masks
[index
];
2055 if (COMPARISON_CLASS_P (cond
))
2056 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2058 TREE_OPERAND (cond
, 0),
2059 TREE_OPERAND (cond
, 1));
2062 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2069 = constant_boolean_node (true, TREE_TYPE (mask
));
2070 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2071 TREE_TYPE (mask
), mask
, true_val
);
2073 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2075 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2076 /* Save mask and its size for further use. */
2077 vect_sizes
.safe_push (bitsize
);
2078 vect_masks
.safe_push (mask
);
2080 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
2081 /* Copy points-to info if possible. */
2082 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2083 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2085 if (TREE_CODE (lhs
) == SSA_NAME
)
2088 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2090 gimple_call_set_lhs (new_stmt
, lhs
);
2094 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2096 gsi_replace (&gsi
, new_stmt
, true);
2098 else if (gimple_vdef (stmt
))
2100 tree lhs
= gimple_assign_lhs (stmt
);
2101 tree rhs
= gimple_assign_rhs1 (stmt
);
2102 tree type
= TREE_TYPE (lhs
);
2104 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2105 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2107 std::swap (lhs
, rhs
);
2108 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2109 is_gimple_condexpr
, NULL_TREE
,
2110 true, GSI_SAME_STMT
);
2111 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2112 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2118 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2119 other than the exit and latch of the LOOP. Also resets the
2120 GIMPLE_DEBUG information. */
2123 remove_conditions_and_labels (loop_p loop
)
2125 gimple_stmt_iterator gsi
;
2128 for (i
= 0; i
< loop
->num_nodes
; i
++)
2130 basic_block bb
= ifc_bbs
[i
];
2132 if (bb_with_exit_edge_p (loop
, bb
)
2133 || bb
== loop
->latch
)
2136 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2137 switch (gimple_code (gsi_stmt (gsi
)))
2141 gsi_remove (&gsi
, true);
2145 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2146 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2148 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2149 update_stmt (gsi_stmt (gsi
));
2160 /* Combine all the basic blocks from LOOP into one or two super basic
2161 blocks. Replace PHI nodes with conditional modify expressions. */
2164 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2166 basic_block bb
, exit_bb
, merge_target_bb
;
2167 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2172 predicate_bbs (loop
);
2173 remove_conditions_and_labels (loop
);
2174 insert_gimplified_predicates (loop
, any_mask_load_store
);
2175 predicate_all_scalar_phis (loop
);
2177 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2178 predicate_mem_writes (loop
);
2180 /* Merge basic blocks: first remove all the edges in the loop,
2181 except for those from the exit block. */
2183 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2184 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2187 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2188 free_bb_predicate (bb
);
2189 if (bb_with_exit_edge_p (loop
, bb
))
2191 gcc_assert (exit_bb
== NULL
);
2195 gcc_assert (exit_bb
!= loop
->latch
);
2197 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2201 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2203 if (e
->src
== exit_bb
)
2210 if (exit_bb
!= NULL
)
2212 if (exit_bb
!= loop
->header
)
2214 /* Connect this node to loop header. */
2215 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2216 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2219 /* Redirect non-exit edges to loop->latch. */
2220 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2222 if (!loop_exit_edge_p (loop
, e
))
2223 redirect_edge_and_branch (e
, loop
->latch
);
2225 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2229 /* If the loop does not have an exit, reconnect header and latch. */
2230 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2231 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2234 merge_target_bb
= loop
->header
;
2235 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2237 gimple_stmt_iterator gsi
;
2238 gimple_stmt_iterator last
;
2242 if (bb
== exit_bb
|| bb
== loop
->latch
)
2245 /* Make stmts member of loop->header and clear range info from all stmts
2246 in BB which is now no longer executed conditional on a predicate we
2247 could have derived it from. */
2248 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2250 gimple
*stmt
= gsi_stmt (gsi
);
2251 gimple_set_bb (stmt
, merge_target_bb
);
2256 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2257 reset_flow_sensitive_info (op
);
2261 /* Update stmt list. */
2262 last
= gsi_last_bb (merge_target_bb
);
2263 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2264 set_bb_seq (bb
, NULL
);
2266 delete_basic_block (bb
);
2269 /* If possible, merge loop header to the block with the exit edge.
2270 This reduces the number of basic blocks to two, to please the
2271 vectorizer that handles only loops with two nodes. */
2273 && exit_bb
!= loop
->header
2274 && can_merge_blocks_p (loop
->header
, exit_bb
))
2275 merge_blocks (loop
->header
, exit_bb
);
2282 /* Version LOOP before if-converting it; the original loop
2283 will be if-converted, the new copy of the loop will not,
2284 and the LOOP_VECTORIZED internal call will be guarding which
2285 loop to execute. The vectorizer pass will fold this
2286 internal call into either true or false. */
2289 version_loop_for_if_conversion (struct loop
*loop
)
2291 basic_block cond_bb
;
2292 tree cond
= make_ssa_name (boolean_type_node
);
2293 struct loop
*new_loop
;
2295 gimple_stmt_iterator gsi
;
2297 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2298 build_int_cst (integer_type_node
, loop
->num
),
2300 gimple_call_set_lhs (g
, cond
);
2302 initialize_original_copy_tables ();
2303 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2304 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2305 REG_BR_PROB_BASE
, true);
2306 free_original_copy_tables ();
2307 if (new_loop
== NULL
)
2309 new_loop
->dont_vectorize
= true;
2310 new_loop
->force_vectorize
= false;
2311 gsi
= gsi_last_bb (cond_bb
);
2312 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2313 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2314 update_ssa (TODO_update_ssa
);
2318 /* Performs splitting of critical edges if aggressive_if_conv is true.
2319 Returns false if loop won't be if converted and true otherwise. */
2322 ifcvt_split_critical_edges (struct loop
*loop
)
2326 unsigned int num
= loop
->num_nodes
;
2336 if (!single_exit (loop
))
2339 body
= get_loop_body (loop
);
2340 for (i
= 0; i
< num
; i
++)
2343 if (bb
== loop
->latch
2344 || bb_with_exit_edge_p (loop
, bb
))
2346 stmt
= last_stmt (bb
);
2347 /* Skip basic blocks not ending with conditional branch. */
2348 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2350 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2351 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2358 /* Assumes that lhs of DEF_STMT have multiple uses.
2359 Delete one use by (1) creation of copy DEF_STMT with
2360 unique lhs; (2) change original use of lhs in one
2361 use statement with newly created lhs. */
2364 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2369 gimple_stmt_iterator gsi
;
2370 use_operand_p use_p
;
2371 imm_use_iterator imm_iter
;
2373 var
= gimple_assign_lhs (def_stmt
);
2374 copy_stmt
= gimple_copy (def_stmt
);
2375 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2376 gimple_assign_set_lhs (copy_stmt
, lhs
);
2377 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2378 /* Insert copy of DEF_STMT. */
2379 gsi
= gsi_for_stmt (def_stmt
);
2380 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2381 /* Change use of var to lhs in use_stmt. */
2382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2384 fprintf (dump_file
, "Change use of var ");
2385 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2386 fprintf (dump_file
, " to ");
2387 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2388 fprintf (dump_file
, "\n");
2390 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2392 if (USE_STMT (use_p
) != use_stmt
)
2394 SET_USE (use_p
, lhs
);
2399 /* Traverse bool pattern recursively starting from VAR.
2400 Save its def and use statements to defuse_list if VAR does
2401 not have single use. */
2404 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2408 enum tree_code code
;
2411 def_stmt
= SSA_NAME_DEF_STMT (var
);
2412 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2414 if (!has_single_use (var
))
2416 /* Put def and use stmts into defuse_list. */
2417 defuse_list
->safe_push (def_stmt
);
2418 defuse_list
->safe_push (use_stmt
);
2419 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2421 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2422 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2425 rhs1
= gimple_assign_rhs1 (def_stmt
);
2426 code
= gimple_assign_rhs_code (def_stmt
);
2430 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2433 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2434 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2435 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2437 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2440 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2445 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2446 rhs2
= gimple_assign_rhs2 (def_stmt
);
2447 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2455 /* Returns true if STMT can be a root of bool pattern applied
2459 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2461 enum tree_code code
;
2464 code
= gimple_assign_rhs_code (stmt
);
2465 if (CONVERT_EXPR_CODE_P (code
))
2467 lhs
= gimple_assign_lhs (stmt
);
2468 rhs
= gimple_assign_rhs1 (stmt
);
2469 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2471 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2475 else if (code
== COND_EXPR
)
2477 rhs
= gimple_assign_rhs1 (stmt
);
2478 if (TREE_CODE (rhs
) != SSA_NAME
)
2485 /* Traverse all statements in BB which correspond to loop header to
2486 find out all statements which can start bool pattern applied by
2487 vectorizer and convert multiple uses in it to conform pattern
2488 restrictions. Such case can occur if the same predicate is used both
2489 for phi node conversion and load/store mask. */
2492 ifcvt_repair_bool_pattern (basic_block bb
)
2496 gimple_stmt_iterator gsi
;
2497 vec
<gimple
*> defuse_list
= vNULL
;
2498 vec
<gimple
*> pattern_roots
= vNULL
;
2503 /* Collect all root pattern statements. */
2504 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2506 stmt
= gsi_stmt (gsi
);
2507 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2509 if (!stmt_is_root_of_bool_pattern (stmt
))
2511 pattern_roots
.safe_push (stmt
);
2514 if (pattern_roots
.is_empty ())
2517 /* Split all statements with multiple uses iteratively since splitting
2518 may create new multiple uses. */
2523 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2525 rhs
= gimple_assign_rhs1 (stmt
);
2526 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2527 while (defuse_list
.length () > 0)
2530 gimple
*def_stmt
, *use_stmt
;
2531 use_stmt
= defuse_list
.pop ();
2532 def_stmt
= defuse_list
.pop ();
2533 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2539 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2543 /* Delete redundant statements produced by predication which prevents
2544 loop vectorization. */
2547 ifcvt_local_dce (basic_block bb
)
2552 gimple_stmt_iterator gsi
;
2553 vec
<gimple
*> worklist
;
2554 enum gimple_code code
;
2555 use_operand_p use_p
;
2556 imm_use_iterator imm_iter
;
2558 worklist
.create (64);
2559 /* Consider all phi as live statements. */
2560 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2562 phi
= gsi_stmt (gsi
);
2563 gimple_set_plf (phi
, GF_PLF_2
, true);
2564 worklist
.safe_push (phi
);
2566 /* Consider load/store statements, CALL and COND as live. */
2567 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2569 stmt
= gsi_stmt (gsi
);
2570 if (gimple_store_p (stmt
)
2571 || gimple_assign_load_p (stmt
)
2572 || is_gimple_debug (stmt
))
2574 gimple_set_plf (stmt
, GF_PLF_2
, true);
2575 worklist
.safe_push (stmt
);
2578 code
= gimple_code (stmt
);
2579 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2581 gimple_set_plf (stmt
, GF_PLF_2
, true);
2582 worklist
.safe_push (stmt
);
2585 gimple_set_plf (stmt
, GF_PLF_2
, false);
2587 if (code
== GIMPLE_ASSIGN
)
2589 tree lhs
= gimple_assign_lhs (stmt
);
2590 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2592 stmt1
= USE_STMT (use_p
);
2593 if (gimple_bb (stmt1
) != bb
)
2595 gimple_set_plf (stmt
, GF_PLF_2
, true);
2596 worklist
.safe_push (stmt
);
2602 /* Propagate liveness through arguments of live stmt. */
2603 while (worklist
.length () > 0)
2606 use_operand_p use_p
;
2609 stmt
= worklist
.pop ();
2610 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2612 use
= USE_FROM_PTR (use_p
);
2613 if (TREE_CODE (use
) != SSA_NAME
)
2615 stmt1
= SSA_NAME_DEF_STMT (use
);
2616 if (gimple_bb (stmt1
) != bb
2617 || gimple_plf (stmt1
, GF_PLF_2
))
2619 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2620 worklist
.safe_push (stmt1
);
2623 /* Delete dead statements. */
2624 gsi
= gsi_start_bb (bb
);
2625 while (!gsi_end_p (gsi
))
2627 stmt
= gsi_stmt (gsi
);
2628 if (gimple_plf (stmt
, GF_PLF_2
))
2633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2635 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2636 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2638 gsi_remove (&gsi
, true);
2639 release_defs (stmt
);
2643 /* If-convert LOOP when it is legal. For the moment this pass has no
2644 profitability analysis. Returns non-zero todo flags when something
2648 tree_if_conversion (struct loop
*loop
)
2650 unsigned int todo
= 0;
2652 bool any_mask_load_store
= false;
2654 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2655 aggressive_if_conv
= loop
->force_vectorize
;
2656 /* Check either outer loop was marked with simd pragma. */
2657 if (!aggressive_if_conv
)
2659 struct loop
*outer_loop
= loop_outer (loop
);
2660 if (outer_loop
&& outer_loop
->force_vectorize
)
2661 aggressive_if_conv
= true;
2664 if (aggressive_if_conv
)
2665 if (!ifcvt_split_critical_edges (loop
))
2668 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2669 || !dbg_cnt (if_conversion_tree
))
2672 if (any_mask_load_store
2673 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2674 || loop
->dont_vectorize
))
2677 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2680 /* Now all statements are if-convertible. Combine all the basic
2681 blocks into one huge basic block doing the if-conversion
2683 combine_blocks (loop
, any_mask_load_store
);
2685 /* Delete dead predicate computations and repair tree correspondent
2686 to bool pattern to delete multiple uses of predicates. */
2687 if (aggressive_if_conv
)
2689 ifcvt_local_dce (loop
->header
);
2690 ifcvt_repair_bool_pattern (loop
->header
);
2693 todo
|= TODO_cleanup_cfg
;
2694 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2696 mark_virtual_operands_for_renaming (cfun
);
2697 todo
|= TODO_update_ssa_only_virtuals
;
2705 for (i
= 0; i
< loop
->num_nodes
; i
++)
2706 free_bb_predicate (ifc_bbs
[i
]);
2711 free_dominance_info (CDI_POST_DOMINATORS
);
2716 /* Tree if-conversion pass management. */
2720 const pass_data pass_data_if_conversion
=
2722 GIMPLE_PASS
, /* type */
2724 OPTGROUP_NONE
, /* optinfo_flags */
2725 TV_NONE
, /* tv_id */
2726 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2727 0, /* properties_provided */
2728 0, /* properties_destroyed */
2729 0, /* todo_flags_start */
2730 0, /* todo_flags_finish */
2733 class pass_if_conversion
: public gimple_opt_pass
2736 pass_if_conversion (gcc::context
*ctxt
)
2737 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2740 /* opt_pass methods: */
2741 virtual bool gate (function
*);
2742 virtual unsigned int execute (function
*);
2744 }; // class pass_if_conversion
2747 pass_if_conversion::gate (function
*fun
)
2749 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2750 && flag_tree_loop_if_convert
!= 0)
2751 || flag_tree_loop_if_convert
== 1
2752 || flag_tree_loop_if_convert_stores
== 1);
2756 pass_if_conversion::execute (function
*fun
)
2761 if (number_of_loops (fun
) <= 1)
2764 FOR_EACH_LOOP (loop
, 0)
2765 if (flag_tree_loop_if_convert
== 1
2766 || flag_tree_loop_if_convert_stores
== 1
2767 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2768 && !loop
->dont_vectorize
))
2769 todo
|= tree_if_conversion (loop
);
2774 FOR_EACH_BB_FN (bb
, fun
)
2775 gcc_assert (!bb
->aux
);
2784 make_pass_if_conversion (gcc::context
*ctxt
)
2786 return new pass_if_conversion (ctxt
);