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 /* -1 when not initialized, 0 when false, 1 when true. */
586 int written_at_least_once
;
588 /* -1 when not initialized, 0 when false, 1 when true. */
589 int rw_unconditionally
;
594 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
595 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
596 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
598 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
599 HASH tables. While storing them in HASH table, it checks if the
600 reference is unconditionally read or written and stores that as a flag
601 information. For base reference it checks if it is written atlest once
602 unconditionally and stores it as flag information along with DR.
603 In other words for every data reference A in STMT there exist other
604 accesses to a data reference with the same base with predicates that
605 add up (OR-up) to the true predicate: this ensures that the data
606 reference A is touched (read or written) on every iteration of the
607 if-converted loop. */
609 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
612 data_reference_p
*master_dr
, *base_master_dr
;
613 tree ref
= DR_REF (a
);
614 tree base_ref
= DR_BASE_OBJECT (a
);
615 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
618 while (TREE_CODE (ref
) == COMPONENT_REF
619 || TREE_CODE (ref
) == IMAGPART_EXPR
620 || TREE_CODE (ref
) == REALPART_EXPR
)
621 ref
= TREE_OPERAND (ref
, 0);
623 master_dr
= &ref_DR_map
->get_or_insert (ref
, &exist1
);
627 IFC_DR (a
)->predicate
= ca
;
631 IFC_DR (*master_dr
)->predicate
633 (EXPR_LOCATION (IFC_DR (*master_dr
)->predicate
),
634 ca
, IFC_DR (*master_dr
)->predicate
);
636 if (is_true_predicate (IFC_DR (*master_dr
)->predicate
))
637 DR_RW_UNCONDITIONALLY (*master_dr
) = 1;
639 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
,&exist2
);
643 IFC_DR (a
)->predicate
= ca
;
647 IFC_DR (*base_master_dr
)->predicate
649 (EXPR_LOCATION (IFC_DR (*base_master_dr
)->predicate
),
650 ca
, IFC_DR (*base_master_dr
)->predicate
);
653 && (is_true_predicate (IFC_DR (*base_master_dr
)->predicate
)))
654 DR_WRITTEN_AT_LEAST_ONCE (*base_master_dr
) = 1;
657 /* Return true when the memory references of STMT won't trap in the
658 if-converted code. There are two things that we have to check for:
660 - writes to memory occur to writable memory: if-conversion of
661 memory writes transforms the conditional memory writes into
662 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
663 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
664 be executed at all in the original code, it may be a readonly
665 memory. To check that A is not const-qualified, we check that
666 there exists at least an unconditional write to A in the current
669 - reads or writes to memory are valid memory accesses for every
670 iteration. To check that the memory accesses are correctly formed
671 and that we are allowed to read and write in these locations, we
672 check that the memory accesses to be if-converted occur at every
673 iteration unconditionally.
675 Returns true for the memory reference in STMT, same memory reference
676 is read or written unconditionally atleast once and the base memory
677 reference is written unconditionally once. This is to check reference
678 will not write fault. Also retuns true if the memory reference is
679 unconditionally read once then we are conditionally writing to memory
680 which is defined as read and write and is bound to the definition
683 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
685 data_reference_p
*master_dr
, *base_master_dr
;
686 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
688 tree ref_base_a
= DR_REF (a
);
689 tree base
= DR_BASE_OBJECT (a
);
691 gcc_assert (DR_STMT (a
) == stmt
);
693 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
694 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
695 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
696 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
698 master_dr
= ref_DR_map
->get (ref_base_a
);
699 base_master_dr
= baseref_DR_map
->get (base
);
701 gcc_assert (master_dr
!= NULL
&& base_master_dr
!= NULL
);
703 if (DR_RW_UNCONDITIONALLY (*master_dr
) == 1)
705 if (DR_WRITTEN_AT_LEAST_ONCE (*base_master_dr
) == 1)
709 tree base_tree
= get_base_address (DR_REF (a
));
710 if (DECL_P (base_tree
)
711 && decl_binds_to_current_def_p (base_tree
)
712 && !TREE_READONLY (base_tree
))
719 /* Wrapper around gimple_could_trap_p refined for the needs of the
720 if-conversion. Try to prove that the memory accesses of STMT could
721 not trap in the innermost loop containing STMT. */
724 ifcvt_could_trap_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
726 if (gimple_vuse (stmt
)
727 && !gimple_could_trap_p_1 (stmt
, false, false)
728 && ifcvt_memrefs_wont_trap (stmt
, refs
))
731 return gimple_could_trap_p (stmt
);
734 /* Return true if STMT could be converted into a masked load or store
735 (conditional load or store based on a mask computed from bb predicate). */
738 ifcvt_can_use_mask_load_store (gimple
*stmt
)
742 basic_block bb
= gimple_bb (stmt
);
745 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
746 || bb
->loop_father
->dont_vectorize
747 || !gimple_assign_single_p (stmt
)
748 || gimple_has_volatile_ops (stmt
))
751 /* Check whether this is a load or store. */
752 lhs
= gimple_assign_lhs (stmt
);
753 if (gimple_store_p (stmt
))
755 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
760 else if (gimple_assign_load_p (stmt
))
763 ref
= gimple_assign_rhs1 (stmt
);
768 if (may_be_nonaddressable_p (ref
))
771 /* Mask should be integer mode of the same size as the load/store
773 mode
= TYPE_MODE (TREE_TYPE (lhs
));
774 if (int_mode_for_mode (mode
) == BLKmode
775 || VECTOR_MODE_P (mode
))
778 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
784 /* Return true when STMT is if-convertible.
786 GIMPLE_ASSIGN statement is not if-convertible if,
789 - LHS is not var decl. */
792 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
793 vec
<data_reference_p
> refs
,
794 bool *any_mask_load_store
)
796 tree lhs
= gimple_assign_lhs (stmt
);
799 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
801 fprintf (dump_file
, "-------------------------\n");
802 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
805 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
808 /* Some of these constrains might be too conservative. */
809 if (stmt_ends_bb_p (stmt
)
810 || gimple_has_volatile_ops (stmt
)
811 || (TREE_CODE (lhs
) == SSA_NAME
812 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
813 || gimple_has_side_effects (stmt
))
815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
816 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
820 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
821 in between if_convertible_loop_p and combine_blocks
822 we can perform loop versioning. */
823 gimple_set_plf (stmt
, GF_PLF_2
, false);
825 if (flag_tree_loop_if_convert_stores
)
827 if (ifcvt_could_trap_p (stmt
, refs
))
829 if (ifcvt_can_use_mask_load_store (stmt
))
831 gimple_set_plf (stmt
, GF_PLF_2
, true);
832 *any_mask_load_store
= true;
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
836 fprintf (dump_file
, "tree could trap...\n");
842 if (ifcvt_could_trap_p (stmt
, refs
))
844 if (ifcvt_can_use_mask_load_store (stmt
))
846 gimple_set_plf (stmt
, GF_PLF_2
, true);
847 *any_mask_load_store
= true;
850 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
851 fprintf (dump_file
, "tree could trap...\n");
855 bb
= gimple_bb (stmt
);
857 if (TREE_CODE (lhs
) != SSA_NAME
858 && bb
!= bb
->loop_father
->header
859 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
861 if (ifcvt_can_use_mask_load_store (stmt
))
863 gimple_set_plf (stmt
, GF_PLF_2
, true);
864 *any_mask_load_store
= true;
867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
869 fprintf (dump_file
, "LHS is not var\n");
870 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
878 /* Return true when STMT is if-convertible.
880 A statement is if-convertible if:
881 - it is an if-convertible GIMPLE_ASSIGN,
882 - it is a GIMPLE_LABEL or a GIMPLE_COND,
883 - it is builtins call. */
886 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
887 bool *any_mask_load_store
)
889 switch (gimple_code (stmt
))
897 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
898 any_mask_load_store
);
902 tree fndecl
= gimple_call_fndecl (stmt
);
905 int flags
= gimple_call_flags (stmt
);
906 if ((flags
& ECF_CONST
)
907 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
908 /* We can only vectorize some builtins at the moment,
909 so restrict if-conversion to those. */
910 && DECL_BUILT_IN (fndecl
))
917 /* Don't know what to do with 'em so don't do anything. */
918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
920 fprintf (dump_file
, "don't know what to do\n");
921 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
930 /* Assumes that BB has more than 1 predecessors.
931 Returns false if at least one successor is not on critical edge
932 and true otherwise. */
935 all_preds_critical_p (basic_block bb
)
940 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
941 if (EDGE_COUNT (e
->src
->succs
) == 1)
946 /* Returns true if at least one successor in on critical edge. */
948 has_pred_critical_p (basic_block bb
)
953 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
954 if (EDGE_COUNT (e
->src
->succs
) > 1)
959 /* Return true when BB is if-convertible. This routine does not check
960 basic block's statements and phis.
962 A basic block is not if-convertible if:
963 - it is non-empty and it is after the exit block (in BFS order),
964 - it is after the exit block but before the latch,
965 - its edges are not normal.
967 Last restriction is valid if aggressive_if_conv is false.
969 EXIT_BB is the basic block containing the exit of the LOOP. BB is
973 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
979 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
981 if (EDGE_COUNT (bb
->succs
) > 2)
984 if (EDGE_COUNT (bb
->preds
) > 2
985 && !aggressive_if_conv
)
990 if (bb
!= loop
->latch
)
992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
993 fprintf (dump_file
, "basic block after exit bb but before latch\n");
996 else if (!empty_block_p (bb
))
998 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
999 fprintf (dump_file
, "non empty basic block after exit bb\n");
1002 else if (bb
== loop
->latch
1004 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1006 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1007 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1012 /* Be less adventurous and handle only normal edges. */
1013 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1014 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1016 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1017 fprintf (dump_file
, "Difficult to handle edges\n");
1021 /* At least one incoming edge has to be non-critical as otherwise edge
1022 predicates are not equal to basic-block predicates of the edge
1023 source. This check is skipped if aggressive_if_conv is true. */
1024 if (!aggressive_if_conv
1025 && EDGE_COUNT (bb
->preds
) > 1
1026 && bb
!= loop
->header
1027 && all_preds_critical_p (bb
))
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "only critical predecessors\n");
1037 /* Return true when all predecessor blocks of BB are visited. The
1038 VISITED bitmap keeps track of the visited blocks. */
1041 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1045 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1046 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1052 /* Get body of a LOOP in suitable order for if-conversion. It is
1053 caller's responsibility to deallocate basic block list.
1054 If-conversion suitable order is, breadth first sort (BFS) order
1055 with an additional constraint: select a block only if all its
1056 predecessors are already selected. */
1058 static basic_block
*
1059 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1061 basic_block
*blocks
, *blocks_in_bfs_order
;
1064 unsigned int index
= 0;
1065 unsigned int visited_count
= 0;
1067 gcc_assert (loop
->num_nodes
);
1068 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1070 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1071 visited
= BITMAP_ALLOC (NULL
);
1073 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1076 while (index
< loop
->num_nodes
)
1078 bb
= blocks_in_bfs_order
[index
];
1080 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1082 free (blocks_in_bfs_order
);
1083 BITMAP_FREE (visited
);
1088 if (!bitmap_bit_p (visited
, bb
->index
))
1090 if (pred_blocks_visited_p (bb
, &visited
)
1091 || bb
== loop
->header
)
1093 /* This block is now visited. */
1094 bitmap_set_bit (visited
, bb
->index
);
1095 blocks
[visited_count
++] = bb
;
1101 if (index
== loop
->num_nodes
1102 && visited_count
!= loop
->num_nodes
)
1106 free (blocks_in_bfs_order
);
1107 BITMAP_FREE (visited
);
1111 /* Returns true when the analysis of the predicates for all the basic
1112 blocks in LOOP succeeded.
1114 predicate_bbs first allocates the predicates of the basic blocks.
1115 These fields are then initialized with the tree expressions
1116 representing the predicates under which a basic block is executed
1117 in the LOOP. As the loop->header is executed at each iteration, it
1118 has the "true" predicate. Other statements executed under a
1119 condition are predicated with that condition, for example
1126 S1 will be predicated with "x", and
1127 S2 will be predicated with "!x". */
1130 predicate_bbs (loop_p loop
)
1134 for (i
= 0; i
< loop
->num_nodes
; i
++)
1135 init_bb_predicate (ifc_bbs
[i
]);
1137 for (i
= 0; i
< loop
->num_nodes
; i
++)
1139 basic_block bb
= ifc_bbs
[i
];
1143 /* The loop latch and loop exit block are always executed and
1144 have no extra conditions to be processed: skip them. */
1145 if (bb
== loop
->latch
1146 || bb_with_exit_edge_p (loop
, bb
))
1148 reset_bb_predicate (bb
);
1152 cond
= bb_predicate (bb
);
1153 stmt
= last_stmt (bb
);
1154 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1157 edge true_edge
, false_edge
;
1158 location_t loc
= gimple_location (stmt
);
1159 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1161 gimple_cond_lhs (stmt
),
1162 gimple_cond_rhs (stmt
));
1164 /* Add new condition into destination's predicate list. */
1165 extract_true_false_edges_from_block (gimple_bb (stmt
),
1166 &true_edge
, &false_edge
);
1168 /* If C is true, then TRUE_EDGE is taken. */
1169 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1172 /* If C is false, then FALSE_EDGE is taken. */
1173 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1175 add_to_dst_predicate_list (loop
, false_edge
,
1176 unshare_expr (cond
), c2
);
1181 /* If current bb has only one successor, then consider it as an
1182 unconditional goto. */
1183 if (single_succ_p (bb
))
1185 basic_block bb_n
= single_succ (bb
);
1187 /* The successor bb inherits the predicate of its
1188 predecessor. If there is no predicate in the predecessor
1189 bb, then consider the successor bb as always executed. */
1190 if (cond
== NULL_TREE
)
1191 cond
= boolean_true_node
;
1193 add_to_predicate_list (loop
, bb_n
, cond
);
1197 /* The loop header is always executed. */
1198 reset_bb_predicate (loop
->header
);
1199 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1200 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1203 /* Return true when LOOP is if-convertible. This is a helper function
1204 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1205 in if_convertible_loop_p. */
1208 if_convertible_loop_p_1 (struct loop
*loop
,
1209 vec
<loop_p
> *loop_nest
,
1210 vec
<data_reference_p
> *refs
,
1211 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1215 basic_block exit_bb
= NULL
;
1217 /* Don't if-convert the loop when the data dependences cannot be
1218 computed: the loop won't be vectorized in that case. */
1219 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1223 calculate_dominance_info (CDI_DOMINATORS
);
1224 calculate_dominance_info (CDI_POST_DOMINATORS
);
1226 /* Allow statements that can be handled during if-conversion. */
1227 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1231 fprintf (dump_file
, "Irreducible loop\n");
1235 for (i
= 0; i
< loop
->num_nodes
; i
++)
1237 basic_block bb
= ifc_bbs
[i
];
1239 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1242 if (bb_with_exit_edge_p (loop
, bb
))
1246 for (i
= 0; i
< loop
->num_nodes
; i
++)
1248 basic_block bb
= ifc_bbs
[i
];
1249 gimple_stmt_iterator gsi
;
1251 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1252 switch (gimple_code (gsi_stmt (gsi
)))
1259 gimple_set_uid (gsi_stmt (gsi
), 0);
1266 data_reference_p dr
;
1268 ref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1269 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1271 predicate_bbs (loop
);
1273 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1275 dr
->aux
= XNEW (struct ifc_dr
);
1276 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1277 DR_RW_UNCONDITIONALLY (dr
) = -1;
1278 if (gimple_uid (DR_STMT (dr
)) == 0)
1279 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1280 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1283 for (i
= 0; i
< loop
->num_nodes
; i
++)
1285 basic_block bb
= ifc_bbs
[i
];
1286 gimple_stmt_iterator itr
;
1288 /* Check the if-convertibility of statements in predicated BBs. */
1289 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1290 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1291 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1292 any_mask_load_store
))
1296 for (i
= 0; i
< loop
->num_nodes
; i
++)
1297 free_bb_predicate (ifc_bbs
[i
]);
1299 /* Checking PHIs needs to be done after stmts, as the fact whether there
1300 are any masked loads or stores affects the tests. */
1301 for (i
= 0; i
< loop
->num_nodes
; i
++)
1303 basic_block bb
= ifc_bbs
[i
];
1306 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1307 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1308 *any_mask_load_store
))
1313 fprintf (dump_file
, "Applying if-conversion\n");
1318 /* Return true when LOOP is if-convertible.
1319 LOOP is if-convertible if:
1321 - it has two or more basic blocks,
1322 - it has only one exit,
1323 - loop header is not the exit edge,
1324 - if its basic blocks and phi nodes are if convertible. */
1327 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1332 vec
<data_reference_p
> refs
;
1335 /* Handle only innermost loop. */
1336 if (!loop
|| loop
->inner
)
1338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1339 fprintf (dump_file
, "not innermost loop\n");
1343 /* If only one block, no need for if-conversion. */
1344 if (loop
->num_nodes
<= 2)
1346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1347 fprintf (dump_file
, "less than 2 basic blocks\n");
1351 /* More than one loop exit is too much to handle. */
1352 if (!single_exit (loop
))
1354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1355 fprintf (dump_file
, "multiple exits\n");
1359 /* If one of the loop header's edge is an exit edge then do not
1360 apply if-conversion. */
1361 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1362 if (loop_exit_edge_p (loop
, e
))
1367 auto_vec
<loop_p
, 3> loop_nest
;
1368 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1369 any_mask_load_store
);
1371 data_reference_p dr
;
1373 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1376 free_data_refs (refs
);
1377 free_dependence_relations (ddrs
);
1382 delete baseref_DR_map
;
1383 baseref_DR_map
= NULL
;
1388 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1389 which is in predicated basic block.
1390 In fact, the following PHI pattern is searching:
1392 reduc_1 = PHI <..., reduc_2>
1396 reduc_2 = PHI <reduc_1, reduc_3>
1398 ARG_0 and ARG_1 are correspondent PHI arguments.
1399 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1400 EXTENDED is true if PHI has > 2 arguments. */
1403 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1404 tree
*op0
, tree
*op1
, bool extended
)
1406 tree lhs
, r_op1
, r_op2
;
1408 gimple
*header_phi
= NULL
;
1409 enum tree_code reduction_op
;
1410 basic_block bb
= gimple_bb (phi
);
1411 struct loop
*loop
= bb
->loop_father
;
1412 edge latch_e
= loop_latch_edge (loop
);
1413 imm_use_iterator imm_iter
;
1414 use_operand_p use_p
;
1417 bool result
= false;
1418 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1421 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1424 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1425 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1427 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1430 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1431 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1435 if (gimple_bb (header_phi
) != loop
->header
)
1438 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1441 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1442 || gimple_has_volatile_ops (stmt
))
1445 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1448 if (!is_predicated (gimple_bb (stmt
)))
1451 /* Check that stmt-block is predecessor of phi-block. */
1452 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1461 if (!has_single_use (lhs
))
1464 reduction_op
= gimple_assign_rhs_code (stmt
);
1465 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1467 r_op1
= gimple_assign_rhs1 (stmt
);
1468 r_op2
= gimple_assign_rhs2 (stmt
);
1470 /* Make R_OP1 to hold reduction variable. */
1471 if (r_op2
== PHI_RESULT (header_phi
)
1472 && reduction_op
== PLUS_EXPR
)
1473 std::swap (r_op1
, r_op2
);
1474 else if (r_op1
!= PHI_RESULT (header_phi
))
1477 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1478 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1480 gimple
*use_stmt
= USE_STMT (use_p
);
1481 if (is_gimple_debug (use_stmt
))
1483 if (use_stmt
== stmt
)
1485 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1489 *op0
= r_op1
; *op1
= r_op2
;
1494 /* Converts conditional scalar reduction into unconditional form, e.g.
1496 if (_5 != 0) goto bb_5 else goto bb_6
1502 # res_2 = PHI <res_13(4), res_6(5)>
1505 will be converted into sequence
1506 _ifc__1 = _5 != 0 ? 1 : 0;
1507 res_2 = res_13 + _ifc__1;
1508 Argument SWAP tells that arguments of conditional expression should be
1510 Returns rhs of resulting PHI assignment. */
1513 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1514 tree cond
, tree op0
, tree op1
, bool swap
)
1516 gimple_stmt_iterator stmt_it
;
1519 tree rhs1
= gimple_assign_rhs1 (reduc
);
1520 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1522 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1526 fprintf (dump_file
, "Found cond scalar reduction.\n");
1527 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1530 /* Build cond expression using COND and constant operand
1531 of reduction rhs. */
1532 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1533 unshare_expr (cond
),
1537 /* Create assignment stmt and insert it at GSI. */
1538 new_assign
= gimple_build_assign (tmp
, c
);
1539 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1540 /* Build rhs for unconditional increment/decrement. */
1541 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1542 TREE_TYPE (rhs1
), op0
, tmp
);
1544 /* Delete original reduction stmt. */
1545 stmt_it
= gsi_for_stmt (reduc
);
1546 gsi_remove (&stmt_it
, true);
1547 release_defs (reduc
);
1551 /* Produce condition for all occurrences of ARG in PHI node. */
1554 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1555 gimple_stmt_iterator
*gsi
)
1559 tree cond
= NULL_TREE
;
1563 len
= occur
->length ();
1564 gcc_assert (len
> 0);
1565 for (i
= 0; i
< len
; i
++)
1567 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1568 c
= bb_predicate (e
->src
);
1569 if (is_true_predicate (c
))
1571 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1572 is_gimple_condexpr
, NULL_TREE
,
1573 true, GSI_SAME_STMT
);
1574 if (cond
!= NULL_TREE
)
1576 /* Must build OR expression. */
1577 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1578 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1579 is_gimple_condexpr
, NULL_TREE
,
1580 true, GSI_SAME_STMT
);
1585 gcc_assert (cond
!= NULL_TREE
);
1589 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1590 This routine can handle PHI nodes with more than two arguments.
1593 S1: A = PHI <x1(1), x2(5)>
1595 S2: A = cond ? x1 : x2;
1597 The generated code is inserted at GSI that points to the top of
1598 basic block's statement list.
1599 If PHI node has more than two arguments a chain of conditional
1600 expression is produced. */
1604 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1606 gimple
*new_stmt
= NULL
, *reduc
;
1607 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1609 unsigned int index0
;
1610 unsigned int max
, args_len
;
1615 res
= gimple_phi_result (phi
);
1616 if (virtual_operand_p (res
))
1619 if ((rhs
= degenerate_phi_result (phi
))
1620 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1622 && !chrec_contains_undetermined (scev
)
1624 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1626 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1628 fprintf (dump_file
, "Degenerate phi!\n");
1629 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1631 new_stmt
= gimple_build_assign (res
, rhs
);
1632 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1633 update_stmt (new_stmt
);
1637 bb
= gimple_bb (phi
);
1638 if (EDGE_COUNT (bb
->preds
) == 2)
1640 /* Predicate ordinary PHI node with 2 arguments. */
1641 edge first_edge
, second_edge
;
1642 basic_block true_bb
;
1643 first_edge
= EDGE_PRED (bb
, 0);
1644 second_edge
= EDGE_PRED (bb
, 1);
1645 cond
= bb_predicate (first_edge
->src
);
1646 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1647 std::swap (first_edge
, second_edge
);
1648 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1650 cond
= bb_predicate (second_edge
->src
);
1651 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1652 cond
= TREE_OPERAND (cond
, 0);
1654 first_edge
= second_edge
;
1657 cond
= bb_predicate (first_edge
->src
);
1658 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1659 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1660 is_gimple_condexpr
, NULL_TREE
,
1661 true, GSI_SAME_STMT
);
1662 true_bb
= first_edge
->src
;
1663 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1665 arg0
= gimple_phi_arg_def (phi
, 1);
1666 arg1
= gimple_phi_arg_def (phi
, 0);
1670 arg0
= gimple_phi_arg_def (phi
, 0);
1671 arg1
= gimple_phi_arg_def (phi
, 1);
1673 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1675 /* Convert reduction stmt into vectorizable form. */
1676 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1677 true_bb
!= gimple_bb (reduc
));
1679 /* Build new RHS using selected condition and arguments. */
1680 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1682 new_stmt
= gimple_build_assign (res
, rhs
);
1683 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1684 update_stmt (new_stmt
);
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1688 fprintf (dump_file
, "new phi replacement stmt\n");
1689 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1694 /* Create hashmap for PHI node which contain vector of argument indexes
1695 having the same value. */
1697 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1698 unsigned int num_args
= gimple_phi_num_args (phi
);
1700 /* Vector of different PHI argument values. */
1701 auto_vec
<tree
> args (num_args
);
1703 /* Compute phi_arg_map. */
1704 for (i
= 0; i
< num_args
; i
++)
1708 arg
= gimple_phi_arg_def (phi
, i
);
1709 if (!phi_arg_map
.get (arg
))
1710 args
.quick_push (arg
);
1711 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1714 /* Determine element with max number of occurrences. */
1717 args_len
= args
.length ();
1718 for (i
= 0; i
< args_len
; i
++)
1721 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1728 /* Put element with max number of occurences to the end of ARGS. */
1729 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1730 std::swap (args
[args_len
- 1], args
[max_ind
]);
1732 /* Handle one special case when number of arguments with different values
1733 is equal 2 and one argument has the only occurrence. Such PHI can be
1734 handled as if would have only 2 arguments. */
1735 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1738 indexes
= phi_arg_map
.get (args
[0]);
1739 index0
= (*indexes
)[0];
1742 e
= gimple_phi_arg_edge (phi
, index0
);
1743 cond
= bb_predicate (e
->src
);
1744 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1747 cond
= TREE_OPERAND (cond
, 0);
1749 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1750 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1751 is_gimple_condexpr
, NULL_TREE
,
1752 true, GSI_SAME_STMT
);
1753 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1755 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1759 /* Convert reduction stmt into vectorizable form. */
1760 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1762 new_stmt
= gimple_build_assign (res
, rhs
);
1763 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1764 update_stmt (new_stmt
);
1770 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1773 for (i
= 0; i
< args_len
; i
++)
1776 indexes
= phi_arg_map
.get (args
[i
]);
1777 if (i
!= args_len
- 1)
1778 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1781 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1782 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1784 new_stmt
= gimple_build_assign (lhs
, rhs
);
1785 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1786 update_stmt (new_stmt
);
1791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1793 fprintf (dump_file
, "new extended phi replacement stmt\n");
1794 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1798 /* Replaces in LOOP all the scalar phi nodes other than those in the
1799 LOOP->header block with conditional modify expressions. */
1802 predicate_all_scalar_phis (struct loop
*loop
)
1805 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1808 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1811 gimple_stmt_iterator gsi
;
1812 gphi_iterator phi_gsi
;
1815 if (bb
== loop
->header
)
1818 if (EDGE_COUNT (bb
->preds
) == 1)
1821 phi_gsi
= gsi_start_phis (bb
);
1822 if (gsi_end_p (phi_gsi
))
1825 gsi
= gsi_after_labels (bb
);
1826 while (!gsi_end_p (phi_gsi
))
1828 phi
= phi_gsi
.phi ();
1829 predicate_scalar_phi (phi
, &gsi
);
1830 release_phi_node (phi
);
1831 gsi_next (&phi_gsi
);
1834 set_phi_nodes (bb
, NULL
);
1838 /* Insert in each basic block of LOOP the statements produced by the
1839 gimplification of the predicates. */
1842 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1846 for (i
= 0; i
< loop
->num_nodes
; i
++)
1848 basic_block bb
= ifc_bbs
[i
];
1850 if (!is_predicated (bb
))
1851 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1852 if (!is_predicated (bb
))
1854 /* Do not insert statements for a basic block that is not
1855 predicated. Also make sure that the predicate of the
1856 basic block is set to true. */
1857 reset_bb_predicate (bb
);
1861 stmts
= bb_predicate_gimplified_stmts (bb
);
1864 if (flag_tree_loop_if_convert_stores
1865 || any_mask_load_store
)
1867 /* Insert the predicate of the BB just after the label,
1868 as the if-conversion of memory writes will use this
1870 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1871 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1875 /* Insert the predicate of the BB at the end of the BB
1876 as this would reduce the register pressure: the only
1877 use of this predicate will be in successor BBs. */
1878 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1881 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1882 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1884 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1887 /* Once the sequence is code generated, set it to NULL. */
1888 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1893 /* Helper function for predicate_mem_writes. Returns index of existent
1894 mask if it was created for given SIZE and -1 otherwise. */
1897 mask_exists (int size
, vec
<int> vec
)
1901 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1907 /* Predicate each write to memory in LOOP.
1909 This function transforms control flow constructs containing memory
1912 | for (i = 0; i < N; i++)
1916 into the following form that does not contain control flow:
1918 | for (i = 0; i < N; i++)
1919 | A[i] = cond ? expr : A[i];
1921 The original CFG looks like this:
1928 | if (i < N) goto bb_5 else goto bb_2
1932 | cond = some_computation;
1933 | if (cond) goto bb_3 else goto bb_4
1945 insert_gimplified_predicates inserts the computation of the COND
1946 expression at the beginning of the destination basic block:
1953 | if (i < N) goto bb_5 else goto bb_2
1957 | cond = some_computation;
1958 | if (cond) goto bb_3 else goto bb_4
1962 | cond = some_computation;
1971 predicate_mem_writes is then predicating the memory write as follows:
1978 | if (i < N) goto bb_5 else goto bb_2
1982 | if (cond) goto bb_3 else goto bb_4
1986 | cond = some_computation;
1987 | A[i] = cond ? expr : A[i];
1995 and finally combine_blocks removes the basic block boundaries making
1996 the loop vectorizable:
2000 | if (i < N) goto bb_5 else goto bb_1
2004 | cond = some_computation;
2005 | A[i] = cond ? expr : A[i];
2006 | if (i < N) goto bb_5 else goto bb_4
2015 predicate_mem_writes (loop_p loop
)
2017 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2018 auto_vec
<int, 1> vect_sizes
;
2019 auto_vec
<tree
, 1> vect_masks
;
2021 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2023 gimple_stmt_iterator gsi
;
2024 basic_block bb
= ifc_bbs
[i
];
2025 tree cond
= bb_predicate (bb
);
2030 if (is_true_predicate (cond
))
2034 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2037 cond
= TREE_OPERAND (cond
, 0);
2040 vect_sizes
.truncate (0);
2041 vect_masks
.truncate (0);
2043 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2044 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2046 else if (gimple_plf (stmt
, GF_PLF_2
))
2048 tree lhs
= gimple_assign_lhs (stmt
);
2049 tree rhs
= gimple_assign_rhs1 (stmt
);
2050 tree ref
, addr
, ptr
, mask
;
2052 gimple_seq stmts
= NULL
;
2053 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2054 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2055 mark_addressable (ref
);
2056 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2057 true, NULL_TREE
, true,
2059 if (!vect_sizes
.is_empty ()
2060 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2061 /* Use created mask. */
2062 mask
= vect_masks
[index
];
2065 if (COMPARISON_CLASS_P (cond
))
2066 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2068 TREE_OPERAND (cond
, 0),
2069 TREE_OPERAND (cond
, 1));
2072 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2079 = constant_boolean_node (true, TREE_TYPE (mask
));
2080 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2081 TREE_TYPE (mask
), mask
, true_val
);
2083 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2085 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2086 /* Save mask and its size for further use. */
2087 vect_sizes
.safe_push (bitsize
);
2088 vect_masks
.safe_push (mask
);
2090 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
2091 /* Copy points-to info if possible. */
2092 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2093 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2095 if (TREE_CODE (lhs
) == SSA_NAME
)
2098 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2100 gimple_call_set_lhs (new_stmt
, lhs
);
2104 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2106 gsi_replace (&gsi
, new_stmt
, true);
2108 else if (gimple_vdef (stmt
))
2110 tree lhs
= gimple_assign_lhs (stmt
);
2111 tree rhs
= gimple_assign_rhs1 (stmt
);
2112 tree type
= TREE_TYPE (lhs
);
2114 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2115 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2117 std::swap (lhs
, rhs
);
2118 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2119 is_gimple_condexpr
, NULL_TREE
,
2120 true, GSI_SAME_STMT
);
2121 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2122 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2128 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2129 other than the exit and latch of the LOOP. Also resets the
2130 GIMPLE_DEBUG information. */
2133 remove_conditions_and_labels (loop_p loop
)
2135 gimple_stmt_iterator gsi
;
2138 for (i
= 0; i
< loop
->num_nodes
; i
++)
2140 basic_block bb
= ifc_bbs
[i
];
2142 if (bb_with_exit_edge_p (loop
, bb
)
2143 || bb
== loop
->latch
)
2146 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2147 switch (gimple_code (gsi_stmt (gsi
)))
2151 gsi_remove (&gsi
, true);
2155 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2156 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2158 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2159 update_stmt (gsi_stmt (gsi
));
2170 /* Combine all the basic blocks from LOOP into one or two super basic
2171 blocks. Replace PHI nodes with conditional modify expressions. */
2174 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2176 basic_block bb
, exit_bb
, merge_target_bb
;
2177 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2182 predicate_bbs (loop
);
2183 remove_conditions_and_labels (loop
);
2184 insert_gimplified_predicates (loop
, any_mask_load_store
);
2185 predicate_all_scalar_phis (loop
);
2187 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2188 predicate_mem_writes (loop
);
2190 /* Merge basic blocks: first remove all the edges in the loop,
2191 except for those from the exit block. */
2193 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2194 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2197 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2198 free_bb_predicate (bb
);
2199 if (bb_with_exit_edge_p (loop
, bb
))
2201 gcc_assert (exit_bb
== NULL
);
2205 gcc_assert (exit_bb
!= loop
->latch
);
2207 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2211 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2213 if (e
->src
== exit_bb
)
2220 if (exit_bb
!= NULL
)
2222 if (exit_bb
!= loop
->header
)
2224 /* Connect this node to loop header. */
2225 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2226 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2229 /* Redirect non-exit edges to loop->latch. */
2230 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2232 if (!loop_exit_edge_p (loop
, e
))
2233 redirect_edge_and_branch (e
, loop
->latch
);
2235 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2239 /* If the loop does not have an exit, reconnect header and latch. */
2240 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2241 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2244 merge_target_bb
= loop
->header
;
2245 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2247 gimple_stmt_iterator gsi
;
2248 gimple_stmt_iterator last
;
2252 if (bb
== exit_bb
|| bb
== loop
->latch
)
2255 /* Make stmts member of loop->header and clear range info from all stmts
2256 in BB which is now no longer executed conditional on a predicate we
2257 could have derived it from. */
2258 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2260 gimple
*stmt
= gsi_stmt (gsi
);
2261 gimple_set_bb (stmt
, merge_target_bb
);
2266 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2267 reset_flow_sensitive_info (op
);
2271 /* Update stmt list. */
2272 last
= gsi_last_bb (merge_target_bb
);
2273 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2274 set_bb_seq (bb
, NULL
);
2276 delete_basic_block (bb
);
2279 /* If possible, merge loop header to the block with the exit edge.
2280 This reduces the number of basic blocks to two, to please the
2281 vectorizer that handles only loops with two nodes. */
2283 && exit_bb
!= loop
->header
2284 && can_merge_blocks_p (loop
->header
, exit_bb
))
2285 merge_blocks (loop
->header
, exit_bb
);
2292 /* Version LOOP before if-converting it; the original loop
2293 will be if-converted, the new copy of the loop will not,
2294 and the LOOP_VECTORIZED internal call will be guarding which
2295 loop to execute. The vectorizer pass will fold this
2296 internal call into either true or false. */
2299 version_loop_for_if_conversion (struct loop
*loop
)
2301 basic_block cond_bb
;
2302 tree cond
= make_ssa_name (boolean_type_node
);
2303 struct loop
*new_loop
;
2305 gimple_stmt_iterator gsi
;
2307 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2308 build_int_cst (integer_type_node
, loop
->num
),
2310 gimple_call_set_lhs (g
, cond
);
2312 initialize_original_copy_tables ();
2313 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2314 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2315 REG_BR_PROB_BASE
, true);
2316 free_original_copy_tables ();
2317 if (new_loop
== NULL
)
2319 new_loop
->dont_vectorize
= true;
2320 new_loop
->force_vectorize
= false;
2321 gsi
= gsi_last_bb (cond_bb
);
2322 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2323 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2324 update_ssa (TODO_update_ssa
);
2328 /* Performs splitting of critical edges if aggressive_if_conv is true.
2329 Returns false if loop won't be if converted and true otherwise. */
2332 ifcvt_split_critical_edges (struct loop
*loop
)
2336 unsigned int num
= loop
->num_nodes
;
2346 if (!single_exit (loop
))
2349 body
= get_loop_body (loop
);
2350 for (i
= 0; i
< num
; i
++)
2353 if (bb
== loop
->latch
2354 || bb_with_exit_edge_p (loop
, bb
))
2356 stmt
= last_stmt (bb
);
2357 /* Skip basic blocks not ending with conditional branch. */
2358 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2360 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2361 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2368 /* Assumes that lhs of DEF_STMT have multiple uses.
2369 Delete one use by (1) creation of copy DEF_STMT with
2370 unique lhs; (2) change original use of lhs in one
2371 use statement with newly created lhs. */
2374 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2379 gimple_stmt_iterator gsi
;
2380 use_operand_p use_p
;
2381 imm_use_iterator imm_iter
;
2383 var
= gimple_assign_lhs (def_stmt
);
2384 copy_stmt
= gimple_copy (def_stmt
);
2385 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2386 gimple_assign_set_lhs (copy_stmt
, lhs
);
2387 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2388 /* Insert copy of DEF_STMT. */
2389 gsi
= gsi_for_stmt (def_stmt
);
2390 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2391 /* Change use of var to lhs in use_stmt. */
2392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2394 fprintf (dump_file
, "Change use of var ");
2395 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2396 fprintf (dump_file
, " to ");
2397 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2398 fprintf (dump_file
, "\n");
2400 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2402 if (USE_STMT (use_p
) != use_stmt
)
2404 SET_USE (use_p
, lhs
);
2409 /* Traverse bool pattern recursively starting from VAR.
2410 Save its def and use statements to defuse_list if VAR does
2411 not have single use. */
2414 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2418 enum tree_code code
;
2421 def_stmt
= SSA_NAME_DEF_STMT (var
);
2422 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2424 if (!has_single_use (var
))
2426 /* Put def and use stmts into defuse_list. */
2427 defuse_list
->safe_push (def_stmt
);
2428 defuse_list
->safe_push (use_stmt
);
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2431 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2432 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2435 rhs1
= gimple_assign_rhs1 (def_stmt
);
2436 code
= gimple_assign_rhs_code (def_stmt
);
2440 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2443 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2444 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2445 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2447 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2450 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2455 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2456 rhs2
= gimple_assign_rhs2 (def_stmt
);
2457 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2465 /* Returns true if STMT can be a root of bool pattern applied
2469 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2471 enum tree_code code
;
2474 code
= gimple_assign_rhs_code (stmt
);
2475 if (CONVERT_EXPR_CODE_P (code
))
2477 lhs
= gimple_assign_lhs (stmt
);
2478 rhs
= gimple_assign_rhs1 (stmt
);
2479 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2481 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2485 else if (code
== COND_EXPR
)
2487 rhs
= gimple_assign_rhs1 (stmt
);
2488 if (TREE_CODE (rhs
) != SSA_NAME
)
2495 /* Traverse all statements in BB which correspond to loop header to
2496 find out all statements which can start bool pattern applied by
2497 vectorizer and convert multiple uses in it to conform pattern
2498 restrictions. Such case can occur if the same predicate is used both
2499 for phi node conversion and load/store mask. */
2502 ifcvt_repair_bool_pattern (basic_block bb
)
2506 gimple_stmt_iterator gsi
;
2507 vec
<gimple
*> defuse_list
= vNULL
;
2508 vec
<gimple
*> pattern_roots
= vNULL
;
2513 /* Collect all root pattern statements. */
2514 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2516 stmt
= gsi_stmt (gsi
);
2517 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2519 if (!stmt_is_root_of_bool_pattern (stmt
))
2521 pattern_roots
.safe_push (stmt
);
2524 if (pattern_roots
.is_empty ())
2527 /* Split all statements with multiple uses iteratively since splitting
2528 may create new multiple uses. */
2533 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2535 rhs
= gimple_assign_rhs1 (stmt
);
2536 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2537 while (defuse_list
.length () > 0)
2540 gimple
*def_stmt
, *use_stmt
;
2541 use_stmt
= defuse_list
.pop ();
2542 def_stmt
= defuse_list
.pop ();
2543 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2549 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2553 /* Delete redundant statements produced by predication which prevents
2554 loop vectorization. */
2557 ifcvt_local_dce (basic_block bb
)
2562 gimple_stmt_iterator gsi
;
2563 vec
<gimple
*> worklist
;
2564 enum gimple_code code
;
2565 use_operand_p use_p
;
2566 imm_use_iterator imm_iter
;
2568 worklist
.create (64);
2569 /* Consider all phi as live statements. */
2570 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2572 phi
= gsi_stmt (gsi
);
2573 gimple_set_plf (phi
, GF_PLF_2
, true);
2574 worklist
.safe_push (phi
);
2576 /* Consider load/store statements, CALL and COND as live. */
2577 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2579 stmt
= gsi_stmt (gsi
);
2580 if (gimple_store_p (stmt
)
2581 || gimple_assign_load_p (stmt
)
2582 || is_gimple_debug (stmt
))
2584 gimple_set_plf (stmt
, GF_PLF_2
, true);
2585 worklist
.safe_push (stmt
);
2588 code
= gimple_code (stmt
);
2589 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2591 gimple_set_plf (stmt
, GF_PLF_2
, true);
2592 worklist
.safe_push (stmt
);
2595 gimple_set_plf (stmt
, GF_PLF_2
, false);
2597 if (code
== GIMPLE_ASSIGN
)
2599 tree lhs
= gimple_assign_lhs (stmt
);
2600 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2602 stmt1
= USE_STMT (use_p
);
2603 if (gimple_bb (stmt1
) != bb
)
2605 gimple_set_plf (stmt
, GF_PLF_2
, true);
2606 worklist
.safe_push (stmt
);
2612 /* Propagate liveness through arguments of live stmt. */
2613 while (worklist
.length () > 0)
2616 use_operand_p use_p
;
2619 stmt
= worklist
.pop ();
2620 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2622 use
= USE_FROM_PTR (use_p
);
2623 if (TREE_CODE (use
) != SSA_NAME
)
2625 stmt1
= SSA_NAME_DEF_STMT (use
);
2626 if (gimple_bb (stmt1
) != bb
2627 || gimple_plf (stmt1
, GF_PLF_2
))
2629 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2630 worklist
.safe_push (stmt1
);
2633 /* Delete dead statements. */
2634 gsi
= gsi_start_bb (bb
);
2635 while (!gsi_end_p (gsi
))
2637 stmt
= gsi_stmt (gsi
);
2638 if (gimple_plf (stmt
, GF_PLF_2
))
2643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2645 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2646 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2648 gsi_remove (&gsi
, true);
2649 release_defs (stmt
);
2653 /* If-convert LOOP when it is legal. For the moment this pass has no
2654 profitability analysis. Returns non-zero todo flags when something
2658 tree_if_conversion (struct loop
*loop
)
2660 unsigned int todo
= 0;
2662 bool any_mask_load_store
= false;
2664 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2665 aggressive_if_conv
= loop
->force_vectorize
;
2666 /* Check either outer loop was marked with simd pragma. */
2667 if (!aggressive_if_conv
)
2669 struct loop
*outer_loop
= loop_outer (loop
);
2670 if (outer_loop
&& outer_loop
->force_vectorize
)
2671 aggressive_if_conv
= true;
2674 if (aggressive_if_conv
)
2675 if (!ifcvt_split_critical_edges (loop
))
2678 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2679 || !dbg_cnt (if_conversion_tree
))
2682 if (any_mask_load_store
2683 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2684 || loop
->dont_vectorize
))
2687 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2690 /* Now all statements are if-convertible. Combine all the basic
2691 blocks into one huge basic block doing the if-conversion
2693 combine_blocks (loop
, any_mask_load_store
);
2695 /* Delete dead predicate computations and repair tree correspondent
2696 to bool pattern to delete multiple uses of predicates. */
2697 if (aggressive_if_conv
)
2699 ifcvt_local_dce (loop
->header
);
2700 ifcvt_repair_bool_pattern (loop
->header
);
2703 todo
|= TODO_cleanup_cfg
;
2704 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2706 mark_virtual_operands_for_renaming (cfun
);
2707 todo
|= TODO_update_ssa_only_virtuals
;
2715 for (i
= 0; i
< loop
->num_nodes
; i
++)
2716 free_bb_predicate (ifc_bbs
[i
]);
2721 free_dominance_info (CDI_POST_DOMINATORS
);
2726 /* Tree if-conversion pass management. */
2730 const pass_data pass_data_if_conversion
=
2732 GIMPLE_PASS
, /* type */
2734 OPTGROUP_NONE
, /* optinfo_flags */
2735 TV_NONE
, /* tv_id */
2736 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2737 0, /* properties_provided */
2738 0, /* properties_destroyed */
2739 0, /* todo_flags_start */
2740 0, /* todo_flags_finish */
2743 class pass_if_conversion
: public gimple_opt_pass
2746 pass_if_conversion (gcc::context
*ctxt
)
2747 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2750 /* opt_pass methods: */
2751 virtual bool gate (function
*);
2752 virtual unsigned int execute (function
*);
2754 }; // class pass_if_conversion
2757 pass_if_conversion::gate (function
*fun
)
2759 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2760 && flag_tree_loop_if_convert
!= 0)
2761 || flag_tree_loop_if_convert
== 1
2762 || flag_tree_loop_if_convert_stores
== 1);
2766 pass_if_conversion::execute (function
*fun
)
2771 if (number_of_loops (fun
) <= 1)
2774 FOR_EACH_LOOP (loop
, 0)
2775 if (flag_tree_loop_if_convert
== 1
2776 || flag_tree_loop_if_convert_stores
== 1
2777 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2778 && !loop
->dont_vectorize
))
2779 todo
|= tree_if_conversion (loop
);
2784 FOR_EACH_BB_FN (bb
, fun
)
2785 gcc_assert (!bb
->aux
);
2794 make_pass_if_conversion (gcc::context
*ctxt
)
2796 return new pass_if_conversion (ctxt
);