1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
91 #include "fold-const.h"
92 #include "stor-layout.h"
95 #include "hard-reg-set.h"
97 #include "dominance.h"
99 #include "basic-block.h"
100 #include "gimple-pretty-print.h"
101 #include "tree-ssa-alias.h"
102 #include "internal-fn.h"
103 #include "gimple-fold.h"
104 #include "gimple-expr.h"
107 #include "gimplify.h"
108 #include "gimple-iterator.h"
109 #include "gimplify-me.h"
110 #include "gimple-ssa.h"
111 #include "tree-cfg.h"
112 #include "tree-phinodes.h"
113 #include "ssa-iterators.h"
114 #include "stringpool.h"
115 #include "tree-ssanames.h"
116 #include "tree-into-ssa.h"
117 #include "tree-ssa.h"
119 #include "tree-chrec.h"
120 #include "tree-data-ref.h"
121 #include "tree-scalar-evolution.h"
122 #include "tree-ssa-loop-ivopts.h"
123 #include "tree-ssa-address.h"
124 #include "tree-pass.h"
127 #include "insn-config.h"
132 #include "emit-rtl.h"
136 #include "insn-codes.h"
139 /* List of basic blocks in if-conversion-suitable order. */
140 static basic_block
*ifc_bbs
;
142 /* Apply more aggressive (extended) if-conversion if true. */
143 static bool aggressive_if_conv
;
145 /* Structure used to predicate basic blocks. This is attached to the
146 ->aux field of the BBs in the loop to be if-converted. */
147 typedef struct bb_predicate_s
{
149 /* The condition under which this basic block is executed. */
152 /* PREDICATE is gimplified, and the sequence of statements is
153 recorded here, in order to avoid the duplication of computations
154 that occur in previous conditions. See PR44483. */
155 gimple_seq predicate_gimplified_stmts
;
158 /* Returns true when the basic block BB has a predicate. */
161 bb_has_predicate (basic_block bb
)
163 return bb
->aux
!= NULL
;
166 /* Returns the gimplified predicate for basic block BB. */
169 bb_predicate (basic_block bb
)
171 return ((bb_predicate_p
) bb
->aux
)->predicate
;
174 /* Sets the gimplified predicate COND for basic block BB. */
177 set_bb_predicate (basic_block bb
, tree cond
)
179 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
180 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
181 || is_gimple_condexpr (cond
));
182 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
185 /* Returns the sequence of statements of the gimplification of the
186 predicate for basic block BB. */
188 static inline gimple_seq
189 bb_predicate_gimplified_stmts (basic_block bb
)
191 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
194 /* Sets the sequence of statements STMTS of the gimplification of the
195 predicate for basic block BB. */
198 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
200 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
203 /* Adds the sequence of statements STMTS to the sequence of statements
204 of the predicate for basic block BB. */
207 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
210 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
213 /* Initializes to TRUE the predicate of basic block BB. */
216 init_bb_predicate (basic_block bb
)
218 bb
->aux
= XNEW (struct bb_predicate_s
);
219 set_bb_predicate_gimplified_stmts (bb
, NULL
);
220 set_bb_predicate (bb
, boolean_true_node
);
223 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
224 but don't actually free it. */
227 release_bb_predicate (basic_block bb
)
229 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
232 gimple_stmt_iterator i
;
234 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
235 free_stmt_operands (cfun
, gsi_stmt (i
));
236 set_bb_predicate_gimplified_stmts (bb
, NULL
);
240 /* Free the predicate of basic block BB. */
243 free_bb_predicate (basic_block bb
)
245 if (!bb_has_predicate (bb
))
248 release_bb_predicate (bb
);
253 /* Reinitialize predicate of BB with the true predicate. */
256 reset_bb_predicate (basic_block bb
)
258 if (!bb_has_predicate (bb
))
259 init_bb_predicate (bb
);
262 release_bb_predicate (bb
);
263 set_bb_predicate (bb
, boolean_true_node
);
267 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
268 the expression EXPR. Inserts the statement created for this
269 computation before GSI and leaves the iterator GSI at the same
273 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
275 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
276 gimple stmt
= gimple_build_assign (new_name
, expr
);
277 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
281 /* Return true when COND is a true predicate. */
284 is_true_predicate (tree cond
)
286 return (cond
== NULL_TREE
287 || cond
== boolean_true_node
288 || integer_onep (cond
));
291 /* Returns true when BB has a predicate that is not trivial: true or
295 is_predicated (basic_block bb
)
297 return !is_true_predicate (bb_predicate (bb
));
300 /* Parses the predicate COND and returns its comparison code and
301 operands OP0 and OP1. */
303 static enum tree_code
304 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
308 if (TREE_CODE (cond
) == SSA_NAME
309 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
311 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
313 *op0
= gimple_assign_rhs1 (s
);
314 *op1
= gimple_assign_rhs2 (s
);
315 return gimple_assign_rhs_code (s
);
318 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
320 tree op
= gimple_assign_rhs1 (s
);
321 tree type
= TREE_TYPE (op
);
322 enum tree_code code
= parse_predicate (op
, op0
, op1
);
324 return code
== ERROR_MARK
? ERROR_MARK
325 : invert_tree_comparison (code
, HONOR_NANS (type
));
331 if (COMPARISON_CLASS_P (cond
))
333 *op0
= TREE_OPERAND (cond
, 0);
334 *op1
= TREE_OPERAND (cond
, 1);
335 return TREE_CODE (cond
);
341 /* Returns the fold of predicate C1 OR C2 at location LOC. */
344 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
346 tree op1a
, op1b
, op2a
, op2b
;
347 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
348 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
350 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
352 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
358 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
361 /* Returns true if N is either a constant or a SSA_NAME. */
364 constant_or_ssa_name (tree n
)
366 switch (TREE_CODE (n
))
379 /* Returns either a COND_EXPR or the folded expression if the folded
380 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
381 a constant or a SSA_NAME. */
384 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
386 tree rhs1
, lhs1
, cond_expr
;
388 /* If COND is comparison r != 0 and r has boolean type, convert COND
389 to SSA_NAME to accept by vect bool pattern. */
390 if (TREE_CODE (cond
) == NE_EXPR
)
392 tree op0
= TREE_OPERAND (cond
, 0);
393 tree op1
= TREE_OPERAND (cond
, 1);
394 if (TREE_CODE (op0
) == SSA_NAME
395 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
396 && (integer_zerop (op1
)))
399 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
402 if (cond_expr
== NULL_TREE
)
403 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
405 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
407 if (constant_or_ssa_name (cond_expr
))
410 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
412 rhs1
= TREE_OPERAND (cond_expr
, 1);
413 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
414 if (constant_or_ssa_name (rhs1
))
415 return build1 (ABS_EXPR
, type
, rhs1
);
418 if (TREE_CODE (cond_expr
) == MIN_EXPR
419 || TREE_CODE (cond_expr
) == MAX_EXPR
)
421 lhs1
= TREE_OPERAND (cond_expr
, 0);
422 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
423 rhs1
= TREE_OPERAND (cond_expr
, 1);
424 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
425 if (constant_or_ssa_name (rhs1
)
426 && constant_or_ssa_name (lhs1
))
427 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
429 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
432 /* Add condition NC to the predicate list of basic block BB. LOOP is
433 the loop to be if-converted. Use predicate of cd-equivalent block
434 for join bb if it exists: we call basic blocks bb1 and bb2
435 cd-equivalent if they are executed under the same condition. */
438 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
443 if (is_true_predicate (nc
))
446 /* If dominance tells us this basic block is always executed,
447 don't record any predicates for it. */
448 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
451 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
452 /* We use notion of cd equivalence to get simpler predicate for
453 join block, e.g. if join block has 2 predecessors with predicates
454 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
455 p1 & p2 | p1 & !p2. */
456 if (dom_bb
!= loop
->header
457 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
459 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
460 bc
= bb_predicate (dom_bb
);
461 if (!is_true_predicate (bc
))
462 set_bb_predicate (bb
, bc
);
464 gcc_assert (is_true_predicate (bb_predicate (bb
)));
465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
466 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
467 dom_bb
->index
, bb
->index
);
471 if (!is_predicated (bb
))
475 bc
= bb_predicate (bb
);
476 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
477 if (is_true_predicate (bc
))
479 reset_bb_predicate (bb
);
484 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
485 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
486 tp
= &TREE_OPERAND (bc
, 0);
489 if (!is_gimple_condexpr (*tp
))
492 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
493 add_bb_predicate_gimplified_stmts (bb
, stmts
);
495 set_bb_predicate (bb
, bc
);
498 /* Add the condition COND to the previous condition PREV_COND, and add
499 this to the predicate list of the destination of edge E. LOOP is
500 the loop to be if-converted. */
503 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
504 tree prev_cond
, tree cond
)
506 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
509 if (!is_true_predicate (prev_cond
))
510 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
513 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
514 add_to_predicate_list (loop
, e
->dest
, cond
);
517 /* Return true if one of the successor edges of BB exits LOOP. */
520 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
525 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
526 if (loop_exit_edge_p (loop
, e
))
532 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
533 and it belongs to basic block BB.
535 PHI is not if-convertible if:
536 - it has more than 2 arguments.
538 When the flag_tree_loop_if_convert_stores is not set, PHI is not
540 - a virtual PHI is immediately used in another PHI node,
541 - there is a virtual PHI in a BB other than the loop->header.
542 When the aggressive_if_conv is set, PHI can have more than
546 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
547 bool any_mask_load_store
)
549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
551 fprintf (dump_file
, "-------------------------\n");
552 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
555 if (bb
!= loop
->header
)
557 if (gimple_phi_num_args (phi
) != 2
558 && !aggressive_if_conv
)
560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
561 fprintf (dump_file
, "More than two phi node args.\n");
566 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
569 /* When the flag_tree_loop_if_convert_stores is not set, check
570 that there are no memory writes in the branches of the loop to be
572 if (virtual_operand_p (gimple_phi_result (phi
)))
574 imm_use_iterator imm_iter
;
577 if (bb
!= loop
->header
)
579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
580 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
584 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
586 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
587 && USE_STMT (use_p
) != (gimple
) phi
)
589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
590 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
599 /* Records the status of a data reference. This struct is attached to
600 each DR->aux field. */
603 /* -1 when not initialized, 0 when false, 1 when true. */
604 int written_at_least_once
;
606 /* -1 when not initialized, 0 when false, 1 when true. */
607 int rw_unconditionally
;
610 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
611 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
612 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
614 /* Returns true when the memory references of STMT are read or written
615 unconditionally. In other words, this function returns true when
616 for every data reference A in STMT there exist other accesses to
617 a data reference with the same base with predicates that add up (OR-up) to
618 the true predicate: this ensures that the data reference A is touched
619 (read or written) on every iteration of the if-converted loop. */
622 memrefs_read_or_written_unconditionally (gimple stmt
,
623 vec
<data_reference_p
> drs
)
626 data_reference_p a
, b
;
627 tree ca
= bb_predicate (gimple_bb (stmt
));
629 for (i
= 0; drs
.iterate (i
, &a
); i
++)
630 if (DR_STMT (a
) == stmt
)
633 int x
= DR_RW_UNCONDITIONALLY (a
);
641 for (j
= 0; drs
.iterate (j
, &b
); j
++)
643 tree ref_base_a
= DR_REF (a
);
644 tree ref_base_b
= DR_REF (b
);
646 if (DR_STMT (b
) == stmt
)
649 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
650 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
651 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
652 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
654 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
655 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
656 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
657 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
659 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
661 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
663 if (DR_RW_UNCONDITIONALLY (b
) == 1
664 || is_true_predicate (cb
)
665 || is_true_predicate (ca
666 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
668 DR_RW_UNCONDITIONALLY (a
) = 1;
669 DR_RW_UNCONDITIONALLY (b
) = 1;
678 DR_RW_UNCONDITIONALLY (a
) = 0;
686 /* Returns true when the memory references of STMT are unconditionally
687 written. In other words, this function returns true when for every
688 data reference A written in STMT, there exist other writes to the
689 same data reference with predicates that add up (OR-up) to the true
690 predicate: this ensures that the data reference A is written on
691 every iteration of the if-converted loop. */
694 write_memrefs_written_at_least_once (gimple stmt
,
695 vec
<data_reference_p
> drs
)
698 data_reference_p a
, b
;
699 tree ca
= bb_predicate (gimple_bb (stmt
));
701 for (i
= 0; drs
.iterate (i
, &a
); i
++)
702 if (DR_STMT (a
) == stmt
706 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
714 for (j
= 0; drs
.iterate (j
, &b
); j
++)
715 if (DR_STMT (b
) != stmt
717 && same_data_refs_base_objects (a
, b
))
719 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
721 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
722 || is_true_predicate (cb
)
723 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
726 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
727 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
735 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
743 /* Return true when the memory references of STMT won't trap in the
744 if-converted code. There are two things that we have to check for:
746 - writes to memory occur to writable memory: if-conversion of
747 memory writes transforms the conditional memory writes into
748 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
749 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
750 be executed at all in the original code, it may be a readonly
751 memory. To check that A is not const-qualified, we check that
752 there exists at least an unconditional write to A in the current
755 - reads or writes to memory are valid memory accesses for every
756 iteration. To check that the memory accesses are correctly formed
757 and that we are allowed to read and write in these locations, we
758 check that the memory accesses to be if-converted occur at every
759 iteration unconditionally. */
762 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
764 return write_memrefs_written_at_least_once (stmt
, refs
)
765 && memrefs_read_or_written_unconditionally (stmt
, refs
);
768 /* Wrapper around gimple_could_trap_p refined for the needs of the
769 if-conversion. Try to prove that the memory accesses of STMT could
770 not trap in the innermost loop containing STMT. */
773 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
775 if (gimple_vuse (stmt
)
776 && !gimple_could_trap_p_1 (stmt
, false, false)
777 && ifcvt_memrefs_wont_trap (stmt
, refs
))
780 return gimple_could_trap_p (stmt
);
783 /* Return true if STMT could be converted into a masked load or store
784 (conditional load or store based on a mask computed from bb predicate). */
787 ifcvt_can_use_mask_load_store (gimple stmt
)
791 basic_block bb
= gimple_bb (stmt
);
794 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
795 || bb
->loop_father
->dont_vectorize
796 || !gimple_assign_single_p (stmt
)
797 || gimple_has_volatile_ops (stmt
))
800 /* Check whether this is a load or store. */
801 lhs
= gimple_assign_lhs (stmt
);
802 if (gimple_store_p (stmt
))
804 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
809 else if (gimple_assign_load_p (stmt
))
812 ref
= gimple_assign_rhs1 (stmt
);
817 if (may_be_nonaddressable_p (ref
))
820 /* Mask should be integer mode of the same size as the load/store
822 mode
= TYPE_MODE (TREE_TYPE (lhs
));
823 if (int_mode_for_mode (mode
) == BLKmode
824 || VECTOR_MODE_P (mode
))
827 if (can_vec_mask_load_store_p (mode
, is_load
))
833 /* Return true when STMT is if-convertible.
835 GIMPLE_ASSIGN statement is not if-convertible if,
838 - LHS is not var decl. */
841 if_convertible_gimple_assign_stmt_p (gimple stmt
,
842 vec
<data_reference_p
> refs
,
843 bool *any_mask_load_store
)
845 tree lhs
= gimple_assign_lhs (stmt
);
848 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
850 fprintf (dump_file
, "-------------------------\n");
851 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
854 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
857 /* Some of these constrains might be too conservative. */
858 if (stmt_ends_bb_p (stmt
)
859 || gimple_has_volatile_ops (stmt
)
860 || (TREE_CODE (lhs
) == SSA_NAME
861 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
862 || gimple_has_side_effects (stmt
))
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
869 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
870 in between if_convertible_loop_p and combine_blocks
871 we can perform loop versioning. */
872 gimple_set_plf (stmt
, GF_PLF_2
, false);
874 if (flag_tree_loop_if_convert_stores
)
876 if (ifcvt_could_trap_p (stmt
, refs
))
878 if (ifcvt_can_use_mask_load_store (stmt
))
880 gimple_set_plf (stmt
, GF_PLF_2
, true);
881 *any_mask_load_store
= true;
884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
885 fprintf (dump_file
, "tree could trap...\n");
891 if (gimple_assign_rhs_could_trap_p (stmt
))
893 if (ifcvt_can_use_mask_load_store (stmt
))
895 gimple_set_plf (stmt
, GF_PLF_2
, true);
896 *any_mask_load_store
= true;
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, "tree could trap...\n");
904 bb
= gimple_bb (stmt
);
906 if (TREE_CODE (lhs
) != SSA_NAME
907 && bb
!= bb
->loop_father
->header
908 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
910 if (ifcvt_can_use_mask_load_store (stmt
))
912 gimple_set_plf (stmt
, GF_PLF_2
, true);
913 *any_mask_load_store
= true;
916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
918 fprintf (dump_file
, "LHS is not var\n");
919 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
927 /* Return true when STMT is if-convertible.
929 A statement is if-convertible if:
930 - it is an if-convertible GIMPLE_ASSIGN,
931 - it is a GIMPLE_LABEL or a GIMPLE_COND,
932 - it is builtins call. */
935 if_convertible_stmt_p (gimple stmt
, vec
<data_reference_p
> refs
,
936 bool *any_mask_load_store
)
938 switch (gimple_code (stmt
))
946 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
947 any_mask_load_store
);
951 tree fndecl
= gimple_call_fndecl (stmt
);
954 int flags
= gimple_call_flags (stmt
);
955 if ((flags
& ECF_CONST
)
956 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
957 /* We can only vectorize some builtins at the moment,
958 so restrict if-conversion to those. */
959 && DECL_BUILT_IN (fndecl
))
966 /* Don't know what to do with 'em so don't do anything. */
967 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
969 fprintf (dump_file
, "don't know what to do\n");
970 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
979 /* Assumes that BB has more than 1 predecessors.
980 Returns false if at least one successor is not on critical edge
981 and true otherwise. */
984 all_preds_critical_p (basic_block bb
)
989 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
990 if (EDGE_COUNT (e
->src
->succs
) == 1)
995 /* Returns true if at least one successor in on critical edge. */
997 has_pred_critical_p (basic_block bb
)
1002 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1003 if (EDGE_COUNT (e
->src
->succs
) > 1)
1008 /* Return true when BB is if-convertible. This routine does not check
1009 basic block's statements and phis.
1011 A basic block is not if-convertible if:
1012 - it is non-empty and it is after the exit block (in BFS order),
1013 - it is after the exit block but before the latch,
1014 - its edges are not normal.
1016 Last restriction is valid if aggressive_if_conv is false.
1018 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1022 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1028 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1030 if (EDGE_COUNT (bb
->succs
) > 2)
1033 if (EDGE_COUNT (bb
->preds
) > 2
1034 && !aggressive_if_conv
)
1039 if (bb
!= loop
->latch
)
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1042 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1045 else if (!empty_block_p (bb
))
1047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1048 fprintf (dump_file
, "non empty basic block after exit bb\n");
1051 else if (bb
== loop
->latch
1053 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1056 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1061 /* Be less adventurous and handle only normal edges. */
1062 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1063 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1066 fprintf (dump_file
, "Difficult to handle edges\n");
1070 /* At least one incoming edge has to be non-critical as otherwise edge
1071 predicates are not equal to basic-block predicates of the edge
1072 source. This check is skipped if aggressive_if_conv is true. */
1073 if (!aggressive_if_conv
1074 && EDGE_COUNT (bb
->preds
) > 1
1075 && bb
!= loop
->header
1076 && all_preds_critical_p (bb
))
1078 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1079 fprintf (dump_file
, "only critical predecessors\n");
1086 /* Return true when all predecessor blocks of BB are visited. The
1087 VISITED bitmap keeps track of the visited blocks. */
1090 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1094 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1095 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1101 /* Get body of a LOOP in suitable order for if-conversion. It is
1102 caller's responsibility to deallocate basic block list.
1103 If-conversion suitable order is, breadth first sort (BFS) order
1104 with an additional constraint: select a block only if all its
1105 predecessors are already selected. */
1107 static basic_block
*
1108 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1110 basic_block
*blocks
, *blocks_in_bfs_order
;
1113 unsigned int index
= 0;
1114 unsigned int visited_count
= 0;
1116 gcc_assert (loop
->num_nodes
);
1117 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1119 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1120 visited
= BITMAP_ALLOC (NULL
);
1122 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1125 while (index
< loop
->num_nodes
)
1127 bb
= blocks_in_bfs_order
[index
];
1129 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1131 free (blocks_in_bfs_order
);
1132 BITMAP_FREE (visited
);
1137 if (!bitmap_bit_p (visited
, bb
->index
))
1139 if (pred_blocks_visited_p (bb
, &visited
)
1140 || bb
== loop
->header
)
1142 /* This block is now visited. */
1143 bitmap_set_bit (visited
, bb
->index
);
1144 blocks
[visited_count
++] = bb
;
1150 if (index
== loop
->num_nodes
1151 && visited_count
!= loop
->num_nodes
)
1155 free (blocks_in_bfs_order
);
1156 BITMAP_FREE (visited
);
1160 /* Returns true when the analysis of the predicates for all the basic
1161 blocks in LOOP succeeded.
1163 predicate_bbs first allocates the predicates of the basic blocks.
1164 These fields are then initialized with the tree expressions
1165 representing the predicates under which a basic block is executed
1166 in the LOOP. As the loop->header is executed at each iteration, it
1167 has the "true" predicate. Other statements executed under a
1168 condition are predicated with that condition, for example
1175 S1 will be predicated with "x", and
1176 S2 will be predicated with "!x". */
1179 predicate_bbs (loop_p loop
)
1183 for (i
= 0; i
< loop
->num_nodes
; i
++)
1184 init_bb_predicate (ifc_bbs
[i
]);
1186 for (i
= 0; i
< loop
->num_nodes
; i
++)
1188 basic_block bb
= ifc_bbs
[i
];
1192 /* The loop latch and loop exit block are always executed and
1193 have no extra conditions to be processed: skip them. */
1194 if (bb
== loop
->latch
1195 || bb_with_exit_edge_p (loop
, bb
))
1197 reset_bb_predicate (bb
);
1201 cond
= bb_predicate (bb
);
1202 stmt
= last_stmt (bb
);
1203 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1206 edge true_edge
, false_edge
;
1207 location_t loc
= gimple_location (stmt
);
1208 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1210 gimple_cond_lhs (stmt
),
1211 gimple_cond_rhs (stmt
));
1213 /* Add new condition into destination's predicate list. */
1214 extract_true_false_edges_from_block (gimple_bb (stmt
),
1215 &true_edge
, &false_edge
);
1217 /* If C is true, then TRUE_EDGE is taken. */
1218 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1221 /* If C is false, then FALSE_EDGE is taken. */
1222 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1224 add_to_dst_predicate_list (loop
, false_edge
,
1225 unshare_expr (cond
), c2
);
1230 /* If current bb has only one successor, then consider it as an
1231 unconditional goto. */
1232 if (single_succ_p (bb
))
1234 basic_block bb_n
= single_succ (bb
);
1236 /* The successor bb inherits the predicate of its
1237 predecessor. If there is no predicate in the predecessor
1238 bb, then consider the successor bb as always executed. */
1239 if (cond
== NULL_TREE
)
1240 cond
= boolean_true_node
;
1242 add_to_predicate_list (loop
, bb_n
, cond
);
1246 /* The loop header is always executed. */
1247 reset_bb_predicate (loop
->header
);
1248 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1249 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1252 /* Return true when LOOP is if-convertible. This is a helper function
1253 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1254 in if_convertible_loop_p. */
1257 if_convertible_loop_p_1 (struct loop
*loop
,
1258 vec
<loop_p
> *loop_nest
,
1259 vec
<data_reference_p
> *refs
,
1260 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1264 basic_block exit_bb
= NULL
;
1266 /* Don't if-convert the loop when the data dependences cannot be
1267 computed: the loop won't be vectorized in that case. */
1268 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1272 calculate_dominance_info (CDI_DOMINATORS
);
1273 calculate_dominance_info (CDI_POST_DOMINATORS
);
1275 /* Allow statements that can be handled during if-conversion. */
1276 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1280 fprintf (dump_file
, "Irreducible loop\n");
1284 for (i
= 0; i
< loop
->num_nodes
; i
++)
1286 basic_block bb
= ifc_bbs
[i
];
1288 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1291 if (bb_with_exit_edge_p (loop
, bb
))
1295 for (i
= 0; i
< loop
->num_nodes
; i
++)
1297 basic_block bb
= ifc_bbs
[i
];
1298 gimple_stmt_iterator gsi
;
1300 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1301 switch (gimple_code (gsi_stmt (gsi
)))
1314 if (flag_tree_loop_if_convert_stores
)
1316 data_reference_p dr
;
1318 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1320 dr
->aux
= XNEW (struct ifc_dr
);
1321 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1322 DR_RW_UNCONDITIONALLY (dr
) = -1;
1324 predicate_bbs (loop
);
1327 for (i
= 0; i
< loop
->num_nodes
; i
++)
1329 basic_block bb
= ifc_bbs
[i
];
1330 gimple_stmt_iterator itr
;
1332 /* Check the if-convertibility of statements in predicated BBs. */
1333 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1334 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1335 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1336 any_mask_load_store
))
1340 if (flag_tree_loop_if_convert_stores
)
1341 for (i
= 0; i
< loop
->num_nodes
; i
++)
1342 free_bb_predicate (ifc_bbs
[i
]);
1344 /* Checking PHIs needs to be done after stmts, as the fact whether there
1345 are any masked loads or stores affects the tests. */
1346 for (i
= 0; i
< loop
->num_nodes
; i
++)
1348 basic_block bb
= ifc_bbs
[i
];
1351 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1352 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1353 *any_mask_load_store
))
1358 fprintf (dump_file
, "Applying if-conversion\n");
1363 /* Return true when LOOP is if-convertible.
1364 LOOP is if-convertible if:
1366 - it has two or more basic blocks,
1367 - it has only one exit,
1368 - loop header is not the exit edge,
1369 - if its basic blocks and phi nodes are if convertible. */
1372 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1377 vec
<data_reference_p
> refs
;
1380 /* Handle only innermost loop. */
1381 if (!loop
|| loop
->inner
)
1383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1384 fprintf (dump_file
, "not innermost loop\n");
1388 /* If only one block, no need for if-conversion. */
1389 if (loop
->num_nodes
<= 2)
1391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1392 fprintf (dump_file
, "less than 2 basic blocks\n");
1396 /* More than one loop exit is too much to handle. */
1397 if (!single_exit (loop
))
1399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1400 fprintf (dump_file
, "multiple exits\n");
1404 /* If one of the loop header's edge is an exit edge then do not
1405 apply if-conversion. */
1406 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1407 if (loop_exit_edge_p (loop
, e
))
1412 auto_vec
<loop_p
, 3> loop_nest
;
1413 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1414 any_mask_load_store
);
1416 if (flag_tree_loop_if_convert_stores
)
1418 data_reference_p dr
;
1421 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1425 free_data_refs (refs
);
1426 free_dependence_relations (ddrs
);
1430 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1431 which is in predicated basic block.
1432 In fact, the following PHI pattern is searching:
1434 reduc_1 = PHI <..., reduc_2>
1438 reduc_2 = PHI <reduc_1, reduc_3>
1440 ARG_0 and ARG_1 are correspondent PHI arguments.
1441 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1442 EXTENDED is true if PHI has > 2 arguments. */
1445 is_cond_scalar_reduction (gimple phi
, gimple
*reduc
, tree arg_0
, tree arg_1
,
1446 tree
*op0
, tree
*op1
, bool extended
)
1448 tree lhs
, r_op1
, r_op2
;
1450 gimple header_phi
= NULL
;
1451 enum tree_code reduction_op
;
1452 basic_block bb
= gimple_bb (phi
);
1453 struct loop
*loop
= bb
->loop_father
;
1454 edge latch_e
= loop_latch_edge (loop
);
1455 imm_use_iterator imm_iter
;
1456 use_operand_p use_p
;
1459 bool result
= false;
1460 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1463 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1466 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1467 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1469 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1472 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1473 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1477 if (gimple_bb (header_phi
) != loop
->header
)
1480 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1483 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1484 || gimple_has_volatile_ops (stmt
))
1487 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1490 if (!is_predicated (gimple_bb (stmt
)))
1493 /* Check that stmt-block is predecessor of phi-block. */
1494 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1503 if (!has_single_use (lhs
))
1506 reduction_op
= gimple_assign_rhs_code (stmt
);
1507 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1509 r_op1
= gimple_assign_rhs1 (stmt
);
1510 r_op2
= gimple_assign_rhs2 (stmt
);
1512 /* Make R_OP1 to hold reduction variable. */
1513 if (r_op2
== PHI_RESULT (header_phi
)
1514 && reduction_op
== PLUS_EXPR
)
1520 else if (r_op1
!= PHI_RESULT (header_phi
))
1523 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1524 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1526 gimple use_stmt
= USE_STMT (use_p
);
1527 if (is_gimple_debug (use_stmt
))
1529 if (use_stmt
== stmt
)
1531 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1535 *op0
= r_op1
; *op1
= r_op2
;
1540 /* Converts conditional scalar reduction into unconditional form, e.g.
1542 if (_5 != 0) goto bb_5 else goto bb_6
1548 # res_2 = PHI <res_13(4), res_6(5)>
1551 will be converted into sequence
1552 _ifc__1 = _5 != 0 ? 1 : 0;
1553 res_2 = res_13 + _ifc__1;
1554 Argument SWAP tells that arguments of conditional expression should be
1556 Returns rhs of resulting PHI assignment. */
1559 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1560 tree cond
, tree op0
, tree op1
, bool swap
)
1562 gimple_stmt_iterator stmt_it
;
1565 tree rhs1
= gimple_assign_rhs1 (reduc
);
1566 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1568 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1572 fprintf (dump_file
, "Found cond scalar reduction.\n");
1573 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1576 /* Build cond expression using COND and constant operand
1577 of reduction rhs. */
1578 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1579 unshare_expr (cond
),
1583 /* Create assignment stmt and insert it at GSI. */
1584 new_assign
= gimple_build_assign (tmp
, c
);
1585 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1586 /* Build rhs for unconditional increment/decrement. */
1587 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1588 TREE_TYPE (rhs1
), op0
, tmp
);
1590 /* Delete original reduction stmt. */
1591 stmt_it
= gsi_for_stmt (reduc
);
1592 gsi_remove (&stmt_it
, true);
1593 release_defs (reduc
);
1597 /* Helpers for PHI arguments hashtable map. */
1599 struct phi_args_hash_traits
: default_hashmap_traits
1601 static inline hashval_t
hash (tree
);
1602 static inline bool equal_keys (tree
, tree
);
1606 phi_args_hash_traits::hash (tree value
)
1608 return iterative_hash_expr (value
, 0);
1612 phi_args_hash_traits::equal_keys (tree value1
, tree value2
)
1614 return operand_equal_p (value1
, value2
, 0);
1617 /* Produce condition for all occurrences of ARG in PHI node. */
1620 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1621 gimple_stmt_iterator
*gsi
)
1625 tree cond
= NULL_TREE
;
1629 len
= occur
->length ();
1630 gcc_assert (len
> 0);
1631 for (i
= 0; i
< len
; i
++)
1633 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1634 c
= bb_predicate (e
->src
);
1635 if (is_true_predicate (c
))
1637 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1638 is_gimple_condexpr
, NULL_TREE
,
1639 true, GSI_SAME_STMT
);
1640 if (cond
!= NULL_TREE
)
1642 /* Must build OR expression. */
1643 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1644 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1645 is_gimple_condexpr
, NULL_TREE
,
1646 true, GSI_SAME_STMT
);
1651 gcc_assert (cond
!= NULL_TREE
);
1655 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1656 This routine can handle PHI nodes with more than two arguments.
1659 S1: A = PHI <x1(1), x2(5)>
1661 S2: A = cond ? x1 : x2;
1663 The generated code is inserted at GSI that points to the top of
1664 basic block's statement list.
1665 If PHI node has more than two arguments a chain of conditional
1666 expression is produced. */
1670 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1672 gimple new_stmt
= NULL
, reduc
;
1673 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1675 unsigned int index0
;
1676 unsigned int max
, args_len
;
1681 res
= gimple_phi_result (phi
);
1682 if (virtual_operand_p (res
))
1685 if ((rhs
= degenerate_phi_result (phi
))
1686 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1688 && !chrec_contains_undetermined (scev
)
1690 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1694 fprintf (dump_file
, "Degenerate phi!\n");
1695 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1697 new_stmt
= gimple_build_assign (res
, rhs
);
1698 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1699 update_stmt (new_stmt
);
1703 bb
= gimple_bb (phi
);
1704 if (EDGE_COUNT (bb
->preds
) == 2)
1706 /* Predicate ordinary PHI node with 2 arguments. */
1707 edge first_edge
, second_edge
;
1708 basic_block true_bb
;
1709 first_edge
= EDGE_PRED (bb
, 0);
1710 second_edge
= EDGE_PRED (bb
, 1);
1711 cond
= bb_predicate (first_edge
->src
);
1712 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1714 edge tmp_edge
= first_edge
;
1715 first_edge
= second_edge
;
1716 second_edge
= tmp_edge
;
1718 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1720 cond
= bb_predicate (second_edge
->src
);
1721 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1722 cond
= TREE_OPERAND (cond
, 0);
1724 first_edge
= second_edge
;
1727 cond
= bb_predicate (first_edge
->src
);
1728 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1729 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1730 is_gimple_condexpr
, NULL_TREE
,
1731 true, GSI_SAME_STMT
);
1732 true_bb
= first_edge
->src
;
1733 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1735 arg0
= gimple_phi_arg_def (phi
, 1);
1736 arg1
= gimple_phi_arg_def (phi
, 0);
1740 arg0
= gimple_phi_arg_def (phi
, 0);
1741 arg1
= gimple_phi_arg_def (phi
, 1);
1743 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1745 /* Convert reduction stmt into vectorizable form. */
1746 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1747 true_bb
!= gimple_bb (reduc
));
1749 /* Build new RHS using selected condition and arguments. */
1750 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1752 new_stmt
= gimple_build_assign (res
, rhs
);
1753 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1754 update_stmt (new_stmt
);
1756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 fprintf (dump_file
, "new phi replacement stmt\n");
1759 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1764 /* Create hashmap for PHI node which contain vector of argument indexes
1765 having the same value. */
1767 hash_map
<tree
, auto_vec
<int>, phi_args_hash_traits
> phi_arg_map
;
1768 unsigned int num_args
= gimple_phi_num_args (phi
);
1770 /* Vector of different PHI argument values. */
1771 auto_vec
<tree
> args (num_args
);
1773 /* Compute phi_arg_map. */
1774 for (i
= 0; i
< num_args
; i
++)
1778 arg
= gimple_phi_arg_def (phi
, i
);
1779 if (!phi_arg_map
.get (arg
))
1780 args
.quick_push (arg
);
1781 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1784 /* Determine element with max number of occurrences. */
1787 args_len
= args
.length ();
1788 for (i
= 0; i
< args_len
; i
++)
1791 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1798 /* Put element with max number of occurences to the end of ARGS. */
1799 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1801 tree tmp
= args
[args_len
- 1];
1802 args
[args_len
- 1] = args
[max_ind
];
1803 args
[max_ind
] = tmp
;
1806 /* Handle one special case when number of arguments with different values
1807 is equal 2 and one argument has the only occurrence. Such PHI can be
1808 handled as if would have only 2 arguments. */
1809 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1812 indexes
= phi_arg_map
.get (args
[0]);
1813 index0
= (*indexes
)[0];
1816 e
= gimple_phi_arg_edge (phi
, index0
);
1817 cond
= bb_predicate (e
->src
);
1818 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1821 cond
= TREE_OPERAND (cond
, 0);
1823 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1824 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1825 is_gimple_condexpr
, NULL_TREE
,
1826 true, GSI_SAME_STMT
);
1827 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1829 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1833 /* Convert reduction stmt into vectorizable form. */
1834 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1836 new_stmt
= gimple_build_assign (res
, rhs
);
1837 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1838 update_stmt (new_stmt
);
1844 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1847 for (i
= 0; i
< args_len
; i
++)
1850 indexes
= phi_arg_map
.get (args
[i
]);
1851 if (i
!= args_len
- 1)
1852 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1855 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1856 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1858 new_stmt
= gimple_build_assign (lhs
, rhs
);
1859 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1860 update_stmt (new_stmt
);
1865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1867 fprintf (dump_file
, "new extended phi replacement stmt\n");
1868 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1872 /* Replaces in LOOP all the scalar phi nodes other than those in the
1873 LOOP->header block with conditional modify expressions. */
1876 predicate_all_scalar_phis (struct loop
*loop
)
1879 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1882 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1885 gimple_stmt_iterator gsi
;
1886 gphi_iterator phi_gsi
;
1889 if (bb
== loop
->header
)
1892 if (EDGE_COUNT (bb
->preds
) == 1)
1895 phi_gsi
= gsi_start_phis (bb
);
1896 if (gsi_end_p (phi_gsi
))
1899 gsi
= gsi_after_labels (bb
);
1900 while (!gsi_end_p (phi_gsi
))
1902 phi
= phi_gsi
.phi ();
1903 predicate_scalar_phi (phi
, &gsi
);
1904 release_phi_node (phi
);
1905 gsi_next (&phi_gsi
);
1908 set_phi_nodes (bb
, NULL
);
1912 /* Insert in each basic block of LOOP the statements produced by the
1913 gimplification of the predicates. */
1916 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1920 for (i
= 0; i
< loop
->num_nodes
; i
++)
1922 basic_block bb
= ifc_bbs
[i
];
1924 if (!is_predicated (bb
))
1925 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1926 if (!is_predicated (bb
))
1928 /* Do not insert statements for a basic block that is not
1929 predicated. Also make sure that the predicate of the
1930 basic block is set to true. */
1931 reset_bb_predicate (bb
);
1935 stmts
= bb_predicate_gimplified_stmts (bb
);
1938 if (flag_tree_loop_if_convert_stores
1939 || any_mask_load_store
)
1941 /* Insert the predicate of the BB just after the label,
1942 as the if-conversion of memory writes will use this
1944 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1945 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1949 /* Insert the predicate of the BB at the end of the BB
1950 as this would reduce the register pressure: the only
1951 use of this predicate will be in successor BBs. */
1952 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1955 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1956 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1958 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1961 /* Once the sequence is code generated, set it to NULL. */
1962 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1967 /* Helper function for predicate_mem_writes. Returns index of existent
1968 mask if it was created for given SIZE and -1 otherwise. */
1971 mask_exists (int size
, vec
<int> vec
)
1975 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1981 /* Predicate each write to memory in LOOP.
1983 This function transforms control flow constructs containing memory
1986 | for (i = 0; i < N; i++)
1990 into the following form that does not contain control flow:
1992 | for (i = 0; i < N; i++)
1993 | A[i] = cond ? expr : A[i];
1995 The original CFG looks like this:
2002 | if (i < N) goto bb_5 else goto bb_2
2006 | cond = some_computation;
2007 | if (cond) goto bb_3 else goto bb_4
2019 insert_gimplified_predicates inserts the computation of the COND
2020 expression at the beginning of the destination basic block:
2027 | if (i < N) goto bb_5 else goto bb_2
2031 | cond = some_computation;
2032 | if (cond) goto bb_3 else goto bb_4
2036 | cond = some_computation;
2045 predicate_mem_writes is then predicating the memory write as follows:
2052 | if (i < N) goto bb_5 else goto bb_2
2056 | if (cond) goto bb_3 else goto bb_4
2060 | cond = some_computation;
2061 | A[i] = cond ? expr : A[i];
2069 and finally combine_blocks removes the basic block boundaries making
2070 the loop vectorizable:
2074 | if (i < N) goto bb_5 else goto bb_1
2078 | cond = some_computation;
2079 | A[i] = cond ? expr : A[i];
2080 | if (i < N) goto bb_5 else goto bb_4
2089 predicate_mem_writes (loop_p loop
)
2091 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2092 auto_vec
<int, 1> vect_sizes
;
2093 auto_vec
<tree
, 1> vect_masks
;
2095 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2097 gimple_stmt_iterator gsi
;
2098 basic_block bb
= ifc_bbs
[i
];
2099 tree cond
= bb_predicate (bb
);
2104 if (is_true_predicate (cond
))
2108 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2111 cond
= TREE_OPERAND (cond
, 0);
2114 vect_sizes
.truncate (0);
2115 vect_masks
.truncate (0);
2117 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2118 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2120 else if (gimple_plf (stmt
, GF_PLF_2
))
2122 tree lhs
= gimple_assign_lhs (stmt
);
2123 tree rhs
= gimple_assign_rhs1 (stmt
);
2124 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
2126 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2127 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2128 mark_addressable (ref
);
2129 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2130 true, NULL_TREE
, true,
2132 if (!vect_sizes
.is_empty ()
2133 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2134 /* Use created mask. */
2135 mask
= vect_masks
[index
];
2138 masktype
= build_nonstandard_integer_type (bitsize
, 1);
2139 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
2140 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
2141 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2144 true, GSI_SAME_STMT
);
2145 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
2146 mask_op0
, mask_op1
);
2147 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
2148 /* Save mask and its size for further use. */
2149 vect_sizes
.safe_push (bitsize
);
2150 vect_masks
.safe_push (mask
);
2152 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
2153 /* Copy points-to info if possible. */
2154 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2155 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2157 if (TREE_CODE (lhs
) == SSA_NAME
)
2160 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2162 gimple_call_set_lhs (new_stmt
, lhs
);
2166 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2168 gsi_replace (&gsi
, new_stmt
, true);
2170 else if (gimple_vdef (stmt
))
2172 tree lhs
= gimple_assign_lhs (stmt
);
2173 tree rhs
= gimple_assign_rhs1 (stmt
);
2174 tree type
= TREE_TYPE (lhs
);
2176 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2177 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2184 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2185 is_gimple_condexpr
, NULL_TREE
,
2186 true, GSI_SAME_STMT
);
2187 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2188 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2194 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2195 other than the exit and latch of the LOOP. Also resets the
2196 GIMPLE_DEBUG information. */
2199 remove_conditions_and_labels (loop_p loop
)
2201 gimple_stmt_iterator gsi
;
2204 for (i
= 0; i
< loop
->num_nodes
; i
++)
2206 basic_block bb
= ifc_bbs
[i
];
2208 if (bb_with_exit_edge_p (loop
, bb
)
2209 || bb
== loop
->latch
)
2212 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2213 switch (gimple_code (gsi_stmt (gsi
)))
2217 gsi_remove (&gsi
, true);
2221 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2222 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2224 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2225 update_stmt (gsi_stmt (gsi
));
2236 /* Combine all the basic blocks from LOOP into one or two super basic
2237 blocks. Replace PHI nodes with conditional modify expressions. */
2240 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2242 basic_block bb
, exit_bb
, merge_target_bb
;
2243 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2248 predicate_bbs (loop
);
2249 remove_conditions_and_labels (loop
);
2250 insert_gimplified_predicates (loop
, any_mask_load_store
);
2251 predicate_all_scalar_phis (loop
);
2253 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2254 predicate_mem_writes (loop
);
2256 /* Merge basic blocks: first remove all the edges in the loop,
2257 except for those from the exit block. */
2259 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2262 free_bb_predicate (bb
);
2263 if (bb_with_exit_edge_p (loop
, bb
))
2265 gcc_assert (exit_bb
== NULL
);
2269 gcc_assert (exit_bb
!= loop
->latch
);
2271 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2275 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2277 if (e
->src
== exit_bb
)
2284 if (exit_bb
!= NULL
)
2286 if (exit_bb
!= loop
->header
)
2288 /* Connect this node to loop header. */
2289 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2290 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2293 /* Redirect non-exit edges to loop->latch. */
2294 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2296 if (!loop_exit_edge_p (loop
, e
))
2297 redirect_edge_and_branch (e
, loop
->latch
);
2299 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2303 /* If the loop does not have an exit, reconnect header and latch. */
2304 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2305 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2308 merge_target_bb
= loop
->header
;
2309 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2311 gimple_stmt_iterator gsi
;
2312 gimple_stmt_iterator last
;
2316 if (bb
== exit_bb
|| bb
== loop
->latch
)
2319 /* Make stmts member of loop->header. */
2320 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2321 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2323 /* Update stmt list. */
2324 last
= gsi_last_bb (merge_target_bb
);
2325 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2326 set_bb_seq (bb
, NULL
);
2328 delete_basic_block (bb
);
2331 /* If possible, merge loop header to the block with the exit edge.
2332 This reduces the number of basic blocks to two, to please the
2333 vectorizer that handles only loops with two nodes. */
2335 && exit_bb
!= loop
->header
2336 && can_merge_blocks_p (loop
->header
, exit_bb
))
2337 merge_blocks (loop
->header
, exit_bb
);
2343 /* Version LOOP before if-converting it, the original loop
2344 will be then if-converted, the new copy of the loop will not,
2345 and the LOOP_VECTORIZED internal call will be guarding which
2346 loop to execute. The vectorizer pass will fold this
2347 internal call into either true or false. */
2350 version_loop_for_if_conversion (struct loop
*loop
)
2352 basic_block cond_bb
;
2353 tree cond
= make_ssa_name (boolean_type_node
);
2354 struct loop
*new_loop
;
2356 gimple_stmt_iterator gsi
;
2358 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2359 build_int_cst (integer_type_node
, loop
->num
),
2361 gimple_call_set_lhs (g
, cond
);
2363 initialize_original_copy_tables ();
2364 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2365 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2366 REG_BR_PROB_BASE
, true);
2367 free_original_copy_tables ();
2368 if (new_loop
== NULL
)
2370 new_loop
->dont_vectorize
= true;
2371 new_loop
->force_vectorize
= false;
2372 gsi
= gsi_last_bb (cond_bb
);
2373 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2374 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2375 update_ssa (TODO_update_ssa
);
2379 /* Performs splitting of critical edges if aggressive_if_conv is true.
2380 Returns false if loop won't be if converted and true otherwise. */
2383 ifcvt_split_critical_edges (struct loop
*loop
)
2387 unsigned int num
= loop
->num_nodes
;
2397 if (!single_exit (loop
))
2400 body
= get_loop_body (loop
);
2401 for (i
= 0; i
< num
; i
++)
2404 if (bb
== loop
->latch
2405 || bb_with_exit_edge_p (loop
, bb
))
2407 stmt
= last_stmt (bb
);
2408 /* Skip basic blocks not ending with conditional branch. */
2409 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2411 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2412 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2419 /* Assumes that lhs of DEF_STMT have multiple uses.
2420 Delete one use by (1) creation of copy DEF_STMT with
2421 unique lhs; (2) change original use of lhs in one
2422 use statement with newly created lhs. */
2425 ifcvt_split_def_stmt (gimple def_stmt
, gimple use_stmt
)
2430 gimple_stmt_iterator gsi
;
2431 use_operand_p use_p
;
2432 imm_use_iterator imm_iter
;
2434 var
= gimple_assign_lhs (def_stmt
);
2435 copy_stmt
= gimple_copy (def_stmt
);
2436 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2437 gimple_assign_set_lhs (copy_stmt
, lhs
);
2438 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2439 /* Insert copy of DEF_STMT. */
2440 gsi
= gsi_for_stmt (def_stmt
);
2441 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2442 /* Change use of var to lhs in use_stmt. */
2443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2445 fprintf (dump_file
, "Change use of var ");
2446 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2447 fprintf (dump_file
, " to ");
2448 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2449 fprintf (dump_file
, "\n");
2451 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2453 if (USE_STMT (use_p
) != use_stmt
)
2455 SET_USE (use_p
, lhs
);
2460 /* Traverse bool pattern recursively starting from VAR.
2461 Save its def and use statements to defuse_list if VAR does
2462 not have single use. */
2465 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
> *defuse_list
,
2469 enum tree_code code
;
2472 def_stmt
= SSA_NAME_DEF_STMT (var
);
2473 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2475 if (!has_single_use (var
))
2477 /* Put def and use stmts into defuse_list. */
2478 defuse_list
->safe_push (def_stmt
);
2479 defuse_list
->safe_push (use_stmt
);
2480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2482 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2483 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2486 rhs1
= gimple_assign_rhs1 (def_stmt
);
2487 code
= gimple_assign_rhs_code (def_stmt
);
2491 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2494 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2495 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2496 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2498 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2501 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2506 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2507 rhs2
= gimple_assign_rhs2 (def_stmt
);
2508 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2516 /* Returns true if STMT can be a root of bool pattern apllied
2520 stmt_is_root_of_bool_pattern (gimple stmt
)
2522 enum tree_code code
;
2525 code
= gimple_assign_rhs_code (stmt
);
2526 if (CONVERT_EXPR_CODE_P (code
))
2528 lhs
= gimple_assign_lhs (stmt
);
2529 rhs
= gimple_assign_rhs1 (stmt
);
2530 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2532 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2536 else if (code
== COND_EXPR
)
2538 rhs
= gimple_assign_rhs1 (stmt
);
2539 if (TREE_CODE (rhs
) != SSA_NAME
)
2546 /* Traverse all statements in BB which correspondent to loop header to
2547 find out all statements which can start bool pattern applied by
2548 vectorizer and convert multiple uses in it to conform pattern
2549 restrictions. Such case can occur if the same predicate is used both
2550 for phi node conversion and load/store mask. */
2553 ifcvt_repair_bool_pattern (basic_block bb
)
2557 gimple_stmt_iterator gsi
;
2558 vec
<gimple
> defuse_list
= vNULL
;
2559 vec
<gimple
> pattern_roots
= vNULL
;
2564 /* Collect all root pattern statements. */
2565 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2567 stmt
= gsi_stmt (gsi
);
2568 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2570 if (!stmt_is_root_of_bool_pattern (stmt
))
2572 pattern_roots
.safe_push (stmt
);
2575 if (pattern_roots
.is_empty ())
2578 /* Split all statements with multiple uses iteratively since splitting
2579 may create new multiple uses. */
2584 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2586 rhs
= gimple_assign_rhs1 (stmt
);
2587 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2588 while (defuse_list
.length () > 0)
2591 gimple def_stmt
, use_stmt
;
2592 use_stmt
= defuse_list
.pop ();
2593 def_stmt
= defuse_list
.pop ();
2594 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2604 /* Delete redundant statements produced by predication which prevents
2605 loop vectorization. */
2608 ifcvt_local_dce (basic_block bb
)
2613 gimple_stmt_iterator gsi
;
2614 vec
<gimple
> worklist
;
2615 enum gimple_code code
;
2616 use_operand_p use_p
;
2617 imm_use_iterator imm_iter
;
2619 worklist
.create (64);
2620 /* Consider all phi as live statements. */
2621 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2623 phi
= gsi_stmt (gsi
);
2624 gimple_set_plf (phi
, GF_PLF_2
, true);
2625 worklist
.safe_push (phi
);
2627 /* Consider load/store statemnts, CALL and COND as live. */
2628 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2630 stmt
= gsi_stmt (gsi
);
2631 if (gimple_store_p (stmt
)
2632 || gimple_assign_load_p (stmt
)
2633 || is_gimple_debug (stmt
))
2635 gimple_set_plf (stmt
, GF_PLF_2
, true);
2636 worklist
.safe_push (stmt
);
2639 code
= gimple_code (stmt
);
2640 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2642 gimple_set_plf (stmt
, GF_PLF_2
, true);
2643 worklist
.safe_push (stmt
);
2646 gimple_set_plf (stmt
, GF_PLF_2
, false);
2648 if (code
== GIMPLE_ASSIGN
)
2650 tree lhs
= gimple_assign_lhs (stmt
);
2651 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2653 stmt1
= USE_STMT (use_p
);
2654 if (gimple_bb (stmt1
) != bb
)
2656 gimple_set_plf (stmt
, GF_PLF_2
, true);
2657 worklist
.safe_push (stmt
);
2663 /* Propagate liveness through arguments of live stmt. */
2664 while (worklist
.length () > 0)
2667 use_operand_p use_p
;
2670 stmt
= worklist
.pop ();
2671 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2673 use
= USE_FROM_PTR (use_p
);
2674 if (TREE_CODE (use
) != SSA_NAME
)
2676 stmt1
= SSA_NAME_DEF_STMT (use
);
2677 if (gimple_bb (stmt1
) != bb
2678 || gimple_plf (stmt1
, GF_PLF_2
))
2680 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2681 worklist
.safe_push (stmt1
);
2684 /* Delete dead statements. */
2685 gsi
= gsi_start_bb (bb
);
2686 while (!gsi_end_p (gsi
))
2688 stmt
= gsi_stmt (gsi
);
2689 if (gimple_plf (stmt
, GF_PLF_2
))
2694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2696 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2697 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2699 gsi_remove (&gsi
, true);
2700 release_defs (stmt
);
2704 /* If-convert LOOP when it is legal. For the moment this pass has no
2705 profitability analysis. Returns non-zero todo flags when something
2709 tree_if_conversion (struct loop
*loop
)
2711 unsigned int todo
= 0;
2713 bool any_mask_load_store
= false;
2715 /* Set-up aggressive if-conversion for loops marked with simd pragma. */
2716 aggressive_if_conv
= loop
->force_vectorize
;
2717 /* Check either outer loop was marked with simd pragma. */
2718 if (!aggressive_if_conv
)
2720 struct loop
*outer_loop
= loop_outer (loop
);
2721 if (outer_loop
&& outer_loop
->force_vectorize
)
2722 aggressive_if_conv
= true;
2725 if (aggressive_if_conv
)
2726 if (!ifcvt_split_critical_edges (loop
))
2729 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2730 || !dbg_cnt (if_conversion_tree
))
2733 if (any_mask_load_store
2734 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2735 || loop
->dont_vectorize
))
2738 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2741 /* Now all statements are if-convertible. Combine all the basic
2742 blocks into one huge basic block doing the if-conversion
2744 combine_blocks (loop
, any_mask_load_store
);
2746 /* Delete dead predicate computations and repair tree correspondent
2747 to bool pattern to delete multiple uses of preidcates. */
2748 if (aggressive_if_conv
)
2750 ifcvt_local_dce (loop
->header
);
2751 ifcvt_repair_bool_pattern (loop
->header
);
2754 todo
|= TODO_cleanup_cfg
;
2755 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2757 mark_virtual_operands_for_renaming (cfun
);
2758 todo
|= TODO_update_ssa_only_virtuals
;
2766 for (i
= 0; i
< loop
->num_nodes
; i
++)
2767 free_bb_predicate (ifc_bbs
[i
]);
2772 free_dominance_info (CDI_POST_DOMINATORS
);
2777 /* Tree if-conversion pass management. */
2781 const pass_data pass_data_if_conversion
=
2783 GIMPLE_PASS
, /* type */
2785 OPTGROUP_NONE
, /* optinfo_flags */
2786 TV_NONE
, /* tv_id */
2787 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2788 0, /* properties_provided */
2789 0, /* properties_destroyed */
2790 0, /* todo_flags_start */
2791 0, /* todo_flags_finish */
2794 class pass_if_conversion
: public gimple_opt_pass
2797 pass_if_conversion (gcc::context
*ctxt
)
2798 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2801 /* opt_pass methods: */
2802 virtual bool gate (function
*);
2803 virtual unsigned int execute (function
*);
2805 }; // class pass_if_conversion
2808 pass_if_conversion::gate (function
*fun
)
2810 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2811 && flag_tree_loop_if_convert
!= 0)
2812 || flag_tree_loop_if_convert
== 1
2813 || flag_tree_loop_if_convert_stores
== 1);
2817 pass_if_conversion::execute (function
*fun
)
2822 if (number_of_loops (fun
) <= 1)
2825 FOR_EACH_LOOP (loop
, 0)
2826 if (flag_tree_loop_if_convert
== 1
2827 || flag_tree_loop_if_convert_stores
== 1
2828 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2829 && !loop
->dont_vectorize
))
2830 todo
|= tree_if_conversion (loop
);
2832 #ifdef ENABLE_CHECKING
2835 FOR_EACH_BB_FN (bb
, fun
)
2836 gcc_assert (!bb
->aux
);
2846 make_pass_if_conversion (gcc::context
*ctxt
)
2848 return new pass_if_conversion (ctxt
);