1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2014 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"
88 #include "stor-layout.h"
95 #include "hard-reg-set.h"
98 #include "dominance.h"
100 #include "basic-block.h"
101 #include "gimple-pretty-print.h"
102 #include "tree-ssa-alias.h"
103 #include "internal-fn.h"
104 #include "gimple-fold.h"
105 #include "gimple-expr.h"
108 #include "gimplify.h"
109 #include "gimple-iterator.h"
110 #include "gimplify-me.h"
111 #include "gimple-ssa.h"
112 #include "tree-cfg.h"
113 #include "tree-phinodes.h"
114 #include "ssa-iterators.h"
115 #include "stringpool.h"
116 #include "tree-ssanames.h"
117 #include "tree-into-ssa.h"
118 #include "tree-ssa.h"
120 #include "tree-chrec.h"
121 #include "tree-data-ref.h"
122 #include "tree-scalar-evolution.h"
123 #include "tree-ssa-loop-ivopts.h"
124 #include "tree-ssa-address.h"
125 #include "tree-pass.h"
128 #include "insn-codes.h"
131 /* List of basic blocks in if-conversion-suitable order. */
132 static basic_block
*ifc_bbs
;
134 /* Structure used to predicate basic blocks. This is attached to the
135 ->aux field of the BBs in the loop to be if-converted. */
136 typedef struct bb_predicate_s
{
138 /* The condition under which this basic block is executed. */
141 /* PREDICATE is gimplified, and the sequence of statements is
142 recorded here, in order to avoid the duplication of computations
143 that occur in previous conditions. See PR44483. */
144 gimple_seq predicate_gimplified_stmts
;
147 /* Returns true when the basic block BB has a predicate. */
150 bb_has_predicate (basic_block bb
)
152 return bb
->aux
!= NULL
;
155 /* Returns the gimplified predicate for basic block BB. */
158 bb_predicate (basic_block bb
)
160 return ((bb_predicate_p
) bb
->aux
)->predicate
;
163 /* Sets the gimplified predicate COND for basic block BB. */
166 set_bb_predicate (basic_block bb
, tree cond
)
168 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
169 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
170 || is_gimple_condexpr (cond
));
171 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
174 /* Returns the sequence of statements of the gimplification of the
175 predicate for basic block BB. */
177 static inline gimple_seq
178 bb_predicate_gimplified_stmts (basic_block bb
)
180 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
183 /* Sets the sequence of statements STMTS of the gimplification of the
184 predicate for basic block BB. */
187 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
189 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
192 /* Adds the sequence of statements STMTS to the sequence of statements
193 of the predicate for basic block BB. */
196 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
199 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
202 /* Initializes to TRUE the predicate of basic block BB. */
205 init_bb_predicate (basic_block bb
)
207 bb
->aux
= XNEW (struct bb_predicate_s
);
208 set_bb_predicate_gimplified_stmts (bb
, NULL
);
209 set_bb_predicate (bb
, boolean_true_node
);
212 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
213 but don't actually free it. */
216 release_bb_predicate (basic_block bb
)
218 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
221 gimple_stmt_iterator i
;
223 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
224 free_stmt_operands (cfun
, gsi_stmt (i
));
225 set_bb_predicate_gimplified_stmts (bb
, NULL
);
229 /* Free the predicate of basic block BB. */
232 free_bb_predicate (basic_block bb
)
234 if (!bb_has_predicate (bb
))
237 release_bb_predicate (bb
);
242 /* Reinitialize predicate of BB with the true predicate. */
245 reset_bb_predicate (basic_block bb
)
247 if (!bb_has_predicate (bb
))
248 init_bb_predicate (bb
);
251 release_bb_predicate (bb
);
252 set_bb_predicate (bb
, boolean_true_node
);
256 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
257 the expression EXPR. Inserts the statement created for this
258 computation before GSI and leaves the iterator GSI at the same
262 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
264 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
265 gimple stmt
= gimple_build_assign (new_name
, expr
);
266 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
270 /* Return true when COND is a true predicate. */
273 is_true_predicate (tree cond
)
275 return (cond
== NULL_TREE
276 || cond
== boolean_true_node
277 || integer_onep (cond
));
280 /* Returns true when BB has a predicate that is not trivial: true or
284 is_predicated (basic_block bb
)
286 return !is_true_predicate (bb_predicate (bb
));
289 /* Parses the predicate COND and returns its comparison code and
290 operands OP0 and OP1. */
292 static enum tree_code
293 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
297 if (TREE_CODE (cond
) == SSA_NAME
298 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
300 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
302 *op0
= gimple_assign_rhs1 (s
);
303 *op1
= gimple_assign_rhs2 (s
);
304 return gimple_assign_rhs_code (s
);
307 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
309 tree op
= gimple_assign_rhs1 (s
);
310 tree type
= TREE_TYPE (op
);
311 enum tree_code code
= parse_predicate (op
, op0
, op1
);
313 return code
== ERROR_MARK
? ERROR_MARK
314 : invert_tree_comparison (code
, HONOR_NANS (TYPE_MODE (type
)));
320 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
)
322 *op0
= TREE_OPERAND (cond
, 0);
323 *op1
= TREE_OPERAND (cond
, 1);
324 return TREE_CODE (cond
);
330 /* Returns the fold of predicate C1 OR C2 at location LOC. */
333 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
335 tree op1a
, op1b
, op2a
, op2b
;
336 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
337 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
339 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
341 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
347 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
350 /* Returns true if N is either a constant or a SSA_NAME. */
353 constant_or_ssa_name (tree n
)
355 switch (TREE_CODE (n
))
368 /* Returns either a COND_EXPR or the folded expression if the folded
369 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
370 a constant or a SSA_NAME. */
373 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
375 tree rhs1
, lhs1
, cond_expr
;
376 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
379 if (cond_expr
== NULL_TREE
)
380 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
382 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
384 if (constant_or_ssa_name (cond_expr
))
387 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
389 rhs1
= TREE_OPERAND (cond_expr
, 1);
390 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
391 if (constant_or_ssa_name (rhs1
))
392 return build1 (ABS_EXPR
, type
, rhs1
);
395 if (TREE_CODE (cond_expr
) == MIN_EXPR
396 || TREE_CODE (cond_expr
) == MAX_EXPR
)
398 lhs1
= TREE_OPERAND (cond_expr
, 0);
399 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
400 rhs1
= TREE_OPERAND (cond_expr
, 1);
401 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
402 if (constant_or_ssa_name (rhs1
)
403 && constant_or_ssa_name (lhs1
))
404 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
406 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
409 /* Add condition NC to the predicate list of basic block BB. LOOP is
410 the loop to be if-converted. */
413 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
417 if (is_true_predicate (nc
))
420 if (!is_predicated (bb
))
422 /* If dominance tells us this basic block is always executed, don't
423 record any predicates for it. */
424 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
431 bc
= bb_predicate (bb
);
432 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
433 if (is_true_predicate (bc
))
435 reset_bb_predicate (bb
);
440 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
441 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
442 tp
= &TREE_OPERAND (bc
, 0);
445 if (!is_gimple_condexpr (*tp
))
448 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
449 add_bb_predicate_gimplified_stmts (bb
, stmts
);
451 set_bb_predicate (bb
, bc
);
454 /* Add the condition COND to the previous condition PREV_COND, and add
455 this to the predicate list of the destination of edge E. LOOP is
456 the loop to be if-converted. */
459 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
460 tree prev_cond
, tree cond
)
462 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
465 if (!is_true_predicate (prev_cond
))
466 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
469 add_to_predicate_list (loop
, e
->dest
, cond
);
472 /* Return true if one of the successor edges of BB exits LOOP. */
475 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
480 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
481 if (loop_exit_edge_p (loop
, e
))
487 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
488 and it belongs to basic block BB.
490 PHI is not if-convertible if:
491 - it has more than 2 arguments.
493 When the flag_tree_loop_if_convert_stores is not set, PHI is not
495 - a virtual PHI is immediately used in another PHI node,
496 - there is a virtual PHI in a BB other than the loop->header. */
499 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
,
500 bool any_mask_load_store
)
502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
504 fprintf (dump_file
, "-------------------------\n");
505 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
508 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
511 fprintf (dump_file
, "More than two phi node args.\n");
515 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
518 /* When the flag_tree_loop_if_convert_stores is not set, check
519 that there are no memory writes in the branches of the loop to be
521 if (virtual_operand_p (gimple_phi_result (phi
)))
523 imm_use_iterator imm_iter
;
526 if (bb
!= loop
->header
)
528 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
529 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
533 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
535 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
538 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
547 /* Records the status of a data reference. This struct is attached to
548 each DR->aux field. */
551 /* -1 when not initialized, 0 when false, 1 when true. */
552 int written_at_least_once
;
554 /* -1 when not initialized, 0 when false, 1 when true. */
555 int rw_unconditionally
;
558 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
559 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
560 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
562 /* Returns true when the memory references of STMT are read or written
563 unconditionally. In other words, this function returns true when
564 for every data reference A in STMT there exist other accesses to
565 a data reference with the same base with predicates that add up (OR-up) to
566 the true predicate: this ensures that the data reference A is touched
567 (read or written) on every iteration of the if-converted loop. */
570 memrefs_read_or_written_unconditionally (gimple stmt
,
571 vec
<data_reference_p
> drs
)
574 data_reference_p a
, b
;
575 tree ca
= bb_predicate (gimple_bb (stmt
));
577 for (i
= 0; drs
.iterate (i
, &a
); i
++)
578 if (DR_STMT (a
) == stmt
)
581 int x
= DR_RW_UNCONDITIONALLY (a
);
589 for (j
= 0; drs
.iterate (j
, &b
); j
++)
591 tree ref_base_a
= DR_REF (a
);
592 tree ref_base_b
= DR_REF (b
);
594 if (DR_STMT (b
) == stmt
)
597 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
598 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
599 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
600 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
602 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
603 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
604 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
605 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
607 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
609 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
611 if (DR_RW_UNCONDITIONALLY (b
) == 1
612 || is_true_predicate (cb
)
613 || is_true_predicate (ca
614 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
616 DR_RW_UNCONDITIONALLY (a
) = 1;
617 DR_RW_UNCONDITIONALLY (b
) = 1;
626 DR_RW_UNCONDITIONALLY (a
) = 0;
634 /* Returns true when the memory references of STMT are unconditionally
635 written. In other words, this function returns true when for every
636 data reference A written in STMT, there exist other writes to the
637 same data reference with predicates that add up (OR-up) to the true
638 predicate: this ensures that the data reference A is written on
639 every iteration of the if-converted loop. */
642 write_memrefs_written_at_least_once (gimple stmt
,
643 vec
<data_reference_p
> drs
)
646 data_reference_p a
, b
;
647 tree ca
= bb_predicate (gimple_bb (stmt
));
649 for (i
= 0; drs
.iterate (i
, &a
); i
++)
650 if (DR_STMT (a
) == stmt
654 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
662 for (j
= 0; drs
.iterate (j
, &b
); j
++)
663 if (DR_STMT (b
) != stmt
665 && same_data_refs_base_objects (a
, b
))
667 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
669 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
670 || is_true_predicate (cb
)
671 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
674 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
675 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
683 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
691 /* Return true when the memory references of STMT won't trap in the
692 if-converted code. There are two things that we have to check for:
694 - writes to memory occur to writable memory: if-conversion of
695 memory writes transforms the conditional memory writes into
696 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
697 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
698 be executed at all in the original code, it may be a readonly
699 memory. To check that A is not const-qualified, we check that
700 there exists at least an unconditional write to A in the current
703 - reads or writes to memory are valid memory accesses for every
704 iteration. To check that the memory accesses are correctly formed
705 and that we are allowed to read and write in these locations, we
706 check that the memory accesses to be if-converted occur at every
707 iteration unconditionally. */
710 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
712 return write_memrefs_written_at_least_once (stmt
, refs
)
713 && memrefs_read_or_written_unconditionally (stmt
, refs
);
716 /* Wrapper around gimple_could_trap_p refined for the needs of the
717 if-conversion. Try to prove that the memory accesses of STMT could
718 not trap in the innermost loop containing STMT. */
721 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
723 if (gimple_vuse (stmt
)
724 && !gimple_could_trap_p_1 (stmt
, false, false)
725 && ifcvt_memrefs_wont_trap (stmt
, refs
))
728 return gimple_could_trap_p (stmt
);
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
, 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 (flag_tree_loop_if_convert_stores
)
824 if (ifcvt_could_trap_p (stmt
, refs
))
826 if (ifcvt_can_use_mask_load_store (stmt
))
828 gimple_set_plf (stmt
, GF_PLF_2
, true);
829 *any_mask_load_store
= true;
832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 fprintf (dump_file
, "tree could trap...\n");
839 if (gimple_assign_rhs_could_trap_p (stmt
))
841 if (ifcvt_can_use_mask_load_store (stmt
))
843 gimple_set_plf (stmt
, GF_PLF_2
, true);
844 *any_mask_load_store
= true;
847 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
848 fprintf (dump_file
, "tree could trap...\n");
852 bb
= gimple_bb (stmt
);
854 if (TREE_CODE (lhs
) != SSA_NAME
855 && bb
!= bb
->loop_father
->header
856 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
858 if (ifcvt_can_use_mask_load_store (stmt
))
860 gimple_set_plf (stmt
, GF_PLF_2
, true);
861 *any_mask_load_store
= true;
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
866 fprintf (dump_file
, "LHS is not var\n");
867 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
875 /* Return true when STMT is if-convertible.
877 A statement is if-convertible if:
878 - it is an if-convertible GIMPLE_ASSIGN,
879 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
882 if_convertible_stmt_p (gimple stmt
, vec
<data_reference_p
> refs
,
883 bool *any_mask_load_store
)
885 switch (gimple_code (stmt
))
893 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
894 any_mask_load_store
);
898 tree fndecl
= gimple_call_fndecl (stmt
);
901 int flags
= gimple_call_flags (stmt
);
902 if ((flags
& ECF_CONST
)
903 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
904 /* We can only vectorize some builtins at the moment,
905 so restrict if-conversion to those. */
906 && DECL_BUILT_IN (fndecl
))
913 /* Don't know what to do with 'em so don't do anything. */
914 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
916 fprintf (dump_file
, "don't know what to do\n");
917 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
926 /* Return true when BB is if-convertible. This routine does not check
927 basic block's statements and phis.
929 A basic block is not if-convertible if:
930 - it is non-empty and it is after the exit block (in BFS order),
931 - it is after the exit block but before the latch,
932 - its edges are not normal.
934 EXIT_BB is the basic block containing the exit of the LOOP. BB is
938 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
944 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
946 if (EDGE_COUNT (bb
->preds
) > 2
947 || EDGE_COUNT (bb
->succs
) > 2)
952 if (bb
!= loop
->latch
)
954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
955 fprintf (dump_file
, "basic block after exit bb but before latch\n");
958 else if (!empty_block_p (bb
))
960 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
961 fprintf (dump_file
, "non empty basic block after exit bb\n");
964 else if (bb
== loop
->latch
966 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
969 fprintf (dump_file
, "latch is not dominated by exit_block\n");
974 /* Be less adventurous and handle only normal edges. */
975 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
976 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
979 fprintf (dump_file
, "Difficult to handle edges\n");
983 /* At least one incoming edge has to be non-critical as otherwise edge
984 predicates are not equal to basic-block predicates of the edge
986 if (EDGE_COUNT (bb
->preds
) > 1
987 && bb
!= loop
->header
)
990 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
991 if (EDGE_COUNT (e
->src
->succs
) == 1)
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
996 fprintf (dump_file
, "only critical predecessors\n");
1004 /* Return true when all predecessor blocks of BB are visited. The
1005 VISITED bitmap keeps track of the visited blocks. */
1008 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1012 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1013 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1019 /* Get body of a LOOP in suitable order for if-conversion. It is
1020 caller's responsibility to deallocate basic block list.
1021 If-conversion suitable order is, breadth first sort (BFS) order
1022 with an additional constraint: select a block only if all its
1023 predecessors are already selected. */
1025 static basic_block
*
1026 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1028 basic_block
*blocks
, *blocks_in_bfs_order
;
1031 unsigned int index
= 0;
1032 unsigned int visited_count
= 0;
1034 gcc_assert (loop
->num_nodes
);
1035 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1037 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1038 visited
= BITMAP_ALLOC (NULL
);
1040 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1043 while (index
< loop
->num_nodes
)
1045 bb
= blocks_in_bfs_order
[index
];
1047 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1049 free (blocks_in_bfs_order
);
1050 BITMAP_FREE (visited
);
1055 if (!bitmap_bit_p (visited
, bb
->index
))
1057 if (pred_blocks_visited_p (bb
, &visited
)
1058 || bb
== loop
->header
)
1060 /* This block is now visited. */
1061 bitmap_set_bit (visited
, bb
->index
);
1062 blocks
[visited_count
++] = bb
;
1068 if (index
== loop
->num_nodes
1069 && visited_count
!= loop
->num_nodes
)
1073 free (blocks_in_bfs_order
);
1074 BITMAP_FREE (visited
);
1078 /* Returns true when the analysis of the predicates for all the basic
1079 blocks in LOOP succeeded.
1081 predicate_bbs first allocates the predicates of the basic blocks.
1082 These fields are then initialized with the tree expressions
1083 representing the predicates under which a basic block is executed
1084 in the LOOP. As the loop->header is executed at each iteration, it
1085 has the "true" predicate. Other statements executed under a
1086 condition are predicated with that condition, for example
1093 S1 will be predicated with "x", and
1094 S2 will be predicated with "!x". */
1097 predicate_bbs (loop_p loop
)
1101 for (i
= 0; i
< loop
->num_nodes
; i
++)
1102 init_bb_predicate (ifc_bbs
[i
]);
1104 for (i
= 0; i
< loop
->num_nodes
; i
++)
1106 basic_block bb
= ifc_bbs
[i
];
1110 /* The loop latch is always executed and has no extra conditions
1111 to be processed: skip it. */
1112 if (bb
== loop
->latch
)
1114 reset_bb_predicate (loop
->latch
);
1118 cond
= bb_predicate (bb
);
1119 stmt
= last_stmt (bb
);
1120 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1123 edge true_edge
, false_edge
;
1124 location_t loc
= gimple_location (stmt
);
1125 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
1127 gimple_cond_lhs (stmt
),
1128 gimple_cond_rhs (stmt
));
1130 /* Add new condition into destination's predicate list. */
1131 extract_true_false_edges_from_block (gimple_bb (stmt
),
1132 &true_edge
, &false_edge
);
1134 /* If C is true, then TRUE_EDGE is taken. */
1135 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1138 /* If C is false, then FALSE_EDGE is taken. */
1139 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1141 add_to_dst_predicate_list (loop
, false_edge
,
1142 unshare_expr (cond
), c2
);
1147 /* If current bb has only one successor, then consider it as an
1148 unconditional goto. */
1149 if (single_succ_p (bb
))
1151 basic_block bb_n
= single_succ (bb
);
1153 /* The successor bb inherits the predicate of its
1154 predecessor. If there is no predicate in the predecessor
1155 bb, then consider the successor bb as always executed. */
1156 if (cond
== NULL_TREE
)
1157 cond
= boolean_true_node
;
1159 add_to_predicate_list (loop
, bb_n
, cond
);
1163 /* The loop header is always executed. */
1164 reset_bb_predicate (loop
->header
);
1165 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1166 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1169 /* Return true when LOOP is if-convertible. This is a helper function
1170 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1171 in if_convertible_loop_p. */
1174 if_convertible_loop_p_1 (struct loop
*loop
,
1175 vec
<loop_p
> *loop_nest
,
1176 vec
<data_reference_p
> *refs
,
1177 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1181 basic_block exit_bb
= NULL
;
1183 /* Don't if-convert the loop when the data dependences cannot be
1184 computed: the loop won't be vectorized in that case. */
1185 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1189 calculate_dominance_info (CDI_DOMINATORS
);
1191 /* Allow statements that can be handled during if-conversion. */
1192 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1195 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1196 fprintf (dump_file
, "Irreducible loop\n");
1200 for (i
= 0; i
< loop
->num_nodes
; i
++)
1202 basic_block bb
= ifc_bbs
[i
];
1204 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1207 if (bb_with_exit_edge_p (loop
, bb
))
1211 for (i
= 0; i
< loop
->num_nodes
; i
++)
1213 basic_block bb
= ifc_bbs
[i
];
1214 gimple_stmt_iterator gsi
;
1216 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1217 switch (gimple_code (gsi_stmt (gsi
)))
1230 if (flag_tree_loop_if_convert_stores
)
1232 data_reference_p dr
;
1234 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1236 dr
->aux
= XNEW (struct ifc_dr
);
1237 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1238 DR_RW_UNCONDITIONALLY (dr
) = -1;
1240 predicate_bbs (loop
);
1243 for (i
= 0; i
< loop
->num_nodes
; i
++)
1245 basic_block bb
= ifc_bbs
[i
];
1246 gimple_stmt_iterator itr
;
1248 /* Check the if-convertibility of statements in predicated BBs. */
1249 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1250 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1251 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1252 any_mask_load_store
))
1256 if (flag_tree_loop_if_convert_stores
)
1257 for (i
= 0; i
< loop
->num_nodes
; i
++)
1258 free_bb_predicate (ifc_bbs
[i
]);
1260 /* Checking PHIs needs to be done after stmts, as the fact whether there
1261 are any masked loads or stores affects the tests. */
1262 for (i
= 0; i
< loop
->num_nodes
; i
++)
1264 basic_block bb
= ifc_bbs
[i
];
1265 gimple_stmt_iterator itr
;
1267 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1268 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
),
1269 *any_mask_load_store
))
1274 fprintf (dump_file
, "Applying if-conversion\n");
1279 /* Return true when LOOP is if-convertible.
1280 LOOP is if-convertible if:
1282 - it has two or more basic blocks,
1283 - it has only one exit,
1284 - loop header is not the exit edge,
1285 - if its basic blocks and phi nodes are if convertible. */
1288 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1293 vec
<data_reference_p
> refs
;
1296 /* Handle only innermost loop. */
1297 if (!loop
|| loop
->inner
)
1299 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1300 fprintf (dump_file
, "not innermost loop\n");
1304 /* If only one block, no need for if-conversion. */
1305 if (loop
->num_nodes
<= 2)
1307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1308 fprintf (dump_file
, "less than 2 basic blocks\n");
1312 /* More than one loop exit is too much to handle. */
1313 if (!single_exit (loop
))
1315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1316 fprintf (dump_file
, "multiple exits\n");
1320 /* If one of the loop header's edge is an exit edge then do not
1321 apply if-conversion. */
1322 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1323 if (loop_exit_edge_p (loop
, e
))
1328 auto_vec
<loop_p
, 3> loop_nest
;
1329 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1330 any_mask_load_store
);
1332 if (flag_tree_loop_if_convert_stores
)
1334 data_reference_p dr
;
1337 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1341 free_data_refs (refs
);
1342 free_dependence_relations (ddrs
);
1346 /* Basic block BB has two predecessors. Using predecessor's bb
1347 predicate, set an appropriate condition COND for the PHI node
1348 replacement. Return the true block whose phi arguments are
1349 selected when cond is true. LOOP is the loop containing the
1350 if-converted region, GSI is the place to insert the code for the
1354 find_phi_replacement_condition (basic_block bb
, tree
*cond
,
1355 gimple_stmt_iterator
*gsi
)
1357 edge first_edge
, second_edge
;
1360 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
1361 first_edge
= EDGE_PRED (bb
, 0);
1362 second_edge
= EDGE_PRED (bb
, 1);
1364 /* Prefer an edge with a not negated predicate.
1365 ??? That's a very weak cost model. */
1366 tmp_cond
= bb_predicate (first_edge
->src
);
1367 gcc_assert (tmp_cond
);
1368 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
1372 tmp_edge
= first_edge
;
1373 first_edge
= second_edge
;
1374 second_edge
= tmp_edge
;
1377 /* Check if the edge we take the condition from is not critical.
1378 We know that at least one non-critical edge exists. */
1379 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1381 *cond
= bb_predicate (second_edge
->src
);
1383 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
1384 *cond
= TREE_OPERAND (*cond
, 0);
1386 /* Select non loop header bb. */
1387 first_edge
= second_edge
;
1390 *cond
= bb_predicate (first_edge
->src
);
1392 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1393 *cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (*cond
),
1394 is_gimple_condexpr
, NULL_TREE
,
1395 true, GSI_SAME_STMT
);
1397 return first_edge
->src
;
1400 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1401 which is in predicated basic block.
1402 In fact, the following PHI pattern is searching:
1404 reduc_1 = PHI <..., reduc_2>
1408 reduc_2 = PHI <reduc_1, reduc_3>
1410 REDUC, OP0 and OP1 contain reduction stmt and its operands. */
1413 is_cond_scalar_reduction (gimple phi
, gimple
*reduc
,
1414 tree
*op0
, tree
*op1
)
1416 tree lhs
, r_op1
, r_op2
;
1419 gimple header_phi
= NULL
;
1420 enum tree_code reduction_op
;
1421 basic_block bb
= gimple_bb (phi
);
1422 struct loop
*loop
= bb
->loop_father
;
1423 edge latch_e
= loop_latch_edge (loop
);
1424 imm_use_iterator imm_iter
;
1425 use_operand_p use_p
;
1427 arg_0
= PHI_ARG_DEF (phi
, 0);
1428 arg_1
= PHI_ARG_DEF (phi
, 1);
1429 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1432 if (gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1435 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1436 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1438 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1441 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1442 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1446 if (gimple_bb (header_phi
) != loop
->header
)
1449 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1452 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1453 || gimple_has_volatile_ops (stmt
))
1456 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1459 if (!is_predicated (gimple_bb (stmt
)))
1462 /* Check that stmt-block is predecessor of phi-block. */
1463 if (EDGE_PRED (bb
, 0)->src
!= gimple_bb (stmt
)
1464 && EDGE_PRED (bb
, 1)->src
!= gimple_bb (stmt
))
1467 if (!has_single_use (lhs
))
1470 reduction_op
= gimple_assign_rhs_code (stmt
);
1471 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1473 r_op1
= gimple_assign_rhs1 (stmt
);
1474 r_op2
= gimple_assign_rhs2 (stmt
);
1476 /* Make R_OP1 to hold reduction variable. */
1477 if (r_op2
== PHI_RESULT (header_phi
)
1478 && reduction_op
== PLUS_EXPR
)
1484 else if (r_op1
!= PHI_RESULT (header_phi
))
1487 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1488 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1490 gimple use_stmt
= USE_STMT (use_p
);
1491 if (is_gimple_debug (use_stmt
))
1493 if (use_stmt
== stmt
)
1495 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1499 *op0
= r_op1
; *op1
= r_op2
;
1504 /* Converts conditional scalar reduction into unconditional form, e.g.
1506 if (_5 != 0) goto bb_5 else goto bb_6
1512 # res_2 = PHI <res_13(4), res_6(5)>
1515 will be converted into sequence
1516 _ifc__1 = _5 != 0 ? 1 : 0;
1517 res_2 = res_13 + _ifc__1;
1518 Argument SWAP tells that arguments of conditional expression should be
1520 Returns rhs of resulting PHI assignment. */
1523 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1524 tree cond
, tree op0
, tree op1
, bool swap
)
1526 gimple_stmt_iterator stmt_it
;
1529 tree rhs1
= gimple_assign_rhs1 (reduc
);
1530 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1532 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1536 fprintf (dump_file
, "Found cond scalar reduction.\n");
1537 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1540 /* Build cond expression using COND and constant operand
1541 of reduction rhs. */
1542 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1543 unshare_expr (cond
),
1547 /* Create assignment stmt and insert it at GSI. */
1548 new_assign
= gimple_build_assign (tmp
, c
);
1549 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1550 /* Build rhs for unconditional increment/decrement. */
1551 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1552 TREE_TYPE (rhs1
), op0
, tmp
);
1554 /* Delete original reduction stmt. */
1555 stmt_it
= gsi_for_stmt (reduc
);
1556 gsi_remove (&stmt_it
, true);
1557 release_defs (reduc
);
1561 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1562 This routine does not handle PHI nodes with more than two
1566 S1: A = PHI <x1(1), x2(5)>
1568 S2: A = cond ? x1 : x2;
1570 The generated code is inserted at GSI that points to the top of
1571 basic block's statement list. When COND is true, phi arg from
1572 TRUE_BB is selected. */
1575 predicate_scalar_phi (gimple phi
, tree cond
,
1576 basic_block true_bb
,
1577 gimple_stmt_iterator
*gsi
)
1581 tree rhs
, res
, arg
, scev
;
1583 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1584 && gimple_phi_num_args (phi
) == 2);
1586 res
= gimple_phi_result (phi
);
1587 /* Do not handle virtual phi nodes. */
1588 if (virtual_operand_p (res
))
1591 bb
= gimple_bb (phi
);
1593 if ((arg
= degenerate_phi_result (phi
))
1594 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1596 && !chrec_contains_undetermined (scev
)
1598 && (arg
= gimple_phi_arg_def (phi
, 0))))
1606 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1607 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1609 arg_0
= gimple_phi_arg_def (phi
, 1);
1610 arg_1
= gimple_phi_arg_def (phi
, 0);
1614 arg_0
= gimple_phi_arg_def (phi
, 0);
1615 arg_1
= gimple_phi_arg_def (phi
, 1);
1617 if (is_cond_scalar_reduction (phi
, &reduc
, &op0
, &op1
))
1618 /* Convert reduction stmt into vectorizable form. */
1619 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1620 true_bb
!= gimple_bb (reduc
));
1622 /* Build new RHS using selected condition and arguments. */
1623 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1627 new_stmt
= gimple_build_assign (res
, rhs
);
1628 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1629 update_stmt (new_stmt
);
1631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1633 fprintf (dump_file
, "new phi replacement stmt\n");
1634 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1638 /* Replaces in LOOP all the scalar phi nodes other than those in the
1639 LOOP->header block with conditional modify expressions. */
1642 predicate_all_scalar_phis (struct loop
*loop
)
1645 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1648 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1651 tree cond
= NULL_TREE
;
1652 gimple_stmt_iterator gsi
, phi_gsi
;
1653 basic_block true_bb
= NULL
;
1656 if (bb
== loop
->header
)
1659 phi_gsi
= gsi_start_phis (bb
);
1660 if (gsi_end_p (phi_gsi
))
1663 /* BB has two predecessors. Using predecessor's aux field, set
1664 appropriate condition for the PHI node replacement. */
1665 gsi
= gsi_after_labels (bb
);
1666 true_bb
= find_phi_replacement_condition (bb
, &cond
, &gsi
);
1668 while (!gsi_end_p (phi_gsi
))
1670 phi
= gsi_stmt (phi_gsi
);
1671 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1672 release_phi_node (phi
);
1673 gsi_next (&phi_gsi
);
1676 set_phi_nodes (bb
, NULL
);
1680 /* Insert in each basic block of LOOP the statements produced by the
1681 gimplification of the predicates. */
1684 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1688 for (i
= 0; i
< loop
->num_nodes
; i
++)
1690 basic_block bb
= ifc_bbs
[i
];
1693 if (!is_predicated (bb
))
1695 /* Do not insert statements for a basic block that is not
1696 predicated. Also make sure that the predicate of the
1697 basic block is set to true. */
1698 reset_bb_predicate (bb
);
1702 stmts
= bb_predicate_gimplified_stmts (bb
);
1705 if (flag_tree_loop_if_convert_stores
1706 || any_mask_load_store
)
1708 /* Insert the predicate of the BB just after the label,
1709 as the if-conversion of memory writes will use this
1711 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1712 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1716 /* Insert the predicate of the BB at the end of the BB
1717 as this would reduce the register pressure: the only
1718 use of this predicate will be in successor BBs. */
1719 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1722 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1723 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1725 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1728 /* Once the sequence is code generated, set it to NULL. */
1729 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1734 /* Predicate each write to memory in LOOP.
1736 This function transforms control flow constructs containing memory
1739 | for (i = 0; i < N; i++)
1743 into the following form that does not contain control flow:
1745 | for (i = 0; i < N; i++)
1746 | A[i] = cond ? expr : A[i];
1748 The original CFG looks like this:
1755 | if (i < N) goto bb_5 else goto bb_2
1759 | cond = some_computation;
1760 | if (cond) goto bb_3 else goto bb_4
1772 insert_gimplified_predicates inserts the computation of the COND
1773 expression at the beginning of the destination basic block:
1780 | if (i < N) goto bb_5 else goto bb_2
1784 | cond = some_computation;
1785 | if (cond) goto bb_3 else goto bb_4
1789 | cond = some_computation;
1798 predicate_mem_writes is then predicating the memory write as follows:
1805 | if (i < N) goto bb_5 else goto bb_2
1809 | if (cond) goto bb_3 else goto bb_4
1813 | cond = some_computation;
1814 | A[i] = cond ? expr : A[i];
1822 and finally combine_blocks removes the basic block boundaries making
1823 the loop vectorizable:
1827 | if (i < N) goto bb_5 else goto bb_1
1831 | cond = some_computation;
1832 | A[i] = cond ? expr : A[i];
1833 | if (i < N) goto bb_5 else goto bb_4
1842 predicate_mem_writes (loop_p loop
)
1844 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1846 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1848 gimple_stmt_iterator gsi
;
1849 basic_block bb
= ifc_bbs
[i
];
1850 tree cond
= bb_predicate (bb
);
1854 if (is_true_predicate (cond
))
1858 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1861 cond
= TREE_OPERAND (cond
, 0);
1864 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1865 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
1867 else if (gimple_plf (stmt
, GF_PLF_2
))
1869 tree lhs
= gimple_assign_lhs (stmt
);
1870 tree rhs
= gimple_assign_rhs1 (stmt
);
1871 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
1873 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
1875 masktype
= build_nonstandard_integer_type (bitsize
, 1);
1876 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
1877 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
1878 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
1879 mark_addressable (ref
);
1880 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
1881 true, NULL_TREE
, true,
1883 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1884 is_gimple_condexpr
, NULL_TREE
,
1885 true, GSI_SAME_STMT
);
1886 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
1887 mask_op0
, mask_op1
);
1888 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
1889 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
1890 /* Copy points-to info if possible. */
1891 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
1892 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
1894 if (TREE_CODE (lhs
) == SSA_NAME
)
1897 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
1899 gimple_call_set_lhs (new_stmt
, lhs
);
1903 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
1905 gsi_replace (&gsi
, new_stmt
, true);
1907 else if (gimple_vdef (stmt
))
1909 tree lhs
= gimple_assign_lhs (stmt
);
1910 tree rhs
= gimple_assign_rhs1 (stmt
);
1911 tree type
= TREE_TYPE (lhs
);
1913 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1914 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1921 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1922 is_gimple_condexpr
, NULL_TREE
,
1923 true, GSI_SAME_STMT
);
1924 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
1925 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1931 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1932 other than the exit and latch of the LOOP. Also resets the
1933 GIMPLE_DEBUG information. */
1936 remove_conditions_and_labels (loop_p loop
)
1938 gimple_stmt_iterator gsi
;
1941 for (i
= 0; i
< loop
->num_nodes
; i
++)
1943 basic_block bb
= ifc_bbs
[i
];
1945 if (bb_with_exit_edge_p (loop
, bb
)
1946 || bb
== loop
->latch
)
1949 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1950 switch (gimple_code (gsi_stmt (gsi
)))
1954 gsi_remove (&gsi
, true);
1958 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1959 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1961 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1962 update_stmt (gsi_stmt (gsi
));
1973 /* Combine all the basic blocks from LOOP into one or two super basic
1974 blocks. Replace PHI nodes with conditional modify expressions. */
1977 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
1979 basic_block bb
, exit_bb
, merge_target_bb
;
1980 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1985 predicate_bbs (loop
);
1986 remove_conditions_and_labels (loop
);
1987 insert_gimplified_predicates (loop
, any_mask_load_store
);
1988 predicate_all_scalar_phis (loop
);
1990 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
1991 predicate_mem_writes (loop
);
1993 /* Merge basic blocks: first remove all the edges in the loop,
1994 except for those from the exit block. */
1996 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1999 free_bb_predicate (bb
);
2000 if (bb_with_exit_edge_p (loop
, bb
))
2002 gcc_assert (exit_bb
== NULL
);
2006 gcc_assert (exit_bb
!= loop
->latch
);
2008 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2012 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2014 if (e
->src
== exit_bb
)
2021 if (exit_bb
!= NULL
)
2023 if (exit_bb
!= loop
->header
)
2025 /* Connect this node to loop header. */
2026 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2027 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2030 /* Redirect non-exit edges to loop->latch. */
2031 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2033 if (!loop_exit_edge_p (loop
, e
))
2034 redirect_edge_and_branch (e
, loop
->latch
);
2036 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2040 /* If the loop does not have an exit, reconnect header and latch. */
2041 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2042 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2045 merge_target_bb
= loop
->header
;
2046 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2048 gimple_stmt_iterator gsi
;
2049 gimple_stmt_iterator last
;
2053 if (bb
== exit_bb
|| bb
== loop
->latch
)
2056 /* Make stmts member of loop->header. */
2057 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2058 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2060 /* Update stmt list. */
2061 last
= gsi_last_bb (merge_target_bb
);
2062 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2063 set_bb_seq (bb
, NULL
);
2065 delete_basic_block (bb
);
2068 /* If possible, merge loop header to the block with the exit edge.
2069 This reduces the number of basic blocks to two, to please the
2070 vectorizer that handles only loops with two nodes. */
2072 && exit_bb
!= loop
->header
2073 && can_merge_blocks_p (loop
->header
, exit_bb
))
2074 merge_blocks (loop
->header
, exit_bb
);
2080 /* Version LOOP before if-converting it, the original loop
2081 will be then if-converted, the new copy of the loop will not,
2082 and the LOOP_VECTORIZED internal call will be guarding which
2083 loop to execute. The vectorizer pass will fold this
2084 internal call into either true or false. */
2087 version_loop_for_if_conversion (struct loop
*loop
)
2089 basic_block cond_bb
;
2090 tree cond
= make_ssa_name (boolean_type_node
, NULL
);
2091 struct loop
*new_loop
;
2093 gimple_stmt_iterator gsi
;
2095 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2096 build_int_cst (integer_type_node
, loop
->num
),
2098 gimple_call_set_lhs (g
, cond
);
2100 initialize_original_copy_tables ();
2101 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2102 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2103 REG_BR_PROB_BASE
, true);
2104 free_original_copy_tables ();
2105 if (new_loop
== NULL
)
2107 new_loop
->dont_vectorize
= true;
2108 new_loop
->force_vectorize
= false;
2109 gsi
= gsi_last_bb (cond_bb
);
2110 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2111 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2112 update_ssa (TODO_update_ssa
);
2116 /* If-convert LOOP when it is legal. For the moment this pass has no
2117 profitability analysis. Returns non-zero todo flags when something
2121 tree_if_conversion (struct loop
*loop
)
2123 unsigned int todo
= 0;
2125 bool any_mask_load_store
= false;
2127 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2128 || !dbg_cnt (if_conversion_tree
))
2131 if (any_mask_load_store
2132 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2133 || loop
->dont_vectorize
))
2136 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2139 /* Now all statements are if-convertible. Combine all the basic
2140 blocks into one huge basic block doing the if-conversion
2142 combine_blocks (loop
, any_mask_load_store
);
2144 todo
|= TODO_cleanup_cfg
;
2145 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2147 mark_virtual_operands_for_renaming (cfun
);
2148 todo
|= TODO_update_ssa_only_virtuals
;
2156 for (i
= 0; i
< loop
->num_nodes
; i
++)
2157 free_bb_predicate (ifc_bbs
[i
]);
2166 /* Tree if-conversion pass management. */
2170 const pass_data pass_data_if_conversion
=
2172 GIMPLE_PASS
, /* type */
2174 OPTGROUP_NONE
, /* optinfo_flags */
2175 TV_NONE
, /* tv_id */
2176 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2177 0, /* properties_provided */
2178 0, /* properties_destroyed */
2179 0, /* todo_flags_start */
2180 0, /* todo_flags_finish */
2183 class pass_if_conversion
: public gimple_opt_pass
2186 pass_if_conversion (gcc::context
*ctxt
)
2187 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2190 /* opt_pass methods: */
2191 virtual bool gate (function
*);
2192 virtual unsigned int execute (function
*);
2194 }; // class pass_if_conversion
2197 pass_if_conversion::gate (function
*fun
)
2199 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2200 && flag_tree_loop_if_convert
!= 0)
2201 || flag_tree_loop_if_convert
== 1
2202 || flag_tree_loop_if_convert_stores
== 1);
2206 pass_if_conversion::execute (function
*fun
)
2211 if (number_of_loops (fun
) <= 1)
2214 FOR_EACH_LOOP (loop
, 0)
2215 if (flag_tree_loop_if_convert
== 1
2216 || flag_tree_loop_if_convert_stores
== 1
2217 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2218 && !loop
->dont_vectorize
))
2219 todo
|= tree_if_conversion (loop
);
2221 #ifdef ENABLE_CHECKING
2224 FOR_EACH_BB_FN (bb
, fun
)
2225 gcc_assert (!bb
->aux
);
2235 make_pass_if_conversion (gcc::context
*ctxt
)
2237 return new pass_if_conversion (ctxt
);