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"
90 #include "double-int.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
101 #include "hard-reg-set.h"
102 #include "function.h"
103 #include "dominance.h"
105 #include "basic-block.h"
106 #include "gimple-pretty-print.h"
107 #include "tree-ssa-alias.h"
108 #include "internal-fn.h"
109 #include "gimple-fold.h"
110 #include "gimple-expr.h"
113 #include "gimplify.h"
114 #include "gimple-iterator.h"
115 #include "gimplify-me.h"
116 #include "gimple-ssa.h"
117 #include "tree-cfg.h"
118 #include "tree-phinodes.h"
119 #include "ssa-iterators.h"
120 #include "stringpool.h"
121 #include "tree-ssanames.h"
122 #include "tree-into-ssa.h"
123 #include "tree-ssa.h"
125 #include "tree-chrec.h"
126 #include "tree-data-ref.h"
127 #include "tree-scalar-evolution.h"
128 #include "tree-ssa-loop-ivopts.h"
129 #include "tree-ssa-address.h"
130 #include "tree-pass.h"
134 #include "statistics.h"
136 #include "fixed-value.h"
137 #include "insn-config.h"
142 #include "emit-rtl.h"
146 #include "insn-codes.h"
149 /* List of basic blocks in if-conversion-suitable order. */
150 static basic_block
*ifc_bbs
;
152 /* Structure used to predicate basic blocks. This is attached to the
153 ->aux field of the BBs in the loop to be if-converted. */
154 typedef struct bb_predicate_s
{
156 /* The condition under which this basic block is executed. */
159 /* PREDICATE is gimplified, and the sequence of statements is
160 recorded here, in order to avoid the duplication of computations
161 that occur in previous conditions. See PR44483. */
162 gimple_seq predicate_gimplified_stmts
;
165 /* Returns true when the basic block BB has a predicate. */
168 bb_has_predicate (basic_block bb
)
170 return bb
->aux
!= NULL
;
173 /* Returns the gimplified predicate for basic block BB. */
176 bb_predicate (basic_block bb
)
178 return ((bb_predicate_p
) bb
->aux
)->predicate
;
181 /* Sets the gimplified predicate COND for basic block BB. */
184 set_bb_predicate (basic_block bb
, tree cond
)
186 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
187 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
188 || is_gimple_condexpr (cond
));
189 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
192 /* Returns the sequence of statements of the gimplification of the
193 predicate for basic block BB. */
195 static inline gimple_seq
196 bb_predicate_gimplified_stmts (basic_block bb
)
198 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
201 /* Sets the sequence of statements STMTS of the gimplification of the
202 predicate for basic block BB. */
205 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
207 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
210 /* Adds the sequence of statements STMTS to the sequence of statements
211 of the predicate for basic block BB. */
214 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
217 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
220 /* Initializes to TRUE the predicate of basic block BB. */
223 init_bb_predicate (basic_block bb
)
225 bb
->aux
= XNEW (struct bb_predicate_s
);
226 set_bb_predicate_gimplified_stmts (bb
, NULL
);
227 set_bb_predicate (bb
, boolean_true_node
);
230 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
231 but don't actually free it. */
234 release_bb_predicate (basic_block bb
)
236 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
239 gimple_stmt_iterator i
;
241 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
242 free_stmt_operands (cfun
, gsi_stmt (i
));
243 set_bb_predicate_gimplified_stmts (bb
, NULL
);
247 /* Free the predicate of basic block BB. */
250 free_bb_predicate (basic_block bb
)
252 if (!bb_has_predicate (bb
))
255 release_bb_predicate (bb
);
260 /* Reinitialize predicate of BB with the true predicate. */
263 reset_bb_predicate (basic_block bb
)
265 if (!bb_has_predicate (bb
))
266 init_bb_predicate (bb
);
269 release_bb_predicate (bb
);
270 set_bb_predicate (bb
, boolean_true_node
);
274 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
275 the expression EXPR. Inserts the statement created for this
276 computation before GSI and leaves the iterator GSI at the same
280 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
282 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
283 gimple stmt
= gimple_build_assign (new_name
, expr
);
284 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
288 /* Return true when COND is a true predicate. */
291 is_true_predicate (tree cond
)
293 return (cond
== NULL_TREE
294 || cond
== boolean_true_node
295 || integer_onep (cond
));
298 /* Returns true when BB has a predicate that is not trivial: true or
302 is_predicated (basic_block bb
)
304 return !is_true_predicate (bb_predicate (bb
));
307 /* Parses the predicate COND and returns its comparison code and
308 operands OP0 and OP1. */
310 static enum tree_code
311 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
315 if (TREE_CODE (cond
) == SSA_NAME
316 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
318 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
320 *op0
= gimple_assign_rhs1 (s
);
321 *op1
= gimple_assign_rhs2 (s
);
322 return gimple_assign_rhs_code (s
);
325 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
327 tree op
= gimple_assign_rhs1 (s
);
328 tree type
= TREE_TYPE (op
);
329 enum tree_code code
= parse_predicate (op
, op0
, op1
);
331 return code
== ERROR_MARK
? ERROR_MARK
332 : invert_tree_comparison (code
, HONOR_NANS (type
));
338 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
)
340 *op0
= TREE_OPERAND (cond
, 0);
341 *op1
= TREE_OPERAND (cond
, 1);
342 return TREE_CODE (cond
);
348 /* Returns the fold of predicate C1 OR C2 at location LOC. */
351 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
353 tree op1a
, op1b
, op2a
, op2b
;
354 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
355 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
357 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
359 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
365 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
368 /* Returns true if N is either a constant or a SSA_NAME. */
371 constant_or_ssa_name (tree n
)
373 switch (TREE_CODE (n
))
386 /* Returns either a COND_EXPR or the folded expression if the folded
387 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
388 a constant or a SSA_NAME. */
391 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
393 tree rhs1
, lhs1
, cond_expr
;
394 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
397 if (cond_expr
== NULL_TREE
)
398 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
400 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
402 if (constant_or_ssa_name (cond_expr
))
405 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
407 rhs1
= TREE_OPERAND (cond_expr
, 1);
408 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
409 if (constant_or_ssa_name (rhs1
))
410 return build1 (ABS_EXPR
, type
, rhs1
);
413 if (TREE_CODE (cond_expr
) == MIN_EXPR
414 || TREE_CODE (cond_expr
) == MAX_EXPR
)
416 lhs1
= TREE_OPERAND (cond_expr
, 0);
417 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
418 rhs1
= TREE_OPERAND (cond_expr
, 1);
419 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
420 if (constant_or_ssa_name (rhs1
)
421 && constant_or_ssa_name (lhs1
))
422 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
424 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
427 /* Add condition NC to the predicate list of basic block BB. LOOP is
428 the loop to be if-converted. Use predicate of cd-equivalent block
429 for join bb if it exists: we call basic blocks bb1 and bb2
430 cd-equivalent if they are executed under the same condition. */
433 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
438 if (is_true_predicate (nc
))
441 /* If dominance tells us this basic block is always executed,
442 don't record any predicates for it. */
443 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
446 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
447 /* We use notion of cd equivalence to get simpler predicate for
448 join block, e.g. if join block has 2 predecessors with predicates
449 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
450 p1 & p2 | p1 & !p2. */
451 if (dom_bb
!= loop
->header
452 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
454 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
455 bc
= bb_predicate (dom_bb
);
456 if (!is_true_predicate (bc
))
457 set_bb_predicate (bb
, bc
);
459 gcc_assert (is_true_predicate (bb_predicate (bb
)));
460 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
461 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
462 dom_bb
->index
, bb
->index
);
466 if (!is_predicated (bb
))
470 bc
= bb_predicate (bb
);
471 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
472 if (is_true_predicate (bc
))
474 reset_bb_predicate (bb
);
479 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
480 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
481 tp
= &TREE_OPERAND (bc
, 0);
484 if (!is_gimple_condexpr (*tp
))
487 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
488 add_bb_predicate_gimplified_stmts (bb
, stmts
);
490 set_bb_predicate (bb
, bc
);
493 /* Add the condition COND to the previous condition PREV_COND, and add
494 this to the predicate list of the destination of edge E. LOOP is
495 the loop to be if-converted. */
498 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
499 tree prev_cond
, tree cond
)
501 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
504 if (!is_true_predicate (prev_cond
))
505 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
508 add_to_predicate_list (loop
, e
->dest
, cond
);
511 /* Return true if one of the successor edges of BB exits LOOP. */
514 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
519 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
520 if (loop_exit_edge_p (loop
, e
))
526 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
527 and it belongs to basic block BB.
529 PHI is not if-convertible if:
530 - it has more than 2 arguments.
532 When the flag_tree_loop_if_convert_stores is not set, PHI is not
534 - a virtual PHI is immediately used in another PHI node,
535 - there is a virtual PHI in a BB other than the loop->header. */
538 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
539 bool any_mask_load_store
)
541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
543 fprintf (dump_file
, "-------------------------\n");
544 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
547 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
550 fprintf (dump_file
, "More than two phi node args.\n");
554 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
557 /* When the flag_tree_loop_if_convert_stores is not set, check
558 that there are no memory writes in the branches of the loop to be
560 if (virtual_operand_p (gimple_phi_result (phi
)))
562 imm_use_iterator imm_iter
;
565 if (bb
!= loop
->header
)
567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
572 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
574 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
586 /* Records the status of a data reference. This struct is attached to
587 each DR->aux field. */
590 /* -1 when not initialized, 0 when false, 1 when true. */
591 int written_at_least_once
;
593 /* -1 when not initialized, 0 when false, 1 when true. */
594 int rw_unconditionally
;
597 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
598 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
599 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
601 /* Returns true when the memory references of STMT are read or written
602 unconditionally. In other words, this function returns true when
603 for every data reference A in STMT there exist other accesses to
604 a data reference with the same base with predicates that add up (OR-up) to
605 the true predicate: this ensures that the data reference A is touched
606 (read or written) on every iteration of the if-converted loop. */
609 memrefs_read_or_written_unconditionally (gimple stmt
,
610 vec
<data_reference_p
> drs
)
613 data_reference_p a
, b
;
614 tree ca
= bb_predicate (gimple_bb (stmt
));
616 for (i
= 0; drs
.iterate (i
, &a
); i
++)
617 if (DR_STMT (a
) == stmt
)
620 int x
= DR_RW_UNCONDITIONALLY (a
);
628 for (j
= 0; drs
.iterate (j
, &b
); j
++)
630 tree ref_base_a
= DR_REF (a
);
631 tree ref_base_b
= DR_REF (b
);
633 if (DR_STMT (b
) == stmt
)
636 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
637 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
638 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
639 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
641 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
642 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
643 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
644 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
646 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
648 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
650 if (DR_RW_UNCONDITIONALLY (b
) == 1
651 || is_true_predicate (cb
)
652 || is_true_predicate (ca
653 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
655 DR_RW_UNCONDITIONALLY (a
) = 1;
656 DR_RW_UNCONDITIONALLY (b
) = 1;
665 DR_RW_UNCONDITIONALLY (a
) = 0;
673 /* Returns true when the memory references of STMT are unconditionally
674 written. In other words, this function returns true when for every
675 data reference A written in STMT, there exist other writes to the
676 same data reference with predicates that add up (OR-up) to the true
677 predicate: this ensures that the data reference A is written on
678 every iteration of the if-converted loop. */
681 write_memrefs_written_at_least_once (gimple stmt
,
682 vec
<data_reference_p
> drs
)
685 data_reference_p a
, b
;
686 tree ca
= bb_predicate (gimple_bb (stmt
));
688 for (i
= 0; drs
.iterate (i
, &a
); i
++)
689 if (DR_STMT (a
) == stmt
693 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
701 for (j
= 0; drs
.iterate (j
, &b
); j
++)
702 if (DR_STMT (b
) != stmt
704 && same_data_refs_base_objects (a
, b
))
706 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
708 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
709 || is_true_predicate (cb
)
710 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
713 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
714 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
722 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
730 /* Return true when the memory references of STMT won't trap in the
731 if-converted code. There are two things that we have to check for:
733 - writes to memory occur to writable memory: if-conversion of
734 memory writes transforms the conditional memory writes into
735 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
736 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
737 be executed at all in the original code, it may be a readonly
738 memory. To check that A is not const-qualified, we check that
739 there exists at least an unconditional write to A in the current
742 - reads or writes to memory are valid memory accesses for every
743 iteration. To check that the memory accesses are correctly formed
744 and that we are allowed to read and write in these locations, we
745 check that the memory accesses to be if-converted occur at every
746 iteration unconditionally. */
749 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
751 return write_memrefs_written_at_least_once (stmt
, refs
)
752 && memrefs_read_or_written_unconditionally (stmt
, refs
);
755 /* Wrapper around gimple_could_trap_p refined for the needs of the
756 if-conversion. Try to prove that the memory accesses of STMT could
757 not trap in the innermost loop containing STMT. */
760 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
762 if (gimple_vuse (stmt
)
763 && !gimple_could_trap_p_1 (stmt
, false, false)
764 && ifcvt_memrefs_wont_trap (stmt
, refs
))
767 return gimple_could_trap_p (stmt
);
770 /* Return true if STMT could be converted into a masked load or store
771 (conditional load or store based on a mask computed from bb predicate). */
774 ifcvt_can_use_mask_load_store (gimple stmt
)
778 basic_block bb
= gimple_bb (stmt
);
781 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
782 || bb
->loop_father
->dont_vectorize
783 || !gimple_assign_single_p (stmt
)
784 || gimple_has_volatile_ops (stmt
))
787 /* Check whether this is a load or store. */
788 lhs
= gimple_assign_lhs (stmt
);
789 if (gimple_store_p (stmt
))
791 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
796 else if (gimple_assign_load_p (stmt
))
799 ref
= gimple_assign_rhs1 (stmt
);
804 if (may_be_nonaddressable_p (ref
))
807 /* Mask should be integer mode of the same size as the load/store
809 mode
= TYPE_MODE (TREE_TYPE (lhs
));
810 if (int_mode_for_mode (mode
) == BLKmode
811 || VECTOR_MODE_P (mode
))
814 if (can_vec_mask_load_store_p (mode
, is_load
))
820 /* Return true when STMT is if-convertible.
822 GIMPLE_ASSIGN statement is not if-convertible if,
825 - LHS is not var decl. */
828 if_convertible_gimple_assign_stmt_p (gimple stmt
,
829 vec
<data_reference_p
> refs
,
830 bool *any_mask_load_store
)
832 tree lhs
= gimple_assign_lhs (stmt
);
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "-------------------------\n");
838 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
841 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
844 /* Some of these constrains might be too conservative. */
845 if (stmt_ends_bb_p (stmt
)
846 || gimple_has_volatile_ops (stmt
)
847 || (TREE_CODE (lhs
) == SSA_NAME
848 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
849 || gimple_has_side_effects (stmt
))
851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
852 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
856 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
857 in between if_convertible_loop_p and combine_blocks
858 we can perform loop versioning. */
859 gimple_set_plf (stmt
, GF_PLF_2
, false);
861 if (flag_tree_loop_if_convert_stores
)
863 if (ifcvt_could_trap_p (stmt
, refs
))
865 if (ifcvt_can_use_mask_load_store (stmt
))
867 gimple_set_plf (stmt
, GF_PLF_2
, true);
868 *any_mask_load_store
= true;
871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
872 fprintf (dump_file
, "tree could trap...\n");
878 if (gimple_assign_rhs_could_trap_p (stmt
))
880 if (ifcvt_can_use_mask_load_store (stmt
))
882 gimple_set_plf (stmt
, GF_PLF_2
, true);
883 *any_mask_load_store
= true;
886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 fprintf (dump_file
, "tree could trap...\n");
891 bb
= gimple_bb (stmt
);
893 if (TREE_CODE (lhs
) != SSA_NAME
894 && bb
!= bb
->loop_father
->header
895 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
897 if (ifcvt_can_use_mask_load_store (stmt
))
899 gimple_set_plf (stmt
, GF_PLF_2
, true);
900 *any_mask_load_store
= true;
903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
905 fprintf (dump_file
, "LHS is not var\n");
906 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
914 /* Return true when STMT is if-convertible.
916 A statement is if-convertible if:
917 - it is an if-convertible GIMPLE_ASSIGN,
918 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
921 if_convertible_stmt_p (gimple stmt
, vec
<data_reference_p
> refs
,
922 bool *any_mask_load_store
)
924 switch (gimple_code (stmt
))
932 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
933 any_mask_load_store
);
937 tree fndecl
= gimple_call_fndecl (stmt
);
940 int flags
= gimple_call_flags (stmt
);
941 if ((flags
& ECF_CONST
)
942 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
943 /* We can only vectorize some builtins at the moment,
944 so restrict if-conversion to those. */
945 && DECL_BUILT_IN (fndecl
))
952 /* Don't know what to do with 'em so don't do anything. */
953 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
955 fprintf (dump_file
, "don't know what to do\n");
956 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
965 /* Return true when BB is if-convertible. This routine does not check
966 basic block's statements and phis.
968 A basic block is not if-convertible if:
969 - it is non-empty and it is after the exit block (in BFS order),
970 - it is after the exit block but before the latch,
971 - its edges are not normal.
973 EXIT_BB is the basic block containing the exit of the LOOP. BB is
977 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
983 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
985 if (EDGE_COUNT (bb
->preds
) > 2
986 || EDGE_COUNT (bb
->succs
) > 2)
991 if (bb
!= loop
->latch
)
993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
994 fprintf (dump_file
, "basic block after exit bb but before latch\n");
997 else if (!empty_block_p (bb
))
999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1000 fprintf (dump_file
, "non empty basic block after exit bb\n");
1003 else if (bb
== loop
->latch
1005 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1008 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1013 /* Be less adventurous and handle only normal edges. */
1014 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1015 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1018 fprintf (dump_file
, "Difficult to handle edges\n");
1022 /* At least one incoming edge has to be non-critical as otherwise edge
1023 predicates are not equal to basic-block predicates of the edge
1025 if (EDGE_COUNT (bb
->preds
) > 1
1026 && bb
!= loop
->header
)
1029 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1030 if (EDGE_COUNT (e
->src
->succs
) == 1)
1034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1035 fprintf (dump_file
, "only critical predecessors\n");
1043 /* Return true when all predecessor blocks of BB are visited. The
1044 VISITED bitmap keeps track of the visited blocks. */
1047 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1051 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1052 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1058 /* Get body of a LOOP in suitable order for if-conversion. It is
1059 caller's responsibility to deallocate basic block list.
1060 If-conversion suitable order is, breadth first sort (BFS) order
1061 with an additional constraint: select a block only if all its
1062 predecessors are already selected. */
1064 static basic_block
*
1065 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1067 basic_block
*blocks
, *blocks_in_bfs_order
;
1070 unsigned int index
= 0;
1071 unsigned int visited_count
= 0;
1073 gcc_assert (loop
->num_nodes
);
1074 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1076 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1077 visited
= BITMAP_ALLOC (NULL
);
1079 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1082 while (index
< loop
->num_nodes
)
1084 bb
= blocks_in_bfs_order
[index
];
1086 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1088 free (blocks_in_bfs_order
);
1089 BITMAP_FREE (visited
);
1094 if (!bitmap_bit_p (visited
, bb
->index
))
1096 if (pred_blocks_visited_p (bb
, &visited
)
1097 || bb
== loop
->header
)
1099 /* This block is now visited. */
1100 bitmap_set_bit (visited
, bb
->index
);
1101 blocks
[visited_count
++] = bb
;
1107 if (index
== loop
->num_nodes
1108 && visited_count
!= loop
->num_nodes
)
1112 free (blocks_in_bfs_order
);
1113 BITMAP_FREE (visited
);
1117 /* Returns true when the analysis of the predicates for all the basic
1118 blocks in LOOP succeeded.
1120 predicate_bbs first allocates the predicates of the basic blocks.
1121 These fields are then initialized with the tree expressions
1122 representing the predicates under which a basic block is executed
1123 in the LOOP. As the loop->header is executed at each iteration, it
1124 has the "true" predicate. Other statements executed under a
1125 condition are predicated with that condition, for example
1132 S1 will be predicated with "x", and
1133 S2 will be predicated with "!x". */
1136 predicate_bbs (loop_p loop
)
1140 for (i
= 0; i
< loop
->num_nodes
; i
++)
1141 init_bb_predicate (ifc_bbs
[i
]);
1143 for (i
= 0; i
< loop
->num_nodes
; i
++)
1145 basic_block bb
= ifc_bbs
[i
];
1149 /* The loop latch is always executed and has no extra conditions
1150 to be processed: skip it. */
1151 if (bb
== loop
->latch
)
1153 reset_bb_predicate (loop
->latch
);
1157 cond
= bb_predicate (bb
);
1158 stmt
= last_stmt (bb
);
1159 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1162 edge true_edge
, false_edge
;
1163 location_t loc
= gimple_location (stmt
);
1164 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
1166 gimple_cond_lhs (stmt
),
1167 gimple_cond_rhs (stmt
));
1169 /* Add new condition into destination's predicate list. */
1170 extract_true_false_edges_from_block (gimple_bb (stmt
),
1171 &true_edge
, &false_edge
);
1173 /* If C is true, then TRUE_EDGE is taken. */
1174 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1177 /* If C is false, then FALSE_EDGE is taken. */
1178 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1180 add_to_dst_predicate_list (loop
, false_edge
,
1181 unshare_expr (cond
), c2
);
1186 /* If current bb has only one successor, then consider it as an
1187 unconditional goto. */
1188 if (single_succ_p (bb
))
1190 basic_block bb_n
= single_succ (bb
);
1192 /* The successor bb inherits the predicate of its
1193 predecessor. If there is no predicate in the predecessor
1194 bb, then consider the successor bb as always executed. */
1195 if (cond
== NULL_TREE
)
1196 cond
= boolean_true_node
;
1198 add_to_predicate_list (loop
, bb_n
, cond
);
1202 /* The loop header is always executed. */
1203 reset_bb_predicate (loop
->header
);
1204 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1205 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1208 /* Return true when LOOP is if-convertible. This is a helper function
1209 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1210 in if_convertible_loop_p. */
1213 if_convertible_loop_p_1 (struct loop
*loop
,
1214 vec
<loop_p
> *loop_nest
,
1215 vec
<data_reference_p
> *refs
,
1216 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1220 basic_block exit_bb
= NULL
;
1222 /* Don't if-convert the loop when the data dependences cannot be
1223 computed: the loop won't be vectorized in that case. */
1224 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1228 calculate_dominance_info (CDI_DOMINATORS
);
1229 calculate_dominance_info (CDI_POST_DOMINATORS
);
1231 /* Allow statements that can be handled during if-conversion. */
1232 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1236 fprintf (dump_file
, "Irreducible loop\n");
1240 for (i
= 0; i
< loop
->num_nodes
; i
++)
1242 basic_block bb
= ifc_bbs
[i
];
1244 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1247 if (bb_with_exit_edge_p (loop
, bb
))
1251 for (i
= 0; i
< loop
->num_nodes
; i
++)
1253 basic_block bb
= ifc_bbs
[i
];
1254 gimple_stmt_iterator gsi
;
1256 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1257 switch (gimple_code (gsi_stmt (gsi
)))
1270 if (flag_tree_loop_if_convert_stores
)
1272 data_reference_p dr
;
1274 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1276 dr
->aux
= XNEW (struct ifc_dr
);
1277 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1278 DR_RW_UNCONDITIONALLY (dr
) = -1;
1280 predicate_bbs (loop
);
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 if (flag_tree_loop_if_convert_stores
)
1297 for (i
= 0; i
< loop
->num_nodes
; i
++)
1298 free_bb_predicate (ifc_bbs
[i
]);
1300 /* Checking PHIs needs to be done after stmts, as the fact whether there
1301 are any masked loads or stores affects the tests. */
1302 for (i
= 0; i
< loop
->num_nodes
; i
++)
1304 basic_block bb
= ifc_bbs
[i
];
1307 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1308 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1309 *any_mask_load_store
))
1314 fprintf (dump_file
, "Applying if-conversion\n");
1319 /* Return true when LOOP is if-convertible.
1320 LOOP is if-convertible if:
1322 - it has two or more basic blocks,
1323 - it has only one exit,
1324 - loop header is not the exit edge,
1325 - if its basic blocks and phi nodes are if convertible. */
1328 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1333 vec
<data_reference_p
> refs
;
1336 /* Handle only innermost loop. */
1337 if (!loop
|| loop
->inner
)
1339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1340 fprintf (dump_file
, "not innermost loop\n");
1344 /* If only one block, no need for if-conversion. */
1345 if (loop
->num_nodes
<= 2)
1347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1348 fprintf (dump_file
, "less than 2 basic blocks\n");
1352 /* More than one loop exit is too much to handle. */
1353 if (!single_exit (loop
))
1355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1356 fprintf (dump_file
, "multiple exits\n");
1360 /* If one of the loop header's edge is an exit edge then do not
1361 apply if-conversion. */
1362 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1363 if (loop_exit_edge_p (loop
, e
))
1368 auto_vec
<loop_p
, 3> loop_nest
;
1369 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1370 any_mask_load_store
);
1372 if (flag_tree_loop_if_convert_stores
)
1374 data_reference_p dr
;
1377 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1381 free_data_refs (refs
);
1382 free_dependence_relations (ddrs
);
1386 /* Basic block BB has two predecessors. Using predecessor's bb
1387 predicate, set an appropriate condition COND for the PHI node
1388 replacement. Return the true block whose phi arguments are
1389 selected when cond is true. LOOP is the loop containing the
1390 if-converted region, GSI is the place to insert the code for the
1394 find_phi_replacement_condition (basic_block bb
, tree
*cond
,
1395 gimple_stmt_iterator
*gsi
)
1397 edge first_edge
, second_edge
;
1400 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
1401 first_edge
= EDGE_PRED (bb
, 0);
1402 second_edge
= EDGE_PRED (bb
, 1);
1404 /* Prefer an edge with a not negated predicate.
1405 ??? That's a very weak cost model. */
1406 tmp_cond
= bb_predicate (first_edge
->src
);
1407 gcc_assert (tmp_cond
);
1408 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
1412 tmp_edge
= first_edge
;
1413 first_edge
= second_edge
;
1414 second_edge
= tmp_edge
;
1417 /* Check if the edge we take the condition from is not critical.
1418 We know that at least one non-critical edge exists. */
1419 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1421 *cond
= bb_predicate (second_edge
->src
);
1423 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
1424 *cond
= TREE_OPERAND (*cond
, 0);
1426 /* Select non loop header bb. */
1427 first_edge
= second_edge
;
1430 *cond
= bb_predicate (first_edge
->src
);
1432 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1433 *cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (*cond
),
1434 is_gimple_condexpr
, NULL_TREE
,
1435 true, GSI_SAME_STMT
);
1437 return first_edge
->src
;
1440 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1441 which is in predicated basic block.
1442 In fact, the following PHI pattern is searching:
1444 reduc_1 = PHI <..., reduc_2>
1448 reduc_2 = PHI <reduc_1, reduc_3>
1450 REDUC, OP0 and OP1 contain reduction stmt and its operands. */
1453 is_cond_scalar_reduction (gimple phi
, gimple
*reduc
,
1454 tree
*op0
, tree
*op1
)
1456 tree lhs
, r_op1
, r_op2
;
1459 gimple header_phi
= NULL
;
1460 enum tree_code reduction_op
;
1461 basic_block bb
= gimple_bb (phi
);
1462 struct loop
*loop
= bb
->loop_father
;
1463 edge latch_e
= loop_latch_edge (loop
);
1464 imm_use_iterator imm_iter
;
1465 use_operand_p use_p
;
1467 arg_0
= PHI_ARG_DEF (phi
, 0);
1468 arg_1
= PHI_ARG_DEF (phi
, 1);
1469 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1472 if (gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1475 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1476 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1478 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1481 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1482 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1486 if (gimple_bb (header_phi
) != loop
->header
)
1489 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1492 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1493 || gimple_has_volatile_ops (stmt
))
1496 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1499 if (!is_predicated (gimple_bb (stmt
)))
1502 /* Check that stmt-block is predecessor of phi-block. */
1503 if (EDGE_PRED (bb
, 0)->src
!= gimple_bb (stmt
)
1504 && EDGE_PRED (bb
, 1)->src
!= gimple_bb (stmt
))
1507 if (!has_single_use (lhs
))
1510 reduction_op
= gimple_assign_rhs_code (stmt
);
1511 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1513 r_op1
= gimple_assign_rhs1 (stmt
);
1514 r_op2
= gimple_assign_rhs2 (stmt
);
1516 /* Make R_OP1 to hold reduction variable. */
1517 if (r_op2
== PHI_RESULT (header_phi
)
1518 && reduction_op
== PLUS_EXPR
)
1524 else if (r_op1
!= PHI_RESULT (header_phi
))
1527 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1528 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1530 gimple use_stmt
= USE_STMT (use_p
);
1531 if (is_gimple_debug (use_stmt
))
1533 if (use_stmt
== stmt
)
1535 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1539 *op0
= r_op1
; *op1
= r_op2
;
1544 /* Converts conditional scalar reduction into unconditional form, e.g.
1546 if (_5 != 0) goto bb_5 else goto bb_6
1552 # res_2 = PHI <res_13(4), res_6(5)>
1555 will be converted into sequence
1556 _ifc__1 = _5 != 0 ? 1 : 0;
1557 res_2 = res_13 + _ifc__1;
1558 Argument SWAP tells that arguments of conditional expression should be
1560 Returns rhs of resulting PHI assignment. */
1563 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1564 tree cond
, tree op0
, tree op1
, bool swap
)
1566 gimple_stmt_iterator stmt_it
;
1569 tree rhs1
= gimple_assign_rhs1 (reduc
);
1570 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1572 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1574 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1576 fprintf (dump_file
, "Found cond scalar reduction.\n");
1577 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1580 /* Build cond expression using COND and constant operand
1581 of reduction rhs. */
1582 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1583 unshare_expr (cond
),
1587 /* Create assignment stmt and insert it at GSI. */
1588 new_assign
= gimple_build_assign (tmp
, c
);
1589 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1590 /* Build rhs for unconditional increment/decrement. */
1591 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1592 TREE_TYPE (rhs1
), op0
, tmp
);
1594 /* Delete original reduction stmt. */
1595 stmt_it
= gsi_for_stmt (reduc
);
1596 gsi_remove (&stmt_it
, true);
1597 release_defs (reduc
);
1601 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1602 This routine does not handle PHI nodes with more than two
1606 S1: A = PHI <x1(1), x2(5)>
1608 S2: A = cond ? x1 : x2;
1610 The generated code is inserted at GSI that points to the top of
1611 basic block's statement list. When COND is true, phi arg from
1612 TRUE_BB is selected. */
1615 predicate_scalar_phi (gphi
*phi
, tree cond
,
1616 basic_block true_bb
,
1617 gimple_stmt_iterator
*gsi
)
1621 tree rhs
, res
, arg
, scev
;
1623 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1624 && gimple_phi_num_args (phi
) == 2);
1626 res
= gimple_phi_result (phi
);
1627 /* Do not handle virtual phi nodes. */
1628 if (virtual_operand_p (res
))
1631 bb
= gimple_bb (phi
);
1633 if ((arg
= degenerate_phi_result (phi
))
1634 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1636 && !chrec_contains_undetermined (scev
)
1638 && (arg
= gimple_phi_arg_def (phi
, 0))))
1646 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1647 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1649 arg_0
= gimple_phi_arg_def (phi
, 1);
1650 arg_1
= gimple_phi_arg_def (phi
, 0);
1654 arg_0
= gimple_phi_arg_def (phi
, 0);
1655 arg_1
= gimple_phi_arg_def (phi
, 1);
1657 if (is_cond_scalar_reduction (phi
, &reduc
, &op0
, &op1
))
1658 /* Convert reduction stmt into vectorizable form. */
1659 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1660 true_bb
!= gimple_bb (reduc
));
1662 /* Build new RHS using selected condition and arguments. */
1663 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1667 new_stmt
= gimple_build_assign (res
, rhs
);
1668 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1669 update_stmt (new_stmt
);
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1673 fprintf (dump_file
, "new phi replacement stmt\n");
1674 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1678 /* Replaces in LOOP all the scalar phi nodes other than those in the
1679 LOOP->header block with conditional modify expressions. */
1682 predicate_all_scalar_phis (struct loop
*loop
)
1685 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1688 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1691 tree cond
= NULL_TREE
;
1692 gimple_stmt_iterator gsi
;
1693 gphi_iterator phi_gsi
;
1694 basic_block true_bb
= NULL
;
1697 if (bb
== loop
->header
)
1700 phi_gsi
= gsi_start_phis (bb
);
1701 if (gsi_end_p (phi_gsi
))
1704 /* BB has two predecessors. Using predecessor's aux field, set
1705 appropriate condition for the PHI node replacement. */
1706 gsi
= gsi_after_labels (bb
);
1707 true_bb
= find_phi_replacement_condition (bb
, &cond
, &gsi
);
1709 while (!gsi_end_p (phi_gsi
))
1711 phi
= phi_gsi
.phi ();
1712 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1713 release_phi_node (phi
);
1714 gsi_next (&phi_gsi
);
1717 set_phi_nodes (bb
, NULL
);
1721 /* Insert in each basic block of LOOP the statements produced by the
1722 gimplification of the predicates. */
1725 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1729 for (i
= 0; i
< loop
->num_nodes
; i
++)
1731 basic_block bb
= ifc_bbs
[i
];
1734 if (!is_predicated (bb
))
1736 /* Do not insert statements for a basic block that is not
1737 predicated. Also make sure that the predicate of the
1738 basic block is set to true. */
1739 reset_bb_predicate (bb
);
1743 stmts
= bb_predicate_gimplified_stmts (bb
);
1746 if (flag_tree_loop_if_convert_stores
1747 || any_mask_load_store
)
1749 /* Insert the predicate of the BB just after the label,
1750 as the if-conversion of memory writes will use this
1752 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1753 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1757 /* Insert the predicate of the BB at the end of the BB
1758 as this would reduce the register pressure: the only
1759 use of this predicate will be in successor BBs. */
1760 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1763 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1764 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1766 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1769 /* Once the sequence is code generated, set it to NULL. */
1770 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1775 /* Predicate each write to memory in LOOP.
1777 This function transforms control flow constructs containing memory
1780 | for (i = 0; i < N; i++)
1784 into the following form that does not contain control flow:
1786 | for (i = 0; i < N; i++)
1787 | A[i] = cond ? expr : A[i];
1789 The original CFG looks like this:
1796 | if (i < N) goto bb_5 else goto bb_2
1800 | cond = some_computation;
1801 | if (cond) goto bb_3 else goto bb_4
1813 insert_gimplified_predicates inserts the computation of the COND
1814 expression at the beginning of the destination basic block:
1821 | if (i < N) goto bb_5 else goto bb_2
1825 | cond = some_computation;
1826 | if (cond) goto bb_3 else goto bb_4
1830 | cond = some_computation;
1839 predicate_mem_writes is then predicating the memory write as follows:
1846 | if (i < N) goto bb_5 else goto bb_2
1850 | if (cond) goto bb_3 else goto bb_4
1854 | cond = some_computation;
1855 | A[i] = cond ? expr : A[i];
1863 and finally combine_blocks removes the basic block boundaries making
1864 the loop vectorizable:
1868 | if (i < N) goto bb_5 else goto bb_1
1872 | cond = some_computation;
1873 | A[i] = cond ? expr : A[i];
1874 | if (i < N) goto bb_5 else goto bb_4
1883 predicate_mem_writes (loop_p loop
)
1885 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1887 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1889 gimple_stmt_iterator gsi
;
1890 basic_block bb
= ifc_bbs
[i
];
1891 tree cond
= bb_predicate (bb
);
1895 if (is_true_predicate (cond
))
1899 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1902 cond
= TREE_OPERAND (cond
, 0);
1905 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1906 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
1908 else if (gimple_plf (stmt
, GF_PLF_2
))
1910 tree lhs
= gimple_assign_lhs (stmt
);
1911 tree rhs
= gimple_assign_rhs1 (stmt
);
1912 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
1914 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
1916 masktype
= build_nonstandard_integer_type (bitsize
, 1);
1917 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
1918 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
1919 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
1920 mark_addressable (ref
);
1921 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
1922 true, NULL_TREE
, true,
1924 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1925 is_gimple_condexpr
, NULL_TREE
,
1926 true, GSI_SAME_STMT
);
1927 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
1928 mask_op0
, mask_op1
);
1929 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
1930 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
1931 /* Copy points-to info if possible. */
1932 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
1933 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
1935 if (TREE_CODE (lhs
) == SSA_NAME
)
1938 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
1940 gimple_call_set_lhs (new_stmt
, lhs
);
1944 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
1946 gsi_replace (&gsi
, new_stmt
, true);
1948 else if (gimple_vdef (stmt
))
1950 tree lhs
= gimple_assign_lhs (stmt
);
1951 tree rhs
= gimple_assign_rhs1 (stmt
);
1952 tree type
= TREE_TYPE (lhs
);
1954 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1955 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1962 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1963 is_gimple_condexpr
, NULL_TREE
,
1964 true, GSI_SAME_STMT
);
1965 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
1966 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1972 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1973 other than the exit and latch of the LOOP. Also resets the
1974 GIMPLE_DEBUG information. */
1977 remove_conditions_and_labels (loop_p loop
)
1979 gimple_stmt_iterator gsi
;
1982 for (i
= 0; i
< loop
->num_nodes
; i
++)
1984 basic_block bb
= ifc_bbs
[i
];
1986 if (bb_with_exit_edge_p (loop
, bb
)
1987 || bb
== loop
->latch
)
1990 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1991 switch (gimple_code (gsi_stmt (gsi
)))
1995 gsi_remove (&gsi
, true);
1999 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2000 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2002 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2003 update_stmt (gsi_stmt (gsi
));
2014 /* Combine all the basic blocks from LOOP into one or two super basic
2015 blocks. Replace PHI nodes with conditional modify expressions. */
2018 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2020 basic_block bb
, exit_bb
, merge_target_bb
;
2021 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2026 predicate_bbs (loop
);
2027 remove_conditions_and_labels (loop
);
2028 insert_gimplified_predicates (loop
, any_mask_load_store
);
2029 predicate_all_scalar_phis (loop
);
2031 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2032 predicate_mem_writes (loop
);
2034 /* Merge basic blocks: first remove all the edges in the loop,
2035 except for those from the exit block. */
2037 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2040 free_bb_predicate (bb
);
2041 if (bb_with_exit_edge_p (loop
, bb
))
2043 gcc_assert (exit_bb
== NULL
);
2047 gcc_assert (exit_bb
!= loop
->latch
);
2049 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2053 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2055 if (e
->src
== exit_bb
)
2062 if (exit_bb
!= NULL
)
2064 if (exit_bb
!= loop
->header
)
2066 /* Connect this node to loop header. */
2067 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2068 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2071 /* Redirect non-exit edges to loop->latch. */
2072 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2074 if (!loop_exit_edge_p (loop
, e
))
2075 redirect_edge_and_branch (e
, loop
->latch
);
2077 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2081 /* If the loop does not have an exit, reconnect header and latch. */
2082 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2083 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2086 merge_target_bb
= loop
->header
;
2087 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2089 gimple_stmt_iterator gsi
;
2090 gimple_stmt_iterator last
;
2094 if (bb
== exit_bb
|| bb
== loop
->latch
)
2097 /* Make stmts member of loop->header. */
2098 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2099 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2101 /* Update stmt list. */
2102 last
= gsi_last_bb (merge_target_bb
);
2103 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2104 set_bb_seq (bb
, NULL
);
2106 delete_basic_block (bb
);
2109 /* If possible, merge loop header to the block with the exit edge.
2110 This reduces the number of basic blocks to two, to please the
2111 vectorizer that handles only loops with two nodes. */
2113 && exit_bb
!= loop
->header
2114 && can_merge_blocks_p (loop
->header
, exit_bb
))
2115 merge_blocks (loop
->header
, exit_bb
);
2121 /* Version LOOP before if-converting it, the original loop
2122 will be then if-converted, the new copy of the loop will not,
2123 and the LOOP_VECTORIZED internal call will be guarding which
2124 loop to execute. The vectorizer pass will fold this
2125 internal call into either true or false. */
2128 version_loop_for_if_conversion (struct loop
*loop
)
2130 basic_block cond_bb
;
2131 tree cond
= make_ssa_name (boolean_type_node
);
2132 struct loop
*new_loop
;
2134 gimple_stmt_iterator gsi
;
2136 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2137 build_int_cst (integer_type_node
, loop
->num
),
2139 gimple_call_set_lhs (g
, cond
);
2141 initialize_original_copy_tables ();
2142 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2143 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2144 REG_BR_PROB_BASE
, true);
2145 free_original_copy_tables ();
2146 if (new_loop
== NULL
)
2148 new_loop
->dont_vectorize
= true;
2149 new_loop
->force_vectorize
= false;
2150 gsi
= gsi_last_bb (cond_bb
);
2151 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2152 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2153 update_ssa (TODO_update_ssa
);
2157 /* If-convert LOOP when it is legal. For the moment this pass has no
2158 profitability analysis. Returns non-zero todo flags when something
2162 tree_if_conversion (struct loop
*loop
)
2164 unsigned int todo
= 0;
2166 bool any_mask_load_store
= false;
2168 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2169 || !dbg_cnt (if_conversion_tree
))
2172 if (any_mask_load_store
2173 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2174 || loop
->dont_vectorize
))
2177 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2180 /* Now all statements are if-convertible. Combine all the basic
2181 blocks into one huge basic block doing the if-conversion
2183 combine_blocks (loop
, any_mask_load_store
);
2185 todo
|= TODO_cleanup_cfg
;
2186 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2188 mark_virtual_operands_for_renaming (cfun
);
2189 todo
|= TODO_update_ssa_only_virtuals
;
2197 for (i
= 0; i
< loop
->num_nodes
; i
++)
2198 free_bb_predicate (ifc_bbs
[i
]);
2203 free_dominance_info (CDI_POST_DOMINATORS
);
2208 /* Tree if-conversion pass management. */
2212 const pass_data pass_data_if_conversion
=
2214 GIMPLE_PASS
, /* type */
2216 OPTGROUP_NONE
, /* optinfo_flags */
2217 TV_NONE
, /* tv_id */
2218 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2219 0, /* properties_provided */
2220 0, /* properties_destroyed */
2221 0, /* todo_flags_start */
2222 0, /* todo_flags_finish */
2225 class pass_if_conversion
: public gimple_opt_pass
2228 pass_if_conversion (gcc::context
*ctxt
)
2229 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2232 /* opt_pass methods: */
2233 virtual bool gate (function
*);
2234 virtual unsigned int execute (function
*);
2236 }; // class pass_if_conversion
2239 pass_if_conversion::gate (function
*fun
)
2241 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2242 && flag_tree_loop_if_convert
!= 0)
2243 || flag_tree_loop_if_convert
== 1
2244 || flag_tree_loop_if_convert_stores
== 1);
2248 pass_if_conversion::execute (function
*fun
)
2253 if (number_of_loops (fun
) <= 1)
2256 FOR_EACH_LOOP (loop
, 0)
2257 if (flag_tree_loop_if_convert
== 1
2258 || flag_tree_loop_if_convert_stores
== 1
2259 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2260 && !loop
->dont_vectorize
))
2261 todo
|= tree_if_conversion (loop
);
2263 #ifdef ENABLE_CHECKING
2266 FOR_EACH_BB_FN (bb
, fun
)
2267 gcc_assert (!bb
->aux
);
2277 make_pass_if_conversion (gcc::context
*ctxt
)
2279 return new pass_if_conversion (ctxt
);