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"
92 #include "fold-const.h"
93 #include "stor-layout.h"
95 #include "gimple-pretty-print.h"
96 #include "internal-fn.h"
97 #include "gimple-fold.h"
99 #include "gimple-iterator.h"
100 #include "gimplify-me.h"
101 #include "tree-cfg.h"
102 #include "tree-into-ssa.h"
103 #include "tree-ssa.h"
105 #include "tree-chrec.h"
106 #include "tree-data-ref.h"
107 #include "tree-scalar-evolution.h"
108 #include "tree-ssa-loop-ivopts.h"
109 #include "tree-ssa-address.h"
110 #include "tree-pass.h"
112 #include "insn-config.h"
117 #include "emit-rtl.h"
121 #include "insn-codes.h"
123 #include "tree-hash-traits.h"
125 /* List of basic blocks in if-conversion-suitable order. */
126 static basic_block
*ifc_bbs
;
128 /* Apply more aggressive (extended) if-conversion if true. */
129 static bool aggressive_if_conv
;
131 /* Structure used to predicate basic blocks. This is attached to the
132 ->aux field of the BBs in the loop to be if-converted. */
133 typedef struct bb_predicate_s
{
135 /* The condition under which this basic block is executed. */
138 /* PREDICATE is gimplified, and the sequence of statements is
139 recorded here, in order to avoid the duplication of computations
140 that occur in previous conditions. See PR44483. */
141 gimple_seq predicate_gimplified_stmts
;
144 /* Returns true when the basic block BB has a predicate. */
147 bb_has_predicate (basic_block bb
)
149 return bb
->aux
!= NULL
;
152 /* Returns the gimplified predicate for basic block BB. */
155 bb_predicate (basic_block bb
)
157 return ((bb_predicate_p
) bb
->aux
)->predicate
;
160 /* Sets the gimplified predicate COND for basic block BB. */
163 set_bb_predicate (basic_block bb
, tree cond
)
165 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
166 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
167 || is_gimple_condexpr (cond
));
168 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
171 /* Returns the sequence of statements of the gimplification of the
172 predicate for basic block BB. */
174 static inline gimple_seq
175 bb_predicate_gimplified_stmts (basic_block bb
)
177 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
180 /* Sets the sequence of statements STMTS of the gimplification of the
181 predicate for basic block BB. */
184 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
186 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
189 /* Adds the sequence of statements STMTS to the sequence of statements
190 of the predicate for basic block BB. */
193 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
196 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
199 /* Initializes to TRUE the predicate of basic block BB. */
202 init_bb_predicate (basic_block bb
)
204 bb
->aux
= XNEW (struct bb_predicate_s
);
205 set_bb_predicate_gimplified_stmts (bb
, NULL
);
206 set_bb_predicate (bb
, boolean_true_node
);
209 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
210 but don't actually free it. */
213 release_bb_predicate (basic_block bb
)
215 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
218 gimple_stmt_iterator i
;
220 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
221 free_stmt_operands (cfun
, gsi_stmt (i
));
222 set_bb_predicate_gimplified_stmts (bb
, NULL
);
226 /* Free the predicate of basic block BB. */
229 free_bb_predicate (basic_block bb
)
231 if (!bb_has_predicate (bb
))
234 release_bb_predicate (bb
);
239 /* Reinitialize predicate of BB with the true predicate. */
242 reset_bb_predicate (basic_block bb
)
244 if (!bb_has_predicate (bb
))
245 init_bb_predicate (bb
);
248 release_bb_predicate (bb
);
249 set_bb_predicate (bb
, boolean_true_node
);
253 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
254 the expression EXPR. Inserts the statement created for this
255 computation before GSI and leaves the iterator GSI at the same
259 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
261 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
262 gimple stmt
= gimple_build_assign (new_name
, expr
);
263 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
267 /* Return true when COND is a true predicate. */
270 is_true_predicate (tree cond
)
272 return (cond
== NULL_TREE
273 || cond
== boolean_true_node
274 || integer_onep (cond
));
277 /* Returns true when BB has a predicate that is not trivial: true or
281 is_predicated (basic_block bb
)
283 return !is_true_predicate (bb_predicate (bb
));
286 /* Parses the predicate COND and returns its comparison code and
287 operands OP0 and OP1. */
289 static enum tree_code
290 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
294 if (TREE_CODE (cond
) == SSA_NAME
295 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
297 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
299 *op0
= gimple_assign_rhs1 (s
);
300 *op1
= gimple_assign_rhs2 (s
);
301 return gimple_assign_rhs_code (s
);
304 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
306 tree op
= gimple_assign_rhs1 (s
);
307 tree type
= TREE_TYPE (op
);
308 enum tree_code code
= parse_predicate (op
, op0
, op1
);
310 return code
== ERROR_MARK
? ERROR_MARK
311 : invert_tree_comparison (code
, HONOR_NANS (type
));
317 if (COMPARISON_CLASS_P (cond
))
319 *op0
= TREE_OPERAND (cond
, 0);
320 *op1
= TREE_OPERAND (cond
, 1);
321 return TREE_CODE (cond
);
327 /* Returns the fold of predicate C1 OR C2 at location LOC. */
330 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
332 tree op1a
, op1b
, op2a
, op2b
;
333 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
334 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
336 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
338 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
344 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
347 /* Returns true if N is either a constant or a SSA_NAME. */
350 constant_or_ssa_name (tree n
)
352 switch (TREE_CODE (n
))
365 /* Returns either a COND_EXPR or the folded expression if the folded
366 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
367 a constant or a SSA_NAME. */
370 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
372 tree rhs1
, lhs1
, cond_expr
;
374 /* If COND is comparison r != 0 and r has boolean type, convert COND
375 to SSA_NAME to accept by vect bool pattern. */
376 if (TREE_CODE (cond
) == NE_EXPR
)
378 tree op0
= TREE_OPERAND (cond
, 0);
379 tree op1
= TREE_OPERAND (cond
, 1);
380 if (TREE_CODE (op0
) == SSA_NAME
381 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
382 && (integer_zerop (op1
)))
385 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
388 if (cond_expr
== NULL_TREE
)
389 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
391 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
393 if (constant_or_ssa_name (cond_expr
))
396 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
398 rhs1
= TREE_OPERAND (cond_expr
, 1);
399 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
400 if (constant_or_ssa_name (rhs1
))
401 return build1 (ABS_EXPR
, type
, rhs1
);
404 if (TREE_CODE (cond_expr
) == MIN_EXPR
405 || TREE_CODE (cond_expr
) == MAX_EXPR
)
407 lhs1
= TREE_OPERAND (cond_expr
, 0);
408 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
409 rhs1
= TREE_OPERAND (cond_expr
, 1);
410 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
411 if (constant_or_ssa_name (rhs1
)
412 && constant_or_ssa_name (lhs1
))
413 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
415 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
418 /* Add condition NC to the predicate list of basic block BB. LOOP is
419 the loop to be if-converted. Use predicate of cd-equivalent block
420 for join bb if it exists: we call basic blocks bb1 and bb2
421 cd-equivalent if they are executed under the same condition. */
424 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
429 if (is_true_predicate (nc
))
432 /* If dominance tells us this basic block is always executed,
433 don't record any predicates for it. */
434 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
437 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
438 /* We use notion of cd equivalence to get simpler predicate for
439 join block, e.g. if join block has 2 predecessors with predicates
440 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
441 p1 & p2 | p1 & !p2. */
442 if (dom_bb
!= loop
->header
443 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
445 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
446 bc
= bb_predicate (dom_bb
);
447 if (!is_true_predicate (bc
))
448 set_bb_predicate (bb
, bc
);
450 gcc_assert (is_true_predicate (bb_predicate (bb
)));
451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
452 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
453 dom_bb
->index
, bb
->index
);
457 if (!is_predicated (bb
))
461 bc
= bb_predicate (bb
);
462 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
463 if (is_true_predicate (bc
))
465 reset_bb_predicate (bb
);
470 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
471 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
472 tp
= &TREE_OPERAND (bc
, 0);
475 if (!is_gimple_condexpr (*tp
))
478 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
479 add_bb_predicate_gimplified_stmts (bb
, stmts
);
481 set_bb_predicate (bb
, bc
);
484 /* Add the condition COND to the previous condition PREV_COND, and add
485 this to the predicate list of the destination of edge E. LOOP is
486 the loop to be if-converted. */
489 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
490 tree prev_cond
, tree cond
)
492 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
495 if (!is_true_predicate (prev_cond
))
496 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
499 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
500 add_to_predicate_list (loop
, e
->dest
, cond
);
503 /* Return true if one of the successor edges of BB exits LOOP. */
506 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
511 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
512 if (loop_exit_edge_p (loop
, e
))
518 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
519 and it belongs to basic block BB.
521 PHI is not if-convertible if:
522 - it has more than 2 arguments.
524 When the flag_tree_loop_if_convert_stores is not set, PHI is not
526 - a virtual PHI is immediately used in another PHI node,
527 - there is a virtual PHI in a BB other than the loop->header.
528 When the aggressive_if_conv is set, PHI can have more than
532 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
533 bool any_mask_load_store
)
535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
537 fprintf (dump_file
, "-------------------------\n");
538 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
541 if (bb
!= loop
->header
)
543 if (gimple_phi_num_args (phi
) != 2
544 && !aggressive_if_conv
)
546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
547 fprintf (dump_file
, "More than two phi node args.\n");
552 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
555 /* When the flag_tree_loop_if_convert_stores is not set, check
556 that there are no memory writes in the branches of the loop to be
558 if (virtual_operand_p (gimple_phi_result (phi
)))
560 imm_use_iterator imm_iter
;
563 if (bb
!= loop
->header
)
565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
566 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
570 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
572 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
573 && USE_STMT (use_p
) != (gimple
) phi
)
575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
576 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
585 /* Records the status of a data reference. This struct is attached to
586 each DR->aux field. */
589 /* -1 when not initialized, 0 when false, 1 when true. */
590 int written_at_least_once
;
592 /* -1 when not initialized, 0 when false, 1 when true. */
593 int rw_unconditionally
;
596 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
597 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
598 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
600 /* Returns true when the memory references of STMT are read or written
601 unconditionally. In other words, this function returns true when
602 for every data reference A in STMT there exist other accesses to
603 a data reference with the same base with predicates that add up (OR-up) to
604 the true predicate: this ensures that the data reference A is touched
605 (read or written) on every iteration of the if-converted loop. */
608 memrefs_read_or_written_unconditionally (gimple stmt
,
609 vec
<data_reference_p
> drs
)
612 data_reference_p a
, b
;
613 tree ca
= bb_predicate (gimple_bb (stmt
));
615 for (i
= 0; drs
.iterate (i
, &a
); i
++)
616 if (DR_STMT (a
) == stmt
)
619 int x
= DR_RW_UNCONDITIONALLY (a
);
627 for (j
= 0; drs
.iterate (j
, &b
); j
++)
629 tree ref_base_a
= DR_REF (a
);
630 tree ref_base_b
= DR_REF (b
);
632 if (DR_STMT (b
) == stmt
)
635 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
636 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
637 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
638 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
640 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
641 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
642 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
643 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
645 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
647 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
649 if (DR_RW_UNCONDITIONALLY (b
) == 1
650 || is_true_predicate (cb
)
651 || is_true_predicate (ca
652 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
654 DR_RW_UNCONDITIONALLY (a
) = 1;
655 DR_RW_UNCONDITIONALLY (b
) = 1;
664 DR_RW_UNCONDITIONALLY (a
) = 0;
672 /* Returns true when the memory references of STMT are unconditionally
673 written. In other words, this function returns true when for every
674 data reference A written in STMT, there exist other writes to the
675 same data reference with predicates that add up (OR-up) to the true
676 predicate: this ensures that the data reference A is written on
677 every iteration of the if-converted loop. */
680 write_memrefs_written_at_least_once (gimple stmt
,
681 vec
<data_reference_p
> drs
)
684 data_reference_p a
, b
;
685 tree ca
= bb_predicate (gimple_bb (stmt
));
687 for (i
= 0; drs
.iterate (i
, &a
); i
++)
688 if (DR_STMT (a
) == stmt
692 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
700 for (j
= 0; drs
.iterate (j
, &b
); j
++)
701 if (DR_STMT (b
) != stmt
703 && same_data_refs_base_objects (a
, b
))
705 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
707 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
708 || is_true_predicate (cb
)
709 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
712 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
713 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
721 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
729 /* Return true when the memory references of STMT won't trap in the
730 if-converted code. There are two things that we have to check for:
732 - writes to memory occur to writable memory: if-conversion of
733 memory writes transforms the conditional memory writes into
734 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
735 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
736 be executed at all in the original code, it may be a readonly
737 memory. To check that A is not const-qualified, we check that
738 there exists at least an unconditional write to A in the current
741 - reads or writes to memory are valid memory accesses for every
742 iteration. To check that the memory accesses are correctly formed
743 and that we are allowed to read and write in these locations, we
744 check that the memory accesses to be if-converted occur at every
745 iteration unconditionally. */
748 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
750 return write_memrefs_written_at_least_once (stmt
, refs
)
751 && memrefs_read_or_written_unconditionally (stmt
, refs
);
754 /* Wrapper around gimple_could_trap_p refined for the needs of the
755 if-conversion. Try to prove that the memory accesses of STMT could
756 not trap in the innermost loop containing STMT. */
759 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
761 if (gimple_vuse (stmt
)
762 && !gimple_could_trap_p_1 (stmt
, false, false)
763 && ifcvt_memrefs_wont_trap (stmt
, refs
))
766 return gimple_could_trap_p (stmt
);
769 /* Return true if STMT could be converted into a masked load or store
770 (conditional load or store based on a mask computed from bb predicate). */
773 ifcvt_can_use_mask_load_store (gimple stmt
)
777 basic_block bb
= gimple_bb (stmt
);
780 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
781 || bb
->loop_father
->dont_vectorize
782 || !gimple_assign_single_p (stmt
)
783 || gimple_has_volatile_ops (stmt
))
786 /* Check whether this is a load or store. */
787 lhs
= gimple_assign_lhs (stmt
);
788 if (gimple_store_p (stmt
))
790 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
795 else if (gimple_assign_load_p (stmt
))
798 ref
= gimple_assign_rhs1 (stmt
);
803 if (may_be_nonaddressable_p (ref
))
806 /* Mask should be integer mode of the same size as the load/store
808 mode
= TYPE_MODE (TREE_TYPE (lhs
));
809 if (int_mode_for_mode (mode
) == BLKmode
810 || VECTOR_MODE_P (mode
))
813 if (can_vec_mask_load_store_p (mode
, is_load
))
819 /* Return true when STMT is if-convertible.
821 GIMPLE_ASSIGN statement is not if-convertible if,
824 - LHS is not var decl. */
827 if_convertible_gimple_assign_stmt_p (gimple stmt
,
828 vec
<data_reference_p
> refs
,
829 bool *any_mask_load_store
)
831 tree lhs
= gimple_assign_lhs (stmt
);
834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
836 fprintf (dump_file
, "-------------------------\n");
837 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
840 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
843 /* Some of these constrains might be too conservative. */
844 if (stmt_ends_bb_p (stmt
)
845 || gimple_has_volatile_ops (stmt
)
846 || (TREE_CODE (lhs
) == SSA_NAME
847 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
848 || gimple_has_side_effects (stmt
))
850 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
851 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
855 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
856 in between if_convertible_loop_p and combine_blocks
857 we can perform loop versioning. */
858 gimple_set_plf (stmt
, GF_PLF_2
, false);
860 if (flag_tree_loop_if_convert_stores
)
862 if (ifcvt_could_trap_p (stmt
, refs
))
864 if (ifcvt_can_use_mask_load_store (stmt
))
866 gimple_set_plf (stmt
, GF_PLF_2
, true);
867 *any_mask_load_store
= true;
870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
871 fprintf (dump_file
, "tree could trap...\n");
877 if (gimple_assign_rhs_could_trap_p (stmt
))
879 if (ifcvt_can_use_mask_load_store (stmt
))
881 gimple_set_plf (stmt
, GF_PLF_2
, true);
882 *any_mask_load_store
= true;
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
886 fprintf (dump_file
, "tree could trap...\n");
890 bb
= gimple_bb (stmt
);
892 if (TREE_CODE (lhs
) != SSA_NAME
893 && bb
!= bb
->loop_father
->header
894 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
896 if (ifcvt_can_use_mask_load_store (stmt
))
898 gimple_set_plf (stmt
, GF_PLF_2
, true);
899 *any_mask_load_store
= true;
902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
904 fprintf (dump_file
, "LHS is not var\n");
905 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
913 /* Return true when STMT is if-convertible.
915 A statement is if-convertible if:
916 - it is an if-convertible GIMPLE_ASSIGN,
917 - it is a GIMPLE_LABEL or a GIMPLE_COND,
918 - it is builtins call. */
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 /* Assumes that BB has more than 1 predecessors.
966 Returns false if at least one successor is not on critical edge
967 and true otherwise. */
970 all_preds_critical_p (basic_block bb
)
975 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
976 if (EDGE_COUNT (e
->src
->succs
) == 1)
981 /* Returns true if at least one successor in on critical edge. */
983 has_pred_critical_p (basic_block bb
)
988 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
989 if (EDGE_COUNT (e
->src
->succs
) > 1)
994 /* Return true when BB is if-convertible. This routine does not check
995 basic block's statements and phis.
997 A basic block is not if-convertible if:
998 - it is non-empty and it is after the exit block (in BFS order),
999 - it is after the exit block but before the latch,
1000 - its edges are not normal.
1002 Last restriction is valid if aggressive_if_conv is false.
1004 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1008 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1014 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1016 if (EDGE_COUNT (bb
->succs
) > 2)
1019 if (EDGE_COUNT (bb
->preds
) > 2
1020 && !aggressive_if_conv
)
1025 if (bb
!= loop
->latch
)
1027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1028 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1031 else if (!empty_block_p (bb
))
1033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1034 fprintf (dump_file
, "non empty basic block after exit bb\n");
1037 else if (bb
== loop
->latch
1039 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1042 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1047 /* Be less adventurous and handle only normal edges. */
1048 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1049 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1051 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1052 fprintf (dump_file
, "Difficult to handle edges\n");
1056 /* At least one incoming edge has to be non-critical as otherwise edge
1057 predicates are not equal to basic-block predicates of the edge
1058 source. This check is skipped if aggressive_if_conv is true. */
1059 if (!aggressive_if_conv
1060 && EDGE_COUNT (bb
->preds
) > 1
1061 && bb
!= loop
->header
1062 && all_preds_critical_p (bb
))
1064 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1065 fprintf (dump_file
, "only critical predecessors\n");
1072 /* Return true when all predecessor blocks of BB are visited. The
1073 VISITED bitmap keeps track of the visited blocks. */
1076 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1080 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1081 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1087 /* Get body of a LOOP in suitable order for if-conversion. It is
1088 caller's responsibility to deallocate basic block list.
1089 If-conversion suitable order is, breadth first sort (BFS) order
1090 with an additional constraint: select a block only if all its
1091 predecessors are already selected. */
1093 static basic_block
*
1094 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1096 basic_block
*blocks
, *blocks_in_bfs_order
;
1099 unsigned int index
= 0;
1100 unsigned int visited_count
= 0;
1102 gcc_assert (loop
->num_nodes
);
1103 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1105 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1106 visited
= BITMAP_ALLOC (NULL
);
1108 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1111 while (index
< loop
->num_nodes
)
1113 bb
= blocks_in_bfs_order
[index
];
1115 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1117 free (blocks_in_bfs_order
);
1118 BITMAP_FREE (visited
);
1123 if (!bitmap_bit_p (visited
, bb
->index
))
1125 if (pred_blocks_visited_p (bb
, &visited
)
1126 || bb
== loop
->header
)
1128 /* This block is now visited. */
1129 bitmap_set_bit (visited
, bb
->index
);
1130 blocks
[visited_count
++] = bb
;
1136 if (index
== loop
->num_nodes
1137 && visited_count
!= loop
->num_nodes
)
1141 free (blocks_in_bfs_order
);
1142 BITMAP_FREE (visited
);
1146 /* Returns true when the analysis of the predicates for all the basic
1147 blocks in LOOP succeeded.
1149 predicate_bbs first allocates the predicates of the basic blocks.
1150 These fields are then initialized with the tree expressions
1151 representing the predicates under which a basic block is executed
1152 in the LOOP. As the loop->header is executed at each iteration, it
1153 has the "true" predicate. Other statements executed under a
1154 condition are predicated with that condition, for example
1161 S1 will be predicated with "x", and
1162 S2 will be predicated with "!x". */
1165 predicate_bbs (loop_p loop
)
1169 for (i
= 0; i
< loop
->num_nodes
; i
++)
1170 init_bb_predicate (ifc_bbs
[i
]);
1172 for (i
= 0; i
< loop
->num_nodes
; i
++)
1174 basic_block bb
= ifc_bbs
[i
];
1178 /* The loop latch and loop exit block are always executed and
1179 have no extra conditions to be processed: skip them. */
1180 if (bb
== loop
->latch
1181 || bb_with_exit_edge_p (loop
, bb
))
1183 reset_bb_predicate (bb
);
1187 cond
= bb_predicate (bb
);
1188 stmt
= last_stmt (bb
);
1189 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1192 edge true_edge
, false_edge
;
1193 location_t loc
= gimple_location (stmt
);
1194 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1196 gimple_cond_lhs (stmt
),
1197 gimple_cond_rhs (stmt
));
1199 /* Add new condition into destination's predicate list. */
1200 extract_true_false_edges_from_block (gimple_bb (stmt
),
1201 &true_edge
, &false_edge
);
1203 /* If C is true, then TRUE_EDGE is taken. */
1204 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1207 /* If C is false, then FALSE_EDGE is taken. */
1208 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1210 add_to_dst_predicate_list (loop
, false_edge
,
1211 unshare_expr (cond
), c2
);
1216 /* If current bb has only one successor, then consider it as an
1217 unconditional goto. */
1218 if (single_succ_p (bb
))
1220 basic_block bb_n
= single_succ (bb
);
1222 /* The successor bb inherits the predicate of its
1223 predecessor. If there is no predicate in the predecessor
1224 bb, then consider the successor bb as always executed. */
1225 if (cond
== NULL_TREE
)
1226 cond
= boolean_true_node
;
1228 add_to_predicate_list (loop
, bb_n
, cond
);
1232 /* The loop header is always executed. */
1233 reset_bb_predicate (loop
->header
);
1234 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1235 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1238 /* Return true when LOOP is if-convertible. This is a helper function
1239 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1240 in if_convertible_loop_p. */
1243 if_convertible_loop_p_1 (struct loop
*loop
,
1244 vec
<loop_p
> *loop_nest
,
1245 vec
<data_reference_p
> *refs
,
1246 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1250 basic_block exit_bb
= NULL
;
1252 /* Don't if-convert the loop when the data dependences cannot be
1253 computed: the loop won't be vectorized in that case. */
1254 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1258 calculate_dominance_info (CDI_DOMINATORS
);
1259 calculate_dominance_info (CDI_POST_DOMINATORS
);
1261 /* Allow statements that can be handled during if-conversion. */
1262 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1266 fprintf (dump_file
, "Irreducible loop\n");
1270 for (i
= 0; i
< loop
->num_nodes
; i
++)
1272 basic_block bb
= ifc_bbs
[i
];
1274 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1277 if (bb_with_exit_edge_p (loop
, bb
))
1281 for (i
= 0; i
< loop
->num_nodes
; i
++)
1283 basic_block bb
= ifc_bbs
[i
];
1284 gimple_stmt_iterator gsi
;
1286 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1287 switch (gimple_code (gsi_stmt (gsi
)))
1300 if (flag_tree_loop_if_convert_stores
)
1302 data_reference_p dr
;
1304 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1306 dr
->aux
= XNEW (struct ifc_dr
);
1307 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1308 DR_RW_UNCONDITIONALLY (dr
) = -1;
1310 predicate_bbs (loop
);
1313 for (i
= 0; i
< loop
->num_nodes
; i
++)
1315 basic_block bb
= ifc_bbs
[i
];
1316 gimple_stmt_iterator itr
;
1318 /* Check the if-convertibility of statements in predicated BBs. */
1319 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1320 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1321 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1322 any_mask_load_store
))
1326 if (flag_tree_loop_if_convert_stores
)
1327 for (i
= 0; i
< loop
->num_nodes
; i
++)
1328 free_bb_predicate (ifc_bbs
[i
]);
1330 /* Checking PHIs needs to be done after stmts, as the fact whether there
1331 are any masked loads or stores affects the tests. */
1332 for (i
= 0; i
< loop
->num_nodes
; i
++)
1334 basic_block bb
= ifc_bbs
[i
];
1337 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1338 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1339 *any_mask_load_store
))
1344 fprintf (dump_file
, "Applying if-conversion\n");
1349 /* Return true when LOOP is if-convertible.
1350 LOOP is if-convertible if:
1352 - it has two or more basic blocks,
1353 - it has only one exit,
1354 - loop header is not the exit edge,
1355 - if its basic blocks and phi nodes are if convertible. */
1358 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1363 vec
<data_reference_p
> refs
;
1366 /* Handle only innermost loop. */
1367 if (!loop
|| loop
->inner
)
1369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1370 fprintf (dump_file
, "not innermost loop\n");
1374 /* If only one block, no need for if-conversion. */
1375 if (loop
->num_nodes
<= 2)
1377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1378 fprintf (dump_file
, "less than 2 basic blocks\n");
1382 /* More than one loop exit is too much to handle. */
1383 if (!single_exit (loop
))
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1386 fprintf (dump_file
, "multiple exits\n");
1390 /* If one of the loop header's edge is an exit edge then do not
1391 apply if-conversion. */
1392 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1393 if (loop_exit_edge_p (loop
, e
))
1398 auto_vec
<loop_p
, 3> loop_nest
;
1399 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1400 any_mask_load_store
);
1402 if (flag_tree_loop_if_convert_stores
)
1404 data_reference_p dr
;
1407 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1411 free_data_refs (refs
);
1412 free_dependence_relations (ddrs
);
1416 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1417 which is in predicated basic block.
1418 In fact, the following PHI pattern is searching:
1420 reduc_1 = PHI <..., reduc_2>
1424 reduc_2 = PHI <reduc_1, reduc_3>
1426 ARG_0 and ARG_1 are correspondent PHI arguments.
1427 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1428 EXTENDED is true if PHI has > 2 arguments. */
1431 is_cond_scalar_reduction (gimple phi
, gimple
*reduc
, tree arg_0
, tree arg_1
,
1432 tree
*op0
, tree
*op1
, bool extended
)
1434 tree lhs
, r_op1
, r_op2
;
1436 gimple header_phi
= NULL
;
1437 enum tree_code reduction_op
;
1438 basic_block bb
= gimple_bb (phi
);
1439 struct loop
*loop
= bb
->loop_father
;
1440 edge latch_e
= loop_latch_edge (loop
);
1441 imm_use_iterator imm_iter
;
1442 use_operand_p use_p
;
1445 bool result
= false;
1446 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1449 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1452 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1453 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1455 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1458 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1459 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1463 if (gimple_bb (header_phi
) != loop
->header
)
1466 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1469 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1470 || gimple_has_volatile_ops (stmt
))
1473 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1476 if (!is_predicated (gimple_bb (stmt
)))
1479 /* Check that stmt-block is predecessor of phi-block. */
1480 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1489 if (!has_single_use (lhs
))
1492 reduction_op
= gimple_assign_rhs_code (stmt
);
1493 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1495 r_op1
= gimple_assign_rhs1 (stmt
);
1496 r_op2
= gimple_assign_rhs2 (stmt
);
1498 /* Make R_OP1 to hold reduction variable. */
1499 if (r_op2
== PHI_RESULT (header_phi
)
1500 && reduction_op
== PLUS_EXPR
)
1501 std::swap (r_op1
, r_op2
);
1502 else if (r_op1
!= PHI_RESULT (header_phi
))
1505 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1506 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1508 gimple use_stmt
= USE_STMT (use_p
);
1509 if (is_gimple_debug (use_stmt
))
1511 if (use_stmt
== stmt
)
1513 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1517 *op0
= r_op1
; *op1
= r_op2
;
1522 /* Converts conditional scalar reduction into unconditional form, e.g.
1524 if (_5 != 0) goto bb_5 else goto bb_6
1530 # res_2 = PHI <res_13(4), res_6(5)>
1533 will be converted into sequence
1534 _ifc__1 = _5 != 0 ? 1 : 0;
1535 res_2 = res_13 + _ifc__1;
1536 Argument SWAP tells that arguments of conditional expression should be
1538 Returns rhs of resulting PHI assignment. */
1541 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1542 tree cond
, tree op0
, tree op1
, bool swap
)
1544 gimple_stmt_iterator stmt_it
;
1547 tree rhs1
= gimple_assign_rhs1 (reduc
);
1548 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1550 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1554 fprintf (dump_file
, "Found cond scalar reduction.\n");
1555 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1558 /* Build cond expression using COND and constant operand
1559 of reduction rhs. */
1560 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1561 unshare_expr (cond
),
1565 /* Create assignment stmt and insert it at GSI. */
1566 new_assign
= gimple_build_assign (tmp
, c
);
1567 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1568 /* Build rhs for unconditional increment/decrement. */
1569 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1570 TREE_TYPE (rhs1
), op0
, tmp
);
1572 /* Delete original reduction stmt. */
1573 stmt_it
= gsi_for_stmt (reduc
);
1574 gsi_remove (&stmt_it
, true);
1575 release_defs (reduc
);
1579 /* Produce condition for all occurrences of ARG in PHI node. */
1582 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1583 gimple_stmt_iterator
*gsi
)
1587 tree cond
= NULL_TREE
;
1591 len
= occur
->length ();
1592 gcc_assert (len
> 0);
1593 for (i
= 0; i
< len
; i
++)
1595 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1596 c
= bb_predicate (e
->src
);
1597 if (is_true_predicate (c
))
1599 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1600 is_gimple_condexpr
, NULL_TREE
,
1601 true, GSI_SAME_STMT
);
1602 if (cond
!= NULL_TREE
)
1604 /* Must build OR expression. */
1605 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1606 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1607 is_gimple_condexpr
, NULL_TREE
,
1608 true, GSI_SAME_STMT
);
1613 gcc_assert (cond
!= NULL_TREE
);
1617 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1618 This routine can handle PHI nodes with more than two arguments.
1621 S1: A = PHI <x1(1), x2(5)>
1623 S2: A = cond ? x1 : x2;
1625 The generated code is inserted at GSI that points to the top of
1626 basic block's statement list.
1627 If PHI node has more than two arguments a chain of conditional
1628 expression is produced. */
1632 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1634 gimple new_stmt
= NULL
, reduc
;
1635 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1637 unsigned int index0
;
1638 unsigned int max
, args_len
;
1643 res
= gimple_phi_result (phi
);
1644 if (virtual_operand_p (res
))
1647 if ((rhs
= degenerate_phi_result (phi
))
1648 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1650 && !chrec_contains_undetermined (scev
)
1652 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1656 fprintf (dump_file
, "Degenerate phi!\n");
1657 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1659 new_stmt
= gimple_build_assign (res
, rhs
);
1660 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1661 update_stmt (new_stmt
);
1665 bb
= gimple_bb (phi
);
1666 if (EDGE_COUNT (bb
->preds
) == 2)
1668 /* Predicate ordinary PHI node with 2 arguments. */
1669 edge first_edge
, second_edge
;
1670 basic_block true_bb
;
1671 first_edge
= EDGE_PRED (bb
, 0);
1672 second_edge
= EDGE_PRED (bb
, 1);
1673 cond
= bb_predicate (first_edge
->src
);
1674 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1675 std::swap (first_edge
, second_edge
);
1676 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1678 cond
= bb_predicate (second_edge
->src
);
1679 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1680 cond
= TREE_OPERAND (cond
, 0);
1682 first_edge
= second_edge
;
1685 cond
= bb_predicate (first_edge
->src
);
1686 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1687 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1688 is_gimple_condexpr
, NULL_TREE
,
1689 true, GSI_SAME_STMT
);
1690 true_bb
= first_edge
->src
;
1691 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1693 arg0
= gimple_phi_arg_def (phi
, 1);
1694 arg1
= gimple_phi_arg_def (phi
, 0);
1698 arg0
= gimple_phi_arg_def (phi
, 0);
1699 arg1
= gimple_phi_arg_def (phi
, 1);
1701 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1703 /* Convert reduction stmt into vectorizable form. */
1704 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1705 true_bb
!= gimple_bb (reduc
));
1707 /* Build new RHS using selected condition and arguments. */
1708 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1710 new_stmt
= gimple_build_assign (res
, rhs
);
1711 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1712 update_stmt (new_stmt
);
1714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1716 fprintf (dump_file
, "new phi replacement stmt\n");
1717 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1722 /* Create hashmap for PHI node which contain vector of argument indexes
1723 having the same value. */
1725 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1726 unsigned int num_args
= gimple_phi_num_args (phi
);
1728 /* Vector of different PHI argument values. */
1729 auto_vec
<tree
> args (num_args
);
1731 /* Compute phi_arg_map. */
1732 for (i
= 0; i
< num_args
; i
++)
1736 arg
= gimple_phi_arg_def (phi
, i
);
1737 if (!phi_arg_map
.get (arg
))
1738 args
.quick_push (arg
);
1739 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1742 /* Determine element with max number of occurrences. */
1745 args_len
= args
.length ();
1746 for (i
= 0; i
< args_len
; i
++)
1749 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1756 /* Put element with max number of occurences to the end of ARGS. */
1757 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1758 std::swap (args
[args_len
- 1], args
[max_ind
]);
1760 /* Handle one special case when number of arguments with different values
1761 is equal 2 and one argument has the only occurrence. Such PHI can be
1762 handled as if would have only 2 arguments. */
1763 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1766 indexes
= phi_arg_map
.get (args
[0]);
1767 index0
= (*indexes
)[0];
1770 e
= gimple_phi_arg_edge (phi
, index0
);
1771 cond
= bb_predicate (e
->src
);
1772 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1775 cond
= TREE_OPERAND (cond
, 0);
1777 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1778 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1779 is_gimple_condexpr
, NULL_TREE
,
1780 true, GSI_SAME_STMT
);
1781 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1783 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1787 /* Convert reduction stmt into vectorizable form. */
1788 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1790 new_stmt
= gimple_build_assign (res
, rhs
);
1791 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1792 update_stmt (new_stmt
);
1798 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1801 for (i
= 0; i
< args_len
; i
++)
1804 indexes
= phi_arg_map
.get (args
[i
]);
1805 if (i
!= args_len
- 1)
1806 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1809 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1810 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1812 new_stmt
= gimple_build_assign (lhs
, rhs
);
1813 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1814 update_stmt (new_stmt
);
1819 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1821 fprintf (dump_file
, "new extended phi replacement stmt\n");
1822 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1826 /* Replaces in LOOP all the scalar phi nodes other than those in the
1827 LOOP->header block with conditional modify expressions. */
1830 predicate_all_scalar_phis (struct loop
*loop
)
1833 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1836 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1839 gimple_stmt_iterator gsi
;
1840 gphi_iterator phi_gsi
;
1843 if (bb
== loop
->header
)
1846 if (EDGE_COUNT (bb
->preds
) == 1)
1849 phi_gsi
= gsi_start_phis (bb
);
1850 if (gsi_end_p (phi_gsi
))
1853 gsi
= gsi_after_labels (bb
);
1854 while (!gsi_end_p (phi_gsi
))
1856 phi
= phi_gsi
.phi ();
1857 predicate_scalar_phi (phi
, &gsi
);
1858 release_phi_node (phi
);
1859 gsi_next (&phi_gsi
);
1862 set_phi_nodes (bb
, NULL
);
1866 /* Insert in each basic block of LOOP the statements produced by the
1867 gimplification of the predicates. */
1870 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1874 for (i
= 0; i
< loop
->num_nodes
; i
++)
1876 basic_block bb
= ifc_bbs
[i
];
1878 if (!is_predicated (bb
))
1879 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1880 if (!is_predicated (bb
))
1882 /* Do not insert statements for a basic block that is not
1883 predicated. Also make sure that the predicate of the
1884 basic block is set to true. */
1885 reset_bb_predicate (bb
);
1889 stmts
= bb_predicate_gimplified_stmts (bb
);
1892 if (flag_tree_loop_if_convert_stores
1893 || any_mask_load_store
)
1895 /* Insert the predicate of the BB just after the label,
1896 as the if-conversion of memory writes will use this
1898 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1899 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1903 /* Insert the predicate of the BB at the end of the BB
1904 as this would reduce the register pressure: the only
1905 use of this predicate will be in successor BBs. */
1906 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1909 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1910 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1912 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1915 /* Once the sequence is code generated, set it to NULL. */
1916 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1921 /* Helper function for predicate_mem_writes. Returns index of existent
1922 mask if it was created for given SIZE and -1 otherwise. */
1925 mask_exists (int size
, vec
<int> vec
)
1929 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1935 /* Predicate each write to memory in LOOP.
1937 This function transforms control flow constructs containing memory
1940 | for (i = 0; i < N; i++)
1944 into the following form that does not contain control flow:
1946 | for (i = 0; i < N; i++)
1947 | A[i] = cond ? expr : A[i];
1949 The original CFG looks like this:
1956 | if (i < N) goto bb_5 else goto bb_2
1960 | cond = some_computation;
1961 | if (cond) goto bb_3 else goto bb_4
1973 insert_gimplified_predicates inserts the computation of the COND
1974 expression at the beginning of the destination basic block:
1981 | if (i < N) goto bb_5 else goto bb_2
1985 | cond = some_computation;
1986 | if (cond) goto bb_3 else goto bb_4
1990 | cond = some_computation;
1999 predicate_mem_writes is then predicating the memory write as follows:
2006 | if (i < N) goto bb_5 else goto bb_2
2010 | if (cond) goto bb_3 else goto bb_4
2014 | cond = some_computation;
2015 | A[i] = cond ? expr : A[i];
2023 and finally combine_blocks removes the basic block boundaries making
2024 the loop vectorizable:
2028 | if (i < N) goto bb_5 else goto bb_1
2032 | cond = some_computation;
2033 | A[i] = cond ? expr : A[i];
2034 | if (i < N) goto bb_5 else goto bb_4
2043 predicate_mem_writes (loop_p loop
)
2045 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2046 auto_vec
<int, 1> vect_sizes
;
2047 auto_vec
<tree
, 1> vect_masks
;
2049 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2051 gimple_stmt_iterator gsi
;
2052 basic_block bb
= ifc_bbs
[i
];
2053 tree cond
= bb_predicate (bb
);
2058 if (is_true_predicate (cond
))
2062 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2065 cond
= TREE_OPERAND (cond
, 0);
2068 vect_sizes
.truncate (0);
2069 vect_masks
.truncate (0);
2071 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2072 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2074 else if (gimple_plf (stmt
, GF_PLF_2
))
2076 tree lhs
= gimple_assign_lhs (stmt
);
2077 tree rhs
= gimple_assign_rhs1 (stmt
);
2078 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
2080 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2081 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2082 mark_addressable (ref
);
2083 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2084 true, NULL_TREE
, true,
2086 if (!vect_sizes
.is_empty ()
2087 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2088 /* Use created mask. */
2089 mask
= vect_masks
[index
];
2092 masktype
= build_nonstandard_integer_type (bitsize
, 1);
2093 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
2094 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
2095 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2098 true, GSI_SAME_STMT
);
2099 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
2100 mask_op0
, mask_op1
);
2101 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
2102 /* Save mask and its size for further use. */
2103 vect_sizes
.safe_push (bitsize
);
2104 vect_masks
.safe_push (mask
);
2106 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
2107 /* Copy points-to info if possible. */
2108 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2109 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2111 if (TREE_CODE (lhs
) == SSA_NAME
)
2114 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2116 gimple_call_set_lhs (new_stmt
, lhs
);
2120 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2122 gsi_replace (&gsi
, new_stmt
, true);
2124 else if (gimple_vdef (stmt
))
2126 tree lhs
= gimple_assign_lhs (stmt
);
2127 tree rhs
= gimple_assign_rhs1 (stmt
);
2128 tree type
= TREE_TYPE (lhs
);
2130 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2131 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2133 std::swap (lhs
, rhs
);
2134 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2135 is_gimple_condexpr
, NULL_TREE
,
2136 true, GSI_SAME_STMT
);
2137 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2138 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2144 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2145 other than the exit and latch of the LOOP. Also resets the
2146 GIMPLE_DEBUG information. */
2149 remove_conditions_and_labels (loop_p loop
)
2151 gimple_stmt_iterator gsi
;
2154 for (i
= 0; i
< loop
->num_nodes
; i
++)
2156 basic_block bb
= ifc_bbs
[i
];
2158 if (bb_with_exit_edge_p (loop
, bb
)
2159 || bb
== loop
->latch
)
2162 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2163 switch (gimple_code (gsi_stmt (gsi
)))
2167 gsi_remove (&gsi
, true);
2171 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2172 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2174 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2175 update_stmt (gsi_stmt (gsi
));
2186 /* Combine all the basic blocks from LOOP into one or two super basic
2187 blocks. Replace PHI nodes with conditional modify expressions. */
2190 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2192 basic_block bb
, exit_bb
, merge_target_bb
;
2193 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2198 predicate_bbs (loop
);
2199 remove_conditions_and_labels (loop
);
2200 insert_gimplified_predicates (loop
, any_mask_load_store
);
2201 predicate_all_scalar_phis (loop
);
2203 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2204 predicate_mem_writes (loop
);
2206 /* Merge basic blocks: first remove all the edges in the loop,
2207 except for those from the exit block. */
2209 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2212 free_bb_predicate (bb
);
2213 if (bb_with_exit_edge_p (loop
, bb
))
2215 gcc_assert (exit_bb
== NULL
);
2219 gcc_assert (exit_bb
!= loop
->latch
);
2221 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2225 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2227 if (e
->src
== exit_bb
)
2234 if (exit_bb
!= NULL
)
2236 if (exit_bb
!= loop
->header
)
2238 /* Connect this node to loop header. */
2239 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2240 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2243 /* Redirect non-exit edges to loop->latch. */
2244 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2246 if (!loop_exit_edge_p (loop
, e
))
2247 redirect_edge_and_branch (e
, loop
->latch
);
2249 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2253 /* If the loop does not have an exit, reconnect header and latch. */
2254 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2255 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2258 merge_target_bb
= loop
->header
;
2259 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2261 gimple_stmt_iterator gsi
;
2262 gimple_stmt_iterator last
;
2266 if (bb
== exit_bb
|| bb
== loop
->latch
)
2269 /* Make stmts member of loop->header. */
2270 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2271 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2273 /* Update stmt list. */
2274 last
= gsi_last_bb (merge_target_bb
);
2275 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2276 set_bb_seq (bb
, NULL
);
2278 delete_basic_block (bb
);
2281 /* If possible, merge loop header to the block with the exit edge.
2282 This reduces the number of basic blocks to two, to please the
2283 vectorizer that handles only loops with two nodes. */
2285 && exit_bb
!= loop
->header
2286 && can_merge_blocks_p (loop
->header
, exit_bb
))
2287 merge_blocks (loop
->header
, exit_bb
);
2293 /* Version LOOP before if-converting it, the original loop
2294 will be then if-converted, the new copy of the loop will not,
2295 and the LOOP_VECTORIZED internal call will be guarding which
2296 loop to execute. The vectorizer pass will fold this
2297 internal call into either true or false. */
2300 version_loop_for_if_conversion (struct loop
*loop
)
2302 basic_block cond_bb
;
2303 tree cond
= make_ssa_name (boolean_type_node
);
2304 struct loop
*new_loop
;
2306 gimple_stmt_iterator gsi
;
2308 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2309 build_int_cst (integer_type_node
, loop
->num
),
2311 gimple_call_set_lhs (g
, cond
);
2313 initialize_original_copy_tables ();
2314 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2315 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2316 REG_BR_PROB_BASE
, true);
2317 free_original_copy_tables ();
2318 if (new_loop
== NULL
)
2320 new_loop
->dont_vectorize
= true;
2321 new_loop
->force_vectorize
= false;
2322 gsi
= gsi_last_bb (cond_bb
);
2323 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2324 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2325 update_ssa (TODO_update_ssa
);
2329 /* Performs splitting of critical edges if aggressive_if_conv is true.
2330 Returns false if loop won't be if converted and true otherwise. */
2333 ifcvt_split_critical_edges (struct loop
*loop
)
2337 unsigned int num
= loop
->num_nodes
;
2347 if (!single_exit (loop
))
2350 body
= get_loop_body (loop
);
2351 for (i
= 0; i
< num
; i
++)
2354 if (bb
== loop
->latch
2355 || bb_with_exit_edge_p (loop
, bb
))
2357 stmt
= last_stmt (bb
);
2358 /* Skip basic blocks not ending with conditional branch. */
2359 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2361 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2362 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2369 /* Assumes that lhs of DEF_STMT have multiple uses.
2370 Delete one use by (1) creation of copy DEF_STMT with
2371 unique lhs; (2) change original use of lhs in one
2372 use statement with newly created lhs. */
2375 ifcvt_split_def_stmt (gimple def_stmt
, gimple use_stmt
)
2380 gimple_stmt_iterator gsi
;
2381 use_operand_p use_p
;
2382 imm_use_iterator imm_iter
;
2384 var
= gimple_assign_lhs (def_stmt
);
2385 copy_stmt
= gimple_copy (def_stmt
);
2386 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2387 gimple_assign_set_lhs (copy_stmt
, lhs
);
2388 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2389 /* Insert copy of DEF_STMT. */
2390 gsi
= gsi_for_stmt (def_stmt
);
2391 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2392 /* Change use of var to lhs in use_stmt. */
2393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2395 fprintf (dump_file
, "Change use of var ");
2396 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2397 fprintf (dump_file
, " to ");
2398 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2399 fprintf (dump_file
, "\n");
2401 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2403 if (USE_STMT (use_p
) != use_stmt
)
2405 SET_USE (use_p
, lhs
);
2410 /* Traverse bool pattern recursively starting from VAR.
2411 Save its def and use statements to defuse_list if VAR does
2412 not have single use. */
2415 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
> *defuse_list
,
2419 enum tree_code code
;
2422 def_stmt
= SSA_NAME_DEF_STMT (var
);
2423 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2425 if (!has_single_use (var
))
2427 /* Put def and use stmts into defuse_list. */
2428 defuse_list
->safe_push (def_stmt
);
2429 defuse_list
->safe_push (use_stmt
);
2430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2432 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2433 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2436 rhs1
= gimple_assign_rhs1 (def_stmt
);
2437 code
= gimple_assign_rhs_code (def_stmt
);
2441 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2444 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2445 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2446 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2448 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2451 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2456 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2457 rhs2
= gimple_assign_rhs2 (def_stmt
);
2458 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2466 /* Returns true if STMT can be a root of bool pattern apllied
2470 stmt_is_root_of_bool_pattern (gimple stmt
)
2472 enum tree_code code
;
2475 code
= gimple_assign_rhs_code (stmt
);
2476 if (CONVERT_EXPR_CODE_P (code
))
2478 lhs
= gimple_assign_lhs (stmt
);
2479 rhs
= gimple_assign_rhs1 (stmt
);
2480 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2482 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2486 else if (code
== COND_EXPR
)
2488 rhs
= gimple_assign_rhs1 (stmt
);
2489 if (TREE_CODE (rhs
) != SSA_NAME
)
2496 /* Traverse all statements in BB which correspondent to loop header to
2497 find out all statements which can start bool pattern applied by
2498 vectorizer and convert multiple uses in it to conform pattern
2499 restrictions. Such case can occur if the same predicate is used both
2500 for phi node conversion and load/store mask. */
2503 ifcvt_repair_bool_pattern (basic_block bb
)
2507 gimple_stmt_iterator gsi
;
2508 vec
<gimple
> defuse_list
= vNULL
;
2509 vec
<gimple
> pattern_roots
= vNULL
;
2514 /* Collect all root pattern statements. */
2515 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2517 stmt
= gsi_stmt (gsi
);
2518 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2520 if (!stmt_is_root_of_bool_pattern (stmt
))
2522 pattern_roots
.safe_push (stmt
);
2525 if (pattern_roots
.is_empty ())
2528 /* Split all statements with multiple uses iteratively since splitting
2529 may create new multiple uses. */
2534 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2536 rhs
= gimple_assign_rhs1 (stmt
);
2537 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2538 while (defuse_list
.length () > 0)
2541 gimple def_stmt
, use_stmt
;
2542 use_stmt
= defuse_list
.pop ();
2543 def_stmt
= defuse_list
.pop ();
2544 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2550 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2554 /* Delete redundant statements produced by predication which prevents
2555 loop vectorization. */
2558 ifcvt_local_dce (basic_block bb
)
2563 gimple_stmt_iterator gsi
;
2564 vec
<gimple
> worklist
;
2565 enum gimple_code code
;
2566 use_operand_p use_p
;
2567 imm_use_iterator imm_iter
;
2569 worklist
.create (64);
2570 /* Consider all phi as live statements. */
2571 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2573 phi
= gsi_stmt (gsi
);
2574 gimple_set_plf (phi
, GF_PLF_2
, true);
2575 worklist
.safe_push (phi
);
2577 /* Consider load/store statemnts, CALL and COND as live. */
2578 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2580 stmt
= gsi_stmt (gsi
);
2581 if (gimple_store_p (stmt
)
2582 || gimple_assign_load_p (stmt
)
2583 || is_gimple_debug (stmt
))
2585 gimple_set_plf (stmt
, GF_PLF_2
, true);
2586 worklist
.safe_push (stmt
);
2589 code
= gimple_code (stmt
);
2590 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2592 gimple_set_plf (stmt
, GF_PLF_2
, true);
2593 worklist
.safe_push (stmt
);
2596 gimple_set_plf (stmt
, GF_PLF_2
, false);
2598 if (code
== GIMPLE_ASSIGN
)
2600 tree lhs
= gimple_assign_lhs (stmt
);
2601 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2603 stmt1
= USE_STMT (use_p
);
2604 if (gimple_bb (stmt1
) != bb
)
2606 gimple_set_plf (stmt
, GF_PLF_2
, true);
2607 worklist
.safe_push (stmt
);
2613 /* Propagate liveness through arguments of live stmt. */
2614 while (worklist
.length () > 0)
2617 use_operand_p use_p
;
2620 stmt
= worklist
.pop ();
2621 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2623 use
= USE_FROM_PTR (use_p
);
2624 if (TREE_CODE (use
) != SSA_NAME
)
2626 stmt1
= SSA_NAME_DEF_STMT (use
);
2627 if (gimple_bb (stmt1
) != bb
2628 || gimple_plf (stmt1
, GF_PLF_2
))
2630 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2631 worklist
.safe_push (stmt1
);
2634 /* Delete dead statements. */
2635 gsi
= gsi_start_bb (bb
);
2636 while (!gsi_end_p (gsi
))
2638 stmt
= gsi_stmt (gsi
);
2639 if (gimple_plf (stmt
, GF_PLF_2
))
2644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2646 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2647 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2649 gsi_remove (&gsi
, true);
2650 release_defs (stmt
);
2654 /* If-convert LOOP when it is legal. For the moment this pass has no
2655 profitability analysis. Returns non-zero todo flags when something
2659 tree_if_conversion (struct loop
*loop
)
2661 unsigned int todo
= 0;
2663 bool any_mask_load_store
= false;
2665 /* Set-up aggressive if-conversion for loops marked with simd pragma. */
2666 aggressive_if_conv
= loop
->force_vectorize
;
2667 /* Check either outer loop was marked with simd pragma. */
2668 if (!aggressive_if_conv
)
2670 struct loop
*outer_loop
= loop_outer (loop
);
2671 if (outer_loop
&& outer_loop
->force_vectorize
)
2672 aggressive_if_conv
= true;
2675 if (aggressive_if_conv
)
2676 if (!ifcvt_split_critical_edges (loop
))
2679 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2680 || !dbg_cnt (if_conversion_tree
))
2683 if (any_mask_load_store
2684 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2685 || loop
->dont_vectorize
))
2688 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2691 /* Now all statements are if-convertible. Combine all the basic
2692 blocks into one huge basic block doing the if-conversion
2694 combine_blocks (loop
, any_mask_load_store
);
2696 /* Delete dead predicate computations and repair tree correspondent
2697 to bool pattern to delete multiple uses of preidcates. */
2698 if (aggressive_if_conv
)
2700 ifcvt_local_dce (loop
->header
);
2701 ifcvt_repair_bool_pattern (loop
->header
);
2704 todo
|= TODO_cleanup_cfg
;
2705 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2707 mark_virtual_operands_for_renaming (cfun
);
2708 todo
|= TODO_update_ssa_only_virtuals
;
2716 for (i
= 0; i
< loop
->num_nodes
; i
++)
2717 free_bb_predicate (ifc_bbs
[i
]);
2722 free_dominance_info (CDI_POST_DOMINATORS
);
2727 /* Tree if-conversion pass management. */
2731 const pass_data pass_data_if_conversion
=
2733 GIMPLE_PASS
, /* type */
2735 OPTGROUP_NONE
, /* optinfo_flags */
2736 TV_NONE
, /* tv_id */
2737 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2738 0, /* properties_provided */
2739 0, /* properties_destroyed */
2740 0, /* todo_flags_start */
2741 0, /* todo_flags_finish */
2744 class pass_if_conversion
: public gimple_opt_pass
2747 pass_if_conversion (gcc::context
*ctxt
)
2748 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2751 /* opt_pass methods: */
2752 virtual bool gate (function
*);
2753 virtual unsigned int execute (function
*);
2755 }; // class pass_if_conversion
2758 pass_if_conversion::gate (function
*fun
)
2760 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2761 && flag_tree_loop_if_convert
!= 0)
2762 || flag_tree_loop_if_convert
== 1
2763 || flag_tree_loop_if_convert_stores
== 1);
2767 pass_if_conversion::execute (function
*fun
)
2772 if (number_of_loops (fun
) <= 1)
2775 FOR_EACH_LOOP (loop
, 0)
2776 if (flag_tree_loop_if_convert
== 1
2777 || flag_tree_loop_if_convert_stores
== 1
2778 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2779 && !loop
->dont_vectorize
))
2780 todo
|= tree_if_conversion (loop
);
2782 #ifdef ENABLE_CHECKING
2785 FOR_EACH_BB_FN (bb
, fun
)
2786 gcc_assert (!bb
->aux
);
2796 make_pass_if_conversion (gcc::context
*ctxt
)
2798 return new pass_if_conversion (ctxt
);