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 (ifcvt_could_trap_p (stmt, refs))
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 data_reference_p dr;
1302 for (i = 0; refs->iterate (i, &dr); i++)
1304 dr->aux = XNEW (struct ifc_dr);
1305 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1306 DR_RW_UNCONDITIONALLY (dr) = -1;
1308 predicate_bbs (loop);
1310 for (i = 0; i < loop->num_nodes; i++)
1312 basic_block bb = ifc_bbs[i];
1313 gimple_stmt_iterator itr;
1315 /* Check the if-convertibility of statements in predicated BBs. */
1316 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1317 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1318 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs,
1319 any_mask_load_store))
1323 for (i = 0; i < loop->num_nodes; i++)
1324 free_bb_predicate (ifc_bbs[i]);
1326 /* Checking PHIs needs to be done after stmts, as the fact whether there
1327 are any masked loads or stores affects the tests. */
1328 for (i = 0; i < loop->num_nodes; i++)
1330 basic_block bb = ifc_bbs[i];
1333 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1334 if (!if_convertible_phi_p (loop, bb, itr.phi (),
1335 *any_mask_load_store))
1340 fprintf (dump_file, "Applying if-conversion\n");
1345 /* Return true when LOOP is if-convertible.
1346 LOOP is if-convertible if:
1348 - it has two or more basic blocks,
1349 - it has only one exit,
1350 - loop header is not the exit edge,
1351 - if its basic blocks and phi nodes are if convertible. */
1354 if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store)
1359 vec<data_reference_p> refs;
1362 /* Handle only innermost loop. */
1363 if (!loop || loop->inner)
1365 if (dump_file && (dump_flags & TDF_DETAILS))
1366 fprintf (dump_file, "not innermost loop\n");
1370 /* If only one block, no need for if-conversion. */
1371 if (loop->num_nodes <= 2)
1373 if (dump_file && (dump_flags & TDF_DETAILS))
1374 fprintf (dump_file, "less than 2 basic blocks\n");
1378 /* More than one loop exit is too much to handle. */
1379 if (!single_exit (loop))
1381 if (dump_file && (dump_flags & TDF_DETAILS))
1382 fprintf (dump_file, "multiple exits\n");
1386 /* If one of the loop header's edge is an exit edge then do not
1387 apply if-conversion. */
1388 FOR_EACH_EDGE (e, ei, loop->header->succs)
1389 if (loop_exit_edge_p (loop, e))
1394 auto_vec<loop_p, 3> loop_nest;
1395 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs,
1396 any_mask_load_store);
1398 data_reference_p dr;
1400 for (i = 0; refs.iterate (i, &dr); i++)
1403 free_data_refs (refs);
1404 free_dependence_relations (ddrs);
1408 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1409 which is in predicated basic block.
1410 In fact, the following PHI pattern is searching:
1412 reduc_1 = PHI <..., reduc_2>
1416 reduc_2 = PHI <reduc_1, reduc_3>
1418 ARG_0 and ARG_1 are correspondent PHI arguments.
1419 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1420 EXTENDED is true if PHI has > 2 arguments. */
1423 is_cond_scalar_reduction (gimple phi, gimple *reduc, tree arg_0, tree arg_1,
1424 tree *op0, tree *op1, bool extended)
1426 tree lhs, r_op1, r_op2;
1428 gimple header_phi = NULL;
1429 enum tree_code reduction_op;
1430 basic_block bb = gimple_bb (phi);
1431 struct loop *loop = bb->loop_father;
1432 edge latch_e = loop_latch_edge (loop);
1433 imm_use_iterator imm_iter;
1434 use_operand_p use_p;
1437 bool result = false;
1438 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1441 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1444 header_phi = SSA_NAME_DEF_STMT (arg_0);
1445 stmt = SSA_NAME_DEF_STMT (arg_1);
1447 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1450 header_phi = SSA_NAME_DEF_STMT (arg_1);
1451 stmt = SSA_NAME_DEF_STMT (arg_0);
1455 if (gimple_bb (header_phi) != loop->header)
1458 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1461 if (gimple_code (stmt) != GIMPLE_ASSIGN
1462 || gimple_has_volatile_ops (stmt))
1465 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1468 if (!is_predicated (gimple_bb (stmt)))
1471 /* Check that stmt-block is predecessor of phi-block. */
1472 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1481 if (!has_single_use (lhs))
1484 reduction_op = gimple_assign_rhs_code (stmt);
1485 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1487 r_op1 = gimple_assign_rhs1 (stmt);
1488 r_op2 = gimple_assign_rhs2 (stmt);
1490 /* Make R_OP1 to hold reduction variable. */
1491 if (r_op2 == PHI_RESULT (header_phi)
1492 && reduction_op == PLUS_EXPR)
1493 std::swap (r_op1, r_op2);
1494 else if (r_op1 != PHI_RESULT (header_phi))
1497 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1498 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1500 gimple use_stmt = USE_STMT (use_p);
1501 if (is_gimple_debug (use_stmt))
1503 if (use_stmt == stmt)
1505 if (gimple_code (use_stmt) != GIMPLE_PHI)
1509 *op0 = r_op1; *op1 = r_op2;
1514 /* Converts conditional scalar reduction into unconditional form, e.g.
1516 if (_5 != 0) goto bb_5 else goto bb_6
1522 # res_2 = PHI <res_13(4), res_6(5)>
1525 will be converted into sequence
1526 _ifc__1 = _5 != 0 ? 1 : 0;
1527 res_2 = res_13 + _ifc__1;
1528 Argument SWAP tells that arguments of conditional expression should be
1530 Returns rhs of resulting PHI assignment. */
1533 convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
1534 tree cond, tree op0, tree op1, bool swap)
1536 gimple_stmt_iterator stmt_it;
1539 tree rhs1 = gimple_assign_rhs1 (reduc);
1540 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1542 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1544 if (dump_file && (dump_flags & TDF_DETAILS))
1546 fprintf (dump_file, "Found cond scalar reduction.\n");
1547 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1550 /* Build cond expression using COND and constant operand
1551 of reduction rhs. */
1552 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1553 unshare_expr (cond),
1557 /* Create assignment stmt and insert it at GSI. */
1558 new_assign = gimple_build_assign (tmp, c);
1559 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1560 /* Build rhs for unconditional increment/decrement. */
1561 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1562 TREE_TYPE (rhs1), op0, tmp);
1564 /* Delete original reduction stmt. */
1565 stmt_it = gsi_for_stmt (reduc);
1566 gsi_remove (&stmt_it, true);
1567 release_defs (reduc);
1571 /* Produce condition for all occurrences of ARG in PHI node. */
1574 gen_phi_arg_condition (gphi *phi, vec<int> *occur,
1575 gimple_stmt_iterator *gsi)
1579 tree cond = NULL_TREE;
1583 len = occur->length ();
1584 gcc_assert (len > 0);
1585 for (i = 0; i < len; i++)
1587 e = gimple_phi_arg_edge (phi, (*occur)[i]);
1588 c = bb_predicate (e->src);
1589 if (is_true_predicate (c))
1591 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
1592 is_gimple_condexpr, NULL_TREE,
1593 true, GSI_SAME_STMT);
1594 if (cond != NULL_TREE)
1596 /* Must build OR expression. */
1597 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
1598 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1599 is_gimple_condexpr, NULL_TREE,
1600 true, GSI_SAME_STMT);
1605 gcc_assert (cond != NULL_TREE);
1609 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1610 This routine can handle PHI nodes with more than two arguments.
1613 S1: A = PHI <x1(1), x2(5)>
1615 S2: A = cond ? x1 : x2;
1617 The generated code is inserted at GSI that points to the top of
1618 basic block's statement list.
1619 If PHI node has more than two arguments a chain of conditional
1620 expression is produced. */
1624 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
1626 gimple new_stmt = NULL, reduc;
1627 tree rhs, res, arg0, arg1, op0, op1, scev;
1629 unsigned int index0;
1630 unsigned int max, args_len;
1635 res = gimple_phi_result (phi);
1636 if (virtual_operand_p (res))
1639 if ((rhs = degenerate_phi_result (phi))
1640 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1642 && !chrec_contains_undetermined (scev)
1644 && (rhs = gimple_phi_arg_def (phi, 0))))
1646 if (dump_file && (dump_flags & TDF_DETAILS))
1648 fprintf (dump_file, "Degenerate phi!\n");
1649 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1651 new_stmt = gimple_build_assign (res, rhs);
1652 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1653 update_stmt (new_stmt);
1657 bb = gimple_bb (phi);
1658 if (EDGE_COUNT (bb->preds) == 2)
1660 /* Predicate ordinary PHI node with 2 arguments. */
1661 edge first_edge, second_edge;
1662 basic_block true_bb;
1663 first_edge = EDGE_PRED (bb, 0);
1664 second_edge = EDGE_PRED (bb, 1);
1665 cond = bb_predicate (first_edge->src);
1666 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1667 std::swap (first_edge, second_edge);
1668 if (EDGE_COUNT (first_edge->src->succs) > 1)
1670 cond = bb_predicate (second_edge->src);
1671 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1672 cond = TREE_OPERAND (cond, 0);
1674 first_edge = second_edge;
1677 cond = bb_predicate (first_edge->src);
1678 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1679 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1680 is_gimple_condexpr, NULL_TREE,
1681 true, GSI_SAME_STMT);
1682 true_bb = first_edge->src;
1683 if (EDGE_PRED (bb, 1)->src == true_bb)
1685 arg0 = gimple_phi_arg_def (phi, 1);
1686 arg1 = gimple_phi_arg_def (phi, 0);
1690 arg0 = gimple_phi_arg_def (phi, 0);
1691 arg1 = gimple_phi_arg_def (phi, 1);
1693 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
1695 /* Convert reduction stmt into vectorizable form. */
1696 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1697 true_bb != gimple_bb (reduc));
1699 /* Build new RHS using selected condition and arguments. */
1700 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1702 new_stmt = gimple_build_assign (res, rhs);
1703 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1704 update_stmt (new_stmt);
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1708 fprintf (dump_file, "new phi replacement stmt\n");
1709 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1714 /* Create hashmap for PHI node which contain vector of argument indexes
1715 having the same value. */
1717 hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
1718 unsigned int num_args = gimple_phi_num_args (phi);
1720 /* Vector of different PHI argument values. */
1721 auto_vec<tree> args (num_args);
1723 /* Compute phi_arg_map. */
1724 for (i = 0; i < num_args; i++)
1728 arg = gimple_phi_arg_def (phi, i);
1729 if (!phi_arg_map.get (arg))
1730 args.quick_push (arg);
1731 phi_arg_map.get_or_insert (arg).safe_push (i);
1734 /* Determine element with max number of occurrences. */
1737 args_len = args.length ();
1738 for (i = 0; i < args_len; i++)
1741 if ((len = phi_arg_map.get (args[i])->length ()) > max)
1748 /* Put element with max number of occurences to the end of ARGS. */
1749 if (max_ind != -1 && max_ind +1 != (int) args_len)
1750 std::swap (args[args_len - 1], args[max_ind]);
1752 /* Handle one special case when number of arguments with different values
1753 is equal 2 and one argument has the only occurrence. Such PHI can be
1754 handled as if would have only 2 arguments. */
1755 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
1758 indexes = phi_arg_map.get (args[0]);
1759 index0 = (*indexes)[0];
1762 e = gimple_phi_arg_edge (phi, index0);
1763 cond = bb_predicate (e->src);
1764 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1767 cond = TREE_OPERAND (cond, 0);
1769 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1770 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1771 is_gimple_condexpr, NULL_TREE,
1772 true, GSI_SAME_STMT);
1773 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
1775 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1779 /* Convert reduction stmt into vectorizable form. */
1780 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1782 new_stmt = gimple_build_assign (res, rhs);
1783 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1784 update_stmt (new_stmt);
1790 tree type = TREE_TYPE (gimple_phi_result (phi));
1793 for (i = 0; i < args_len; i++)
1796 indexes = phi_arg_map.get (args[i]);
1797 if (i != args_len - 1)
1798 lhs = make_temp_ssa_name (type, NULL, "_ifc_");
1801 cond = gen_phi_arg_condition (phi, indexes, gsi);
1802 rhs = fold_build_cond_expr (type, unshare_expr (cond),
1804 new_stmt = gimple_build_assign (lhs, rhs);
1805 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1806 update_stmt (new_stmt);
1811 if (dump_file && (dump_flags & TDF_DETAILS))
1813 fprintf (dump_file, "new extended phi replacement stmt\n");
1814 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1818 /* Replaces in LOOP all the scalar phi nodes other than those in the
1819 LOOP->header block with conditional modify expressions. */
1822 predicate_all_scalar_phis (struct loop *loop)
1825 unsigned int orig_loop_num_nodes = loop->num_nodes;
1828 for (i = 1; i < orig_loop_num_nodes; i++)
1831 gimple_stmt_iterator gsi;
1832 gphi_iterator phi_gsi;
1835 if (bb == loop->header)
1838 if (EDGE_COUNT (bb->preds) == 1)
1841 phi_gsi = gsi_start_phis (bb);
1842 if (gsi_end_p (phi_gsi))
1845 gsi = gsi_after_labels (bb);
1846 while (!gsi_end_p (phi_gsi))
1848 phi = phi_gsi.phi ();
1849 predicate_scalar_phi (phi, &gsi);
1850 release_phi_node (phi);
1851 gsi_next (&phi_gsi);
1854 set_phi_nodes (bb, NULL);
1858 /* Insert in each basic block of LOOP the statements produced by the
1859 gimplification of the predicates. */
1862 insert_gimplified_predicates (loop_p loop, bool any_mask_load_store)
1866 for (i = 0; i < loop->num_nodes; i++)
1868 basic_block bb = ifc_bbs[i];
1870 if (!is_predicated (bb))
1871 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
1872 if (!is_predicated (bb))
1874 /* Do not insert statements for a basic block that is not
1875 predicated. Also make sure that the predicate of the
1876 basic block is set to true. */
1877 reset_bb_predicate (bb);
1881 stmts = bb_predicate_gimplified_stmts (bb);
1884 if (flag_tree_loop_if_convert_stores
1885 || any_mask_load_store)
1887 /* Insert the predicate of the BB just after the label,
1888 as the if-conversion of memory writes will use this
1890 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1891 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1895 /* Insert the predicate of the BB at the end of the BB
1896 as this would reduce the register pressure: the only
1897 use of this predicate will be in successor BBs. */
1898 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1901 || stmt_ends_bb_p (gsi_stmt (gsi)))
1902 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1904 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1907 /* Once the sequence is code generated, set it to NULL. */
1908 set_bb_predicate_gimplified_stmts (bb, NULL);
1913 /* Helper function for predicate_mem_writes. Returns index of existent
1914 mask if it was created for given SIZE and -1 otherwise. */
1917 mask_exists (int size, vec<int> vec)
1921 FOR_EACH_VEC_ELT (vec, ix, v)
1927 /* Predicate each write to memory in LOOP.
1929 This function transforms control flow constructs containing memory
1932 | for (i = 0; i < N; i++)
1936 into the following form that does not contain control flow:
1938 | for (i = 0; i < N; i++)
1939 | A[i] = cond ? expr : A[i];
1941 The original CFG looks like this:
1948 | if (i < N) goto bb_5 else goto bb_2
1952 | cond = some_computation;
1953 | if (cond) goto bb_3 else goto bb_4
1965 insert_gimplified_predicates inserts the computation of the COND
1966 expression at the beginning of the destination basic block:
1973 | if (i < N) goto bb_5 else goto bb_2
1977 | cond = some_computation;
1978 | if (cond) goto bb_3 else goto bb_4
1982 | cond = some_computation;
1991 predicate_mem_writes is then predicating the memory write as follows:
1998 | if (i < N) goto bb_5 else goto bb_2
2002 | if (cond) goto bb_3 else goto bb_4
2006 | cond = some_computation;
2007 | A[i] = cond ? expr : A[i];
2015 and finally combine_blocks removes the basic block boundaries making
2016 the loop vectorizable:
2020 | if (i < N) goto bb_5 else goto bb_1
2024 | cond = some_computation;
2025 | A[i] = cond ? expr : A[i];
2026 | if (i < N) goto bb_5 else goto bb_4
2035 predicate_mem_writes (loop_p loop)
2037 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2038 auto_vec<int, 1> vect_sizes;
2039 auto_vec<tree, 1> vect_masks;
2041 for (i = 1; i < orig_loop_num_nodes; i++)
2043 gimple_stmt_iterator gsi;
2044 basic_block bb = ifc_bbs[i];
2045 tree cond = bb_predicate (bb);
2050 if (is_true_predicate (cond))
2054 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2057 cond = TREE_OPERAND (cond, 0);
2060 vect_sizes.truncate (0);
2061 vect_masks.truncate (0);
2063 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2064 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
2066 else if (gimple_plf (stmt, GF_PLF_2))
2068 tree lhs = gimple_assign_lhs (stmt);
2069 tree rhs = gimple_assign_rhs1 (stmt);
2070 tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask;
2072 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
2073 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2074 mark_addressable (ref);
2075 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
2076 true, NULL_TREE, true,
2078 if (!vect_sizes.is_empty ()
2079 && (index = mask_exists (bitsize, vect_sizes)) != -1)
2080 /* Use created mask. */
2081 mask = vect_masks[index];
2084 masktype = build_nonstandard_integer_type (bitsize, 1);
2085 mask_op0 = build_int_cst (masktype, swap ? 0 : -1);
2086 mask_op1 = build_int_cst (masktype, swap ? -1 : 0);
2087 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2090 true, GSI_SAME_STMT);
2091 mask = fold_build_cond_expr (masktype, unshare_expr (cond),
2092 mask_op0, mask_op1);
2093 mask = ifc_temp_var (masktype, mask, &gsi);
2094 /* Save mask and its size for further use. */
2095 vect_sizes.safe_push (bitsize);
2096 vect_masks.safe_push (mask);
2098 ptr = build_int_cst (reference_alias_ptr_type (ref), 0);
2099 /* Copy points-to info if possible. */
2100 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2101 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2103 if (TREE_CODE (lhs) == SSA_NAME)
2106 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2108 gimple_call_set_lhs (new_stmt, lhs);
2112 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2114 gsi_replace (&gsi, new_stmt, true);
2116 else if (gimple_vdef (stmt))
2118 tree lhs = gimple_assign_lhs (stmt);
2119 tree rhs = gimple_assign_rhs1 (stmt);
2120 tree type = TREE_TYPE (lhs);
2122 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2123 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2125 std::swap (lhs, rhs);
2126 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2127 is_gimple_condexpr, NULL_TREE,
2128 true, GSI_SAME_STMT);
2129 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2130 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2136 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2137 other than the exit and latch of the LOOP. Also resets the
2138 GIMPLE_DEBUG information. */
2141 remove_conditions_and_labels (loop_p loop)
2143 gimple_stmt_iterator gsi;
2146 for (i = 0; i < loop->num_nodes; i++)
2148 basic_block bb = ifc_bbs[i];
2150 if (bb_with_exit_edge_p (loop, bb)
2151 || bb == loop->latch)
2154 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2155 switch (gimple_code (gsi_stmt (gsi)))
2159 gsi_remove (&gsi, true);
2163 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2164 if (gimple_debug_bind_p (gsi_stmt (gsi)))
2166 gimple_debug_bind_reset_value (gsi_stmt (gsi));
2167 update_stmt (gsi_stmt (gsi));
2178 /* Combine all the basic blocks from LOOP into one or two super basic
2179 blocks. Replace PHI nodes with conditional modify expressions. */
2182 combine_blocks (struct loop *loop, bool any_mask_load_store)
2184 basic_block bb, exit_bb, merge_target_bb;
2185 unsigned int orig_loop_num_nodes = loop->num_nodes;
2190 predicate_bbs (loop);
2191 remove_conditions_and_labels (loop);
2192 insert_gimplified_predicates (loop, any_mask_load_store);
2193 predicate_all_scalar_phis (loop);
2195 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2196 predicate_mem_writes (loop);
2198 /* Merge basic blocks: first remove all the edges in the loop,
2199 except for those from the exit block. */
2201 for (i = 0; i < orig_loop_num_nodes; i++)
2204 free_bb_predicate (bb);
2205 if (bb_with_exit_edge_p (loop, bb))
2207 gcc_assert (exit_bb == NULL);
2211 gcc_assert (exit_bb != loop->latch);
2213 for (i = 1; i < orig_loop_num_nodes; i++)
2217 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2219 if (e->src == exit_bb)
2226 if (exit_bb != NULL)
2228 if (exit_bb != loop->header)
2230 /* Connect this node to loop header. */
2231 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2232 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2235 /* Redirect non-exit edges to loop->latch. */
2236 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2238 if (!loop_exit_edge_p (loop, e))
2239 redirect_edge_and_branch (e, loop->latch);
2241 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2245 /* If the loop does not have an exit, reconnect header and latch. */
2246 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2247 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2250 merge_target_bb = loop->header;
2251 for (i = 1; i < orig_loop_num_nodes; i++)
2253 gimple_stmt_iterator gsi;
2254 gimple_stmt_iterator last;
2258 if (bb == exit_bb || bb == loop->latch)
2261 /* Make stmts member of loop->header. */
2262 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2263 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
2265 /* Update stmt list. */
2266 last = gsi_last_bb (merge_target_bb);
2267 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
2268 set_bb_seq (bb, NULL);
2270 delete_basic_block (bb);
2273 /* If possible, merge loop header to the block with the exit edge.
2274 This reduces the number of basic blocks to two, to please the
2275 vectorizer that handles only loops with two nodes. */
2277 && exit_bb != loop->header
2278 && can_merge_blocks_p (loop->header, exit_bb))
2279 merge_blocks (loop->header, exit_bb);
2285 /* Version LOOP before if-converting it, the original loop
2286 will be then if-converted, the new copy of the loop will not,
2287 and the LOOP_VECTORIZED internal call will be guarding which
2288 loop to execute. The vectorizer pass will fold this
2289 internal call into either true or false. */
2292 version_loop_for_if_conversion (struct loop *loop)
2294 basic_block cond_bb;
2295 tree cond = make_ssa_name (boolean_type_node);
2296 struct loop *new_loop;
2298 gimple_stmt_iterator gsi;
2300 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2301 build_int_cst (integer_type_node, loop->num),
2303 gimple_call_set_lhs (g, cond);
2305 initialize_original_copy_tables ();
2306 new_loop = loop_version (loop, cond, &cond_bb,
2307 REG_BR_PROB_BASE, REG_BR_PROB_BASE,
2308 REG_BR_PROB_BASE, true);
2309 free_original_copy_tables ();
2310 if (new_loop == NULL)
2312 new_loop->dont_vectorize = true;
2313 new_loop->force_vectorize = false;
2314 gsi = gsi_last_bb (cond_bb);
2315 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2316 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2317 update_ssa (TODO_update_ssa);
2321 /* Performs splitting of critical edges if aggressive_if_conv is true.
2322 Returns false if loop won't be if converted and true otherwise. */
2325 ifcvt_split_critical_edges (struct loop *loop)
2329 unsigned int num = loop->num_nodes;
2339 if (!single_exit (loop))
2342 body = get_loop_body (loop);
2343 for (i = 0; i < num; i++)
2346 if (bb == loop->latch
2347 || bb_with_exit_edge_p (loop, bb))
2349 stmt = last_stmt (bb);
2350 /* Skip basic blocks not ending with conditional branch. */
2351 if (!(stmt && gimple_code (stmt) == GIMPLE_COND))
2353 FOR_EACH_EDGE (e, ei, bb->succs)
2354 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
2361 /* Assumes that lhs of DEF_STMT have multiple uses.
2362 Delete one use by (1) creation of copy DEF_STMT with
2363 unique lhs; (2) change original use of lhs in one
2364 use statement with newly created lhs. */
2367 ifcvt_split_def_stmt (gimple def_stmt, gimple use_stmt)
2372 gimple_stmt_iterator gsi;
2373 use_operand_p use_p;
2374 imm_use_iterator imm_iter;
2376 var = gimple_assign_lhs (def_stmt);
2377 copy_stmt = gimple_copy (def_stmt);
2378 lhs = make_temp_ssa_name (TREE_TYPE (var), NULL, "_ifc_");
2379 gimple_assign_set_lhs (copy_stmt, lhs);
2380 SSA_NAME_DEF_STMT (lhs) = copy_stmt;
2381 /* Insert copy of DEF_STMT. */
2382 gsi = gsi_for_stmt (def_stmt);
2383 gsi_insert_after (&gsi, copy_stmt, GSI_SAME_STMT);
2384 /* Change use of var to lhs in use_stmt. */
2385 if (dump_file && (dump_flags & TDF_DETAILS))
2387 fprintf (dump_file, "Change use of var ");
2388 print_generic_expr (dump_file, var, TDF_SLIM);
2389 fprintf (dump_file, " to ");
2390 print_generic_expr (dump_file, lhs, TDF_SLIM);
2391 fprintf (dump_file, "\n");
2393 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
2395 if (USE_STMT (use_p) != use_stmt)
2397 SET_USE (use_p, lhs);
2402 /* Traverse bool pattern recursively starting from VAR.
2403 Save its def and use statements to defuse_list if VAR does
2404 not have single use. */
2407 ifcvt_walk_pattern_tree (tree var, vec<gimple> *defuse_list,
2411 enum tree_code code;
2414 def_stmt = SSA_NAME_DEF_STMT (var);
2415 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2417 if (!has_single_use (var))
2419 /* Put def and use stmts into defuse_list. */
2420 defuse_list->safe_push (def_stmt);
2421 defuse_list->safe_push (use_stmt);
2422 if (dump_file && (dump_flags & TDF_DETAILS))
2424 fprintf (dump_file, "Multiple lhs uses in stmt\n");
2425 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
2428 rhs1 = gimple_assign_rhs1 (def_stmt);
2429 code = gimple_assign_rhs_code (def_stmt);
2433 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2436 if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2437 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2438 && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
2440 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2443 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2448 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2449 rhs2 = gimple_assign_rhs2 (def_stmt);
2450 ifcvt_walk_pattern_tree (rhs2, defuse_list, def_stmt);
2458 /* Returns true if STMT can be a root of bool pattern apllied
2462 stmt_is_root_of_bool_pattern (gimple stmt)
2464 enum tree_code code;
2467 code = gimple_assign_rhs_code (stmt);
2468 if (CONVERT_EXPR_CODE_P (code))
2470 lhs = gimple_assign_lhs (stmt);
2471 rhs = gimple_assign_rhs1 (stmt);
2472 if (TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
2474 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
2478 else if (code == COND_EXPR)
2480 rhs = gimple_assign_rhs1 (stmt);
2481 if (TREE_CODE (rhs) != SSA_NAME)
2488 /* Traverse all statements in BB which correspondent to loop header to
2489 find out all statements which can start bool pattern applied by
2490 vectorizer and convert multiple uses in it to conform pattern
2491 restrictions. Such case can occur if the same predicate is used both
2492 for phi node conversion and load/store mask. */
2495 ifcvt_repair_bool_pattern (basic_block bb)
2499 gimple_stmt_iterator gsi;
2500 vec<gimple> defuse_list = vNULL;
2501 vec<gimple> pattern_roots = vNULL;
2506 /* Collect all root pattern statements. */
2507 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2509 stmt = gsi_stmt (gsi);
2510 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2512 if (!stmt_is_root_of_bool_pattern (stmt))
2514 pattern_roots.safe_push (stmt);
2517 if (pattern_roots.is_empty ())
2520 /* Split all statements with multiple uses iteratively since splitting
2521 may create new multiple uses. */
2526 FOR_EACH_VEC_ELT (pattern_roots, ix, stmt)
2528 rhs = gimple_assign_rhs1 (stmt);
2529 ifcvt_walk_pattern_tree (rhs, &defuse_list, stmt);
2530 while (defuse_list.length () > 0)
2533 gimple def_stmt, use_stmt;
2534 use_stmt = defuse_list.pop ();
2535 def_stmt = defuse_list.pop ();
2536 ifcvt_split_def_stmt (def_stmt, use_stmt);
2541 if (dump_file && (dump_flags & TDF_DETAILS))
2542 fprintf (dump_file, "Repair bool pattern takes %d iterations. \n",
2546 /* Delete redundant statements produced by predication which prevents
2547 loop vectorization. */
2550 ifcvt_local_dce (basic_block bb)
2555 gimple_stmt_iterator gsi;
2556 vec<gimple> worklist;
2557 enum gimple_code code;
2558 use_operand_p use_p;
2559 imm_use_iterator imm_iter;
2561 worklist.create (64);
2562 /* Consider all phi as live statements. */
2563 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2565 phi = gsi_stmt (gsi);
2566 gimple_set_plf (phi, GF_PLF_2, true);
2567 worklist.safe_push (phi);
2569 /* Consider load/store statemnts, CALL and COND as live. */
2570 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2572 stmt = gsi_stmt (gsi);
2573 if (gimple_store_p (stmt)
2574 || gimple_assign_load_p (stmt)
2575 || is_gimple_debug (stmt))
2577 gimple_set_plf (stmt, GF_PLF_2, true);
2578 worklist.safe_push (stmt);
2581 code = gimple_code (stmt);
2582 if (code == GIMPLE_COND || code == GIMPLE_CALL)
2584 gimple_set_plf (stmt, GF_PLF_2, true);
2585 worklist.safe_push (stmt);
2588 gimple_set_plf (stmt, GF_PLF_2, false);
2590 if (code == GIMPLE_ASSIGN)
2592 tree lhs = gimple_assign_lhs (stmt);
2593 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2595 stmt1 = USE_STMT (use_p);
2596 if (gimple_bb (stmt1) != bb)
2598 gimple_set_plf (stmt, GF_PLF_2, true);
2599 worklist.safe_push (stmt);
2605 /* Propagate liveness through arguments of live stmt. */
2606 while (worklist.length () > 0)
2609 use_operand_p use_p;
2612 stmt = worklist.pop ();
2613 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2615 use = USE_FROM_PTR (use_p);
2616 if (TREE_CODE (use) != SSA_NAME)
2618 stmt1 = SSA_NAME_DEF_STMT (use);
2619 if (gimple_bb (stmt1) != bb
2620 || gimple_plf (stmt1, GF_PLF_2))
2622 gimple_set_plf (stmt1, GF_PLF_2, true);
2623 worklist.safe_push (stmt1);
2626 /* Delete dead statements. */
2627 gsi = gsi_start_bb (bb);
2628 while (!gsi_end_p (gsi))
2630 stmt = gsi_stmt (gsi);
2631 if (gimple_plf (stmt, GF_PLF_2))
2636 if (dump_file && (dump_flags & TDF_DETAILS))
2638 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
2639 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2641 gsi_remove (&gsi, true);
2642 release_defs (stmt);
2646 /* If-convert LOOP when it is legal. For the moment this pass has no
2647 profitability analysis. Returns non-zero todo flags when something
2651 tree_if_conversion (struct loop *loop)
2653 unsigned int todo = 0;
2655 bool any_mask_load_store = false;
2657 /* Set-up aggressive if-conversion for loops marked with simd pragma. */
2658 aggressive_if_conv = loop->force_vectorize;
2659 /* Check either outer loop was marked with simd pragma. */
2660 if (!aggressive_if_conv)
2662 struct loop *outer_loop = loop_outer (loop);
2663 if (outer_loop && outer_loop->force_vectorize)
2664 aggressive_if_conv = true;
2667 if (aggressive_if_conv)
2668 if (!ifcvt_split_critical_edges (loop))
2671 if (!if_convertible_loop_p (loop, &any_mask_load_store)
2672 || !dbg_cnt (if_conversion_tree))
2675 if (any_mask_load_store
2676 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
2677 || loop->dont_vectorize))
2680 if (any_mask_load_store && !version_loop_for_if_conversion (loop))
2683 /* Now all statements are if-convertible. Combine all the basic
2684 blocks into one huge basic block doing the if-conversion
2686 combine_blocks (loop, any_mask_load_store);
2688 /* Delete dead predicate computations and repair tree correspondent
2689 to bool pattern to delete multiple uses of preidcates. */
2690 if (aggressive_if_conv)
2692 ifcvt_local_dce (loop->header);
2693 ifcvt_repair_bool_pattern (loop->header);
2696 todo |= TODO_cleanup_cfg;
2697 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2699 mark_virtual_operands_for_renaming (cfun);
2700 todo |= TODO_update_ssa_only_virtuals;
2708 for (i = 0; i < loop->num_nodes; i++)
2709 free_bb_predicate (ifc_bbs[i]);
2714 free_dominance_info (CDI_POST_DOMINATORS);
2719 /* Tree if-conversion pass management. */
2723 const pass_data pass_data_if_conversion =
2725 GIMPLE_PASS, /* type */
2727 OPTGROUP_NONE, /* optinfo_flags */
2728 TV_NONE, /* tv_id */
2729 ( PROP_cfg | PROP_ssa ), /* properties_required */
2730 0, /* properties_provided */
2731 0, /* properties_destroyed */
2732 0, /* todo_flags_start */
2733 0, /* todo_flags_finish */
2736 class pass_if_conversion : public gimple_opt_pass
2739 pass_if_conversion (gcc::context *ctxt)
2740 : gimple_opt_pass (pass_data_if_conversion, ctxt)
2743 /* opt_pass methods: */
2744 virtual bool gate (function *);
2745 virtual unsigned int execute (function *);
2747 }; // class pass_if_conversion
2750 pass_if_conversion::gate (function *fun)
2752 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
2753 && flag_tree_loop_if_convert != 0)
2754 || flag_tree_loop_if_convert == 1
2755 || flag_tree_loop_if_convert_stores == 1);
2759 pass_if_conversion::execute (function *fun)
2764 if (number_of_loops (fun) <= 1)
2767 FOR_EACH_LOOP (loop, 0)
2768 if (flag_tree_loop_if_convert == 1
2769 || flag_tree_loop_if_convert_stores == 1
2770 || ((flag_tree_loop_vectorize || loop->force_vectorize)
2771 && !loop->dont_vectorize))
2772 todo |= tree_if_conversion (loop);
2774 #ifdef ENABLE_CHECKING
2777 FOR_EACH_BB_FN (bb, fun)
2778 gcc_assert (!bb->aux);
2788 make_pass_if_conversion (gcc::context *ctxt)
2790 return new pass_if_conversion (ctxt);