1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
90 #include "fold-const.h"
91 #include "stor-layout.h"
94 #include "hard-reg-set.h"
96 #include "dominance.h"
98 #include "basic-block.h"
99 #include "gimple-pretty-print.h"
100 #include "tree-ssa-alias.h"
101 #include "internal-fn.h"
102 #include "gimple-fold.h"
103 #include "gimple-expr.h"
105 #include "gimplify.h"
106 #include "gimple-iterator.h"
107 #include "gimplify-me.h"
108 #include "gimple-ssa.h"
109 #include "tree-cfg.h"
110 #include "tree-phinodes.h"
111 #include "ssa-iterators.h"
112 #include "stringpool.h"
113 #include "tree-ssanames.h"
114 #include "tree-into-ssa.h"
115 #include "tree-ssa.h"
117 #include "tree-chrec.h"
118 #include "tree-data-ref.h"
119 #include "tree-scalar-evolution.h"
120 #include "tree-ssa-loop-ivopts.h"
121 #include "tree-ssa-address.h"
122 #include "tree-pass.h"
125 #include "insn-config.h"
130 #include "emit-rtl.h"
134 #include "insn-codes.h"
137 /* List of basic blocks in if-conversion-suitable order. */
138 static basic_block *ifc_bbs;
140 /* Apply more aggressive (extended) if-conversion if true. */
141 static bool aggressive_if_conv;
143 /* Structure used to predicate basic blocks. This is attached to the
144 ->aux field of the BBs in the loop to be if-converted. */
145 typedef struct bb_predicate_s {
147 /* The condition under which this basic block is executed. */
150 /* PREDICATE is gimplified, and the sequence of statements is
151 recorded here, in order to avoid the duplication of computations
152 that occur in previous conditions. See PR44483. */
153 gimple_seq predicate_gimplified_stmts;
156 /* Returns true when the basic block BB has a predicate. */
159 bb_has_predicate (basic_block bb)
161 return bb->aux != NULL;
164 /* Returns the gimplified predicate for basic block BB. */
167 bb_predicate (basic_block bb)
169 return ((bb_predicate_p) bb->aux)->predicate;
172 /* Sets the gimplified predicate COND for basic block BB. */
175 set_bb_predicate (basic_block bb, tree cond)
177 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
178 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
179 || is_gimple_condexpr (cond));
180 ((bb_predicate_p) bb->aux)->predicate = cond;
183 /* Returns the sequence of statements of the gimplification of the
184 predicate for basic block BB. */
186 static inline gimple_seq
187 bb_predicate_gimplified_stmts (basic_block bb)
189 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts;
192 /* Sets the sequence of statements STMTS of the gimplification of the
193 predicate for basic block BB. */
196 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
198 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts;
201 /* Adds the sequence of statements STMTS to the sequence of statements
202 of the predicate for basic block BB. */
205 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
208 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts);
211 /* Initializes to TRUE the predicate of basic block BB. */
214 init_bb_predicate (basic_block bb)
216 bb->aux = XNEW (struct bb_predicate_s);
217 set_bb_predicate_gimplified_stmts (bb, NULL);
218 set_bb_predicate (bb, boolean_true_node);
221 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
222 but don't actually free it. */
225 release_bb_predicate (basic_block bb)
227 gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
230 gimple_stmt_iterator i;
232 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
233 free_stmt_operands (cfun, gsi_stmt (i));
234 set_bb_predicate_gimplified_stmts (bb, NULL);
238 /* Free the predicate of basic block BB. */
241 free_bb_predicate (basic_block bb)
243 if (!bb_has_predicate (bb))
246 release_bb_predicate (bb);
251 /* Reinitialize predicate of BB with the true predicate. */
254 reset_bb_predicate (basic_block bb)
256 if (!bb_has_predicate (bb))
257 init_bb_predicate (bb);
260 release_bb_predicate (bb);
261 set_bb_predicate (bb, boolean_true_node);
265 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
266 the expression EXPR. Inserts the statement created for this
267 computation before GSI and leaves the iterator GSI at the same
271 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
273 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
274 gimple stmt = gimple_build_assign (new_name, expr);
275 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
279 /* Return true when COND is a true predicate. */
282 is_true_predicate (tree cond)
284 return (cond == NULL_TREE
285 || cond == boolean_true_node
286 || integer_onep (cond));
289 /* Returns true when BB has a predicate that is not trivial: true or
293 is_predicated (basic_block bb)
295 return !is_true_predicate (bb_predicate (bb));
298 /* Parses the predicate COND and returns its comparison code and
299 operands OP0 and OP1. */
301 static enum tree_code
302 parse_predicate (tree cond, tree *op0, tree *op1)
306 if (TREE_CODE (cond) == SSA_NAME
307 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
309 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
311 *op0 = gimple_assign_rhs1 (s);
312 *op1 = gimple_assign_rhs2 (s);
313 return gimple_assign_rhs_code (s);
316 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
318 tree op = gimple_assign_rhs1 (s);
319 tree type = TREE_TYPE (op);
320 enum tree_code code = parse_predicate (op, op0, op1);
322 return code == ERROR_MARK ? ERROR_MARK
323 : invert_tree_comparison (code, HONOR_NANS (type));
329 if (COMPARISON_CLASS_P (cond))
331 *op0 = TREE_OPERAND (cond, 0);
332 *op1 = TREE_OPERAND (cond, 1);
333 return TREE_CODE (cond);
339 /* Returns the fold of predicate C1 OR C2 at location LOC. */
342 fold_or_predicates (location_t loc, tree c1, tree c2)
344 tree op1a, op1b, op2a, op2b;
345 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
346 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
348 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
350 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
356 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
359 /* Returns true if N is either a constant or a SSA_NAME. */
362 constant_or_ssa_name (tree n)
364 switch (TREE_CODE (n))
377 /* Returns either a COND_EXPR or the folded expression if the folded
378 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
379 a constant or a SSA_NAME. */
382 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
384 tree rhs1, lhs1, cond_expr;
386 /* If COND is comparison r != 0 and r has boolean type, convert COND
387 to SSA_NAME to accept by vect bool pattern. */
388 if (TREE_CODE (cond) == NE_EXPR)
390 tree op0 = TREE_OPERAND (cond, 0);
391 tree op1 = TREE_OPERAND (cond, 1);
392 if (TREE_CODE (op0) == SSA_NAME
393 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
394 && (integer_zerop (op1)))
397 cond_expr = fold_ternary (COND_EXPR, type, cond,
400 if (cond_expr == NULL_TREE)
401 return build3 (COND_EXPR, type, cond, rhs, lhs);
403 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
405 if (constant_or_ssa_name (cond_expr))
408 if (TREE_CODE (cond_expr) == ABS_EXPR)
410 rhs1 = TREE_OPERAND (cond_expr, 1);
411 STRIP_USELESS_TYPE_CONVERSION (rhs1);
412 if (constant_or_ssa_name (rhs1))
413 return build1 (ABS_EXPR, type, rhs1);
416 if (TREE_CODE (cond_expr) == MIN_EXPR
417 || TREE_CODE (cond_expr) == MAX_EXPR)
419 lhs1 = TREE_OPERAND (cond_expr, 0);
420 STRIP_USELESS_TYPE_CONVERSION (lhs1);
421 rhs1 = TREE_OPERAND (cond_expr, 1);
422 STRIP_USELESS_TYPE_CONVERSION (rhs1);
423 if (constant_or_ssa_name (rhs1)
424 && constant_or_ssa_name (lhs1))
425 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
427 return build3 (COND_EXPR, type, cond, rhs, lhs);
430 /* Add condition NC to the predicate list of basic block BB. LOOP is
431 the loop to be if-converted. Use predicate of cd-equivalent block
432 for join bb if it exists: we call basic blocks bb1 and bb2
433 cd-equivalent if they are executed under the same condition. */
436 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
441 if (is_true_predicate (nc))
444 /* If dominance tells us this basic block is always executed,
445 don't record any predicates for it. */
446 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
449 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
450 /* We use notion of cd equivalence to get simpler predicate for
451 join block, e.g. if join block has 2 predecessors with predicates
452 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
453 p1 & p2 | p1 & !p2. */
454 if (dom_bb != loop->header
455 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
457 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
458 bc = bb_predicate (dom_bb);
459 if (!is_true_predicate (bc))
460 set_bb_predicate (bb, bc);
462 gcc_assert (is_true_predicate (bb_predicate (bb)));
463 if (dump_file && (dump_flags & TDF_DETAILS))
464 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
465 dom_bb->index, bb->index);
469 if (!is_predicated (bb))
473 bc = bb_predicate (bb);
474 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
475 if (is_true_predicate (bc))
477 reset_bb_predicate (bb);
482 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
483 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
484 tp = &TREE_OPERAND (bc, 0);
487 if (!is_gimple_condexpr (*tp))
490 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
491 add_bb_predicate_gimplified_stmts (bb, stmts);
493 set_bb_predicate (bb, bc);
496 /* Add the condition COND to the previous condition PREV_COND, and add
497 this to the predicate list of the destination of edge E. LOOP is
498 the loop to be if-converted. */
501 add_to_dst_predicate_list (struct loop *loop, edge e,
502 tree prev_cond, tree cond)
504 if (!flow_bb_inside_loop_p (loop, e->dest))
507 if (!is_true_predicate (prev_cond))
508 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
511 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
512 add_to_predicate_list (loop, e->dest, cond);
515 /* Return true if one of the successor edges of BB exits LOOP. */
518 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
523 FOR_EACH_EDGE (e, ei, bb->succs)
524 if (loop_exit_edge_p (loop, e))
530 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
531 and it belongs to basic block BB.
533 PHI is not if-convertible if:
534 - it has more than 2 arguments.
536 When the flag_tree_loop_if_convert_stores is not set, PHI is not
538 - a virtual PHI is immediately used in another PHI node,
539 - there is a virtual PHI in a BB other than the loop->header.
540 When the aggressive_if_conv is set, PHI can have more than
544 if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi,
545 bool any_mask_load_store)
547 if (dump_file && (dump_flags & TDF_DETAILS))
549 fprintf (dump_file, "-------------------------\n");
550 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
553 if (bb != loop->header)
555 if (gimple_phi_num_args (phi) != 2
556 && !aggressive_if_conv)
558 if (dump_file && (dump_flags & TDF_DETAILS))
559 fprintf (dump_file, "More than two phi node args.\n");
564 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
567 /* When the flag_tree_loop_if_convert_stores is not set, check
568 that there are no memory writes in the branches of the loop to be
570 if (virtual_operand_p (gimple_phi_result (phi)))
572 imm_use_iterator imm_iter;
575 if (bb != loop->header)
577 if (dump_file && (dump_flags & TDF_DETAILS))
578 fprintf (dump_file, "Virtual phi not on loop->header.\n");
582 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
584 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
585 && USE_STMT (use_p) != (gimple) phi)
587 if (dump_file && (dump_flags & TDF_DETAILS))
588 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
597 /* Records the status of a data reference. This struct is attached to
598 each DR->aux field. */
601 /* -1 when not initialized, 0 when false, 1 when true. */
602 int written_at_least_once;
604 /* -1 when not initialized, 0 when false, 1 when true. */
605 int rw_unconditionally;
608 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
609 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
610 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
612 /* Returns true when the memory references of STMT are read or written
613 unconditionally. In other words, this function returns true when
614 for every data reference A in STMT there exist other accesses to
615 a data reference with the same base with predicates that add up (OR-up) to
616 the true predicate: this ensures that the data reference A is touched
617 (read or written) on every iteration of the if-converted loop. */
620 memrefs_read_or_written_unconditionally (gimple stmt,
621 vec<data_reference_p> drs)
624 data_reference_p a, b;
625 tree ca = bb_predicate (gimple_bb (stmt));
627 for (i = 0; drs.iterate (i, &a); i++)
628 if (DR_STMT (a) == stmt)
631 int x = DR_RW_UNCONDITIONALLY (a);
639 for (j = 0; drs.iterate (j, &b); j++)
641 tree ref_base_a = DR_REF (a);
642 tree ref_base_b = DR_REF (b);
644 if (DR_STMT (b) == stmt)
647 while (TREE_CODE (ref_base_a) == COMPONENT_REF
648 || TREE_CODE (ref_base_a) == IMAGPART_EXPR
649 || TREE_CODE (ref_base_a) == REALPART_EXPR)
650 ref_base_a = TREE_OPERAND (ref_base_a, 0);
652 while (TREE_CODE (ref_base_b) == COMPONENT_REF
653 || TREE_CODE (ref_base_b) == IMAGPART_EXPR
654 || TREE_CODE (ref_base_b) == REALPART_EXPR)
655 ref_base_b = TREE_OPERAND (ref_base_b, 0);
657 if (!operand_equal_p (ref_base_a, ref_base_b, 0))
659 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
661 if (DR_RW_UNCONDITIONALLY (b) == 1
662 || is_true_predicate (cb)
663 || is_true_predicate (ca
664 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
666 DR_RW_UNCONDITIONALLY (a) = 1;
667 DR_RW_UNCONDITIONALLY (b) = 1;
676 DR_RW_UNCONDITIONALLY (a) = 0;
684 /* Returns true when the memory references of STMT are unconditionally
685 written. In other words, this function returns true when for every
686 data reference A written in STMT, there exist other writes to the
687 same data reference with predicates that add up (OR-up) to the true
688 predicate: this ensures that the data reference A is written on
689 every iteration of the if-converted loop. */
692 write_memrefs_written_at_least_once (gimple stmt,
693 vec<data_reference_p> drs)
696 data_reference_p a, b;
697 tree ca = bb_predicate (gimple_bb (stmt));
699 for (i = 0; drs.iterate (i, &a); i++)
700 if (DR_STMT (a) == stmt
704 int x = DR_WRITTEN_AT_LEAST_ONCE (a);
712 for (j = 0; drs.iterate (j, &b); j++)
713 if (DR_STMT (b) != stmt
715 && same_data_refs_base_objects (a, b))
717 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
719 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
720 || is_true_predicate (cb)
721 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
724 DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
725 DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
733 DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
741 /* Return true when the memory references of STMT won't trap in the
742 if-converted code. There are two things that we have to check for:
744 - writes to memory occur to writable memory: if-conversion of
745 memory writes transforms the conditional memory writes into
746 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
747 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
748 be executed at all in the original code, it may be a readonly
749 memory. To check that A is not const-qualified, we check that
750 there exists at least an unconditional write to A in the current
753 - reads or writes to memory are valid memory accesses for every
754 iteration. To check that the memory accesses are correctly formed
755 and that we are allowed to read and write in these locations, we
756 check that the memory accesses to be if-converted occur at every
757 iteration unconditionally. */
760 ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs)
762 return write_memrefs_written_at_least_once (stmt, refs)
763 && memrefs_read_or_written_unconditionally (stmt, refs);
766 /* Wrapper around gimple_could_trap_p refined for the needs of the
767 if-conversion. Try to prove that the memory accesses of STMT could
768 not trap in the innermost loop containing STMT. */
771 ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs)
773 if (gimple_vuse (stmt)
774 && !gimple_could_trap_p_1 (stmt, false, false)
775 && ifcvt_memrefs_wont_trap (stmt, refs))
778 return gimple_could_trap_p (stmt);
781 /* Return true if STMT could be converted into a masked load or store
782 (conditional load or store based on a mask computed from bb predicate). */
785 ifcvt_can_use_mask_load_store (gimple stmt)
789 basic_block bb = gimple_bb (stmt);
792 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
793 || bb->loop_father->dont_vectorize
794 || !gimple_assign_single_p (stmt)
795 || gimple_has_volatile_ops (stmt))
798 /* Check whether this is a load or store. */
799 lhs = gimple_assign_lhs (stmt);
800 if (gimple_store_p (stmt))
802 if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
807 else if (gimple_assign_load_p (stmt))
810 ref = gimple_assign_rhs1 (stmt);
815 if (may_be_nonaddressable_p (ref))
818 /* Mask should be integer mode of the same size as the load/store
820 mode = TYPE_MODE (TREE_TYPE (lhs));
821 if (int_mode_for_mode (mode) == BLKmode
822 || VECTOR_MODE_P (mode))
825 if (can_vec_mask_load_store_p (mode, is_load))
831 /* Return true when STMT is if-convertible.
833 GIMPLE_ASSIGN statement is not if-convertible if,
836 - LHS is not var decl. */
839 if_convertible_gimple_assign_stmt_p (gimple stmt,
840 vec<data_reference_p> refs,
841 bool *any_mask_load_store)
843 tree lhs = gimple_assign_lhs (stmt);
846 if (dump_file && (dump_flags & TDF_DETAILS))
848 fprintf (dump_file, "-------------------------\n");
849 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
852 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
855 /* Some of these constrains might be too conservative. */
856 if (stmt_ends_bb_p (stmt)
857 || gimple_has_volatile_ops (stmt)
858 || (TREE_CODE (lhs) == SSA_NAME
859 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
860 || gimple_has_side_effects (stmt))
862 if (dump_file && (dump_flags & TDF_DETAILS))
863 fprintf (dump_file, "stmt not suitable for ifcvt\n");
867 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
868 in between if_convertible_loop_p and combine_blocks
869 we can perform loop versioning. */
870 gimple_set_plf (stmt, GF_PLF_2, false);
872 if (flag_tree_loop_if_convert_stores)
874 if (ifcvt_could_trap_p (stmt, refs))
876 if (ifcvt_can_use_mask_load_store (stmt))
878 gimple_set_plf (stmt, GF_PLF_2, true);
879 *any_mask_load_store = true;
882 if (dump_file && (dump_flags & TDF_DETAILS))
883 fprintf (dump_file, "tree could trap...\n");
889 if (gimple_assign_rhs_could_trap_p (stmt))
891 if (ifcvt_can_use_mask_load_store (stmt))
893 gimple_set_plf (stmt, GF_PLF_2, true);
894 *any_mask_load_store = true;
897 if (dump_file && (dump_flags & TDF_DETAILS))
898 fprintf (dump_file, "tree could trap...\n");
902 bb = gimple_bb (stmt);
904 if (TREE_CODE (lhs) != SSA_NAME
905 && bb != bb->loop_father->header
906 && !bb_with_exit_edge_p (bb->loop_father, bb))
908 if (ifcvt_can_use_mask_load_store (stmt))
910 gimple_set_plf (stmt, GF_PLF_2, true);
911 *any_mask_load_store = true;
914 if (dump_file && (dump_flags & TDF_DETAILS))
916 fprintf (dump_file, "LHS is not var\n");
917 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
925 /* Return true when STMT is if-convertible.
927 A statement is if-convertible if:
928 - it is an if-convertible GIMPLE_ASSIGN,
929 - it is a GIMPLE_LABEL or a GIMPLE_COND,
930 - it is builtins call. */
933 if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs,
934 bool *any_mask_load_store)
936 switch (gimple_code (stmt))
944 return if_convertible_gimple_assign_stmt_p (stmt, refs,
945 any_mask_load_store);
949 tree fndecl = gimple_call_fndecl (stmt);
952 int flags = gimple_call_flags (stmt);
953 if ((flags & ECF_CONST)
954 && !(flags & ECF_LOOPING_CONST_OR_PURE)
955 /* We can only vectorize some builtins at the moment,
956 so restrict if-conversion to those. */
957 && DECL_BUILT_IN (fndecl))
964 /* Don't know what to do with 'em so don't do anything. */
965 if (dump_file && (dump_flags & TDF_DETAILS))
967 fprintf (dump_file, "don't know what to do\n");
968 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
977 /* Assumes that BB has more than 1 predecessors.
978 Returns false if at least one successor is not on critical edge
979 and true otherwise. */
982 all_preds_critical_p (basic_block bb)
987 FOR_EACH_EDGE (e, ei, bb->preds)
988 if (EDGE_COUNT (e->src->succs) == 1)
993 /* Returns true if at least one successor in on critical edge. */
995 has_pred_critical_p (basic_block bb)
1000 FOR_EACH_EDGE (e, ei, bb->preds)
1001 if (EDGE_COUNT (e->src->succs) > 1)
1006 /* Return true when BB is if-convertible. This routine does not check
1007 basic block's statements and phis.
1009 A basic block is not if-convertible if:
1010 - it is non-empty and it is after the exit block (in BFS order),
1011 - it is after the exit block but before the latch,
1012 - its edges are not normal.
1014 Last restriction is valid if aggressive_if_conv is false.
1016 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1020 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
1025 if (dump_file && (dump_flags & TDF_DETAILS))
1026 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1028 if (EDGE_COUNT (bb->succs) > 2)
1031 if (EDGE_COUNT (bb->preds) > 2
1032 && !aggressive_if_conv)
1037 if (bb != loop->latch)
1039 if (dump_file && (dump_flags & TDF_DETAILS))
1040 fprintf (dump_file, "basic block after exit bb but before latch\n");
1043 else if (!empty_block_p (bb))
1045 if (dump_file && (dump_flags & TDF_DETAILS))
1046 fprintf (dump_file, "non empty basic block after exit bb\n");
1049 else if (bb == loop->latch
1051 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1053 if (dump_file && (dump_flags & TDF_DETAILS))
1054 fprintf (dump_file, "latch is not dominated by exit_block\n");
1059 /* Be less adventurous and handle only normal edges. */
1060 FOR_EACH_EDGE (e, ei, bb->succs)
1061 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1063 if (dump_file && (dump_flags & TDF_DETAILS))
1064 fprintf (dump_file, "Difficult to handle edges\n");
1068 /* At least one incoming edge has to be non-critical as otherwise edge
1069 predicates are not equal to basic-block predicates of the edge
1070 source. This check is skipped if aggressive_if_conv is true. */
1071 if (!aggressive_if_conv
1072 && EDGE_COUNT (bb->preds) > 1
1073 && bb != loop->header
1074 && all_preds_critical_p (bb))
1076 if (dump_file && (dump_flags & TDF_DETAILS))
1077 fprintf (dump_file, "only critical predecessors\n");
1084 /* Return true when all predecessor blocks of BB are visited. The
1085 VISITED bitmap keeps track of the visited blocks. */
1088 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1092 FOR_EACH_EDGE (e, ei, bb->preds)
1093 if (!bitmap_bit_p (*visited, e->src->index))
1099 /* Get body of a LOOP in suitable order for if-conversion. It is
1100 caller's responsibility to deallocate basic block list.
1101 If-conversion suitable order is, breadth first sort (BFS) order
1102 with an additional constraint: select a block only if all its
1103 predecessors are already selected. */
1105 static basic_block *
1106 get_loop_body_in_if_conv_order (const struct loop *loop)
1108 basic_block *blocks, *blocks_in_bfs_order;
1111 unsigned int index = 0;
1112 unsigned int visited_count = 0;
1114 gcc_assert (loop->num_nodes);
1115 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1117 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1118 visited = BITMAP_ALLOC (NULL);
1120 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1123 while (index < loop->num_nodes)
1125 bb = blocks_in_bfs_order [index];
1127 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1129 free (blocks_in_bfs_order);
1130 BITMAP_FREE (visited);
1135 if (!bitmap_bit_p (visited, bb->index))
1137 if (pred_blocks_visited_p (bb, &visited)
1138 || bb == loop->header)
1140 /* This block is now visited. */
1141 bitmap_set_bit (visited, bb->index);
1142 blocks[visited_count++] = bb;
1148 if (index == loop->num_nodes
1149 && visited_count != loop->num_nodes)
1153 free (blocks_in_bfs_order);
1154 BITMAP_FREE (visited);
1158 /* Returns true when the analysis of the predicates for all the basic
1159 blocks in LOOP succeeded.
1161 predicate_bbs first allocates the predicates of the basic blocks.
1162 These fields are then initialized with the tree expressions
1163 representing the predicates under which a basic block is executed
1164 in the LOOP. As the loop->header is executed at each iteration, it
1165 has the "true" predicate. Other statements executed under a
1166 condition are predicated with that condition, for example
1173 S1 will be predicated with "x", and
1174 S2 will be predicated with "!x". */
1177 predicate_bbs (loop_p loop)
1181 for (i = 0; i < loop->num_nodes; i++)
1182 init_bb_predicate (ifc_bbs[i]);
1184 for (i = 0; i < loop->num_nodes; i++)
1186 basic_block bb = ifc_bbs[i];
1190 /* The loop latch and loop exit block are always executed and
1191 have no extra conditions to be processed: skip them. */
1192 if (bb == loop->latch
1193 || bb_with_exit_edge_p (loop, bb))
1195 reset_bb_predicate (bb);
1199 cond = bb_predicate (bb);
1200 stmt = last_stmt (bb);
1201 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1204 edge true_edge, false_edge;
1205 location_t loc = gimple_location (stmt);
1206 tree c = build2_loc (loc, gimple_cond_code (stmt),
1208 gimple_cond_lhs (stmt),
1209 gimple_cond_rhs (stmt));
1211 /* Add new condition into destination's predicate list. */
1212 extract_true_false_edges_from_block (gimple_bb (stmt),
1213 &true_edge, &false_edge);
1215 /* If C is true, then TRUE_EDGE is taken. */
1216 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1219 /* If C is false, then FALSE_EDGE is taken. */
1220 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1222 add_to_dst_predicate_list (loop, false_edge,
1223 unshare_expr (cond), c2);
1228 /* If current bb has only one successor, then consider it as an
1229 unconditional goto. */
1230 if (single_succ_p (bb))
1232 basic_block bb_n = single_succ (bb);
1234 /* The successor bb inherits the predicate of its
1235 predecessor. If there is no predicate in the predecessor
1236 bb, then consider the successor bb as always executed. */
1237 if (cond == NULL_TREE)
1238 cond = boolean_true_node;
1240 add_to_predicate_list (loop, bb_n, cond);
1244 /* The loop header is always executed. */
1245 reset_bb_predicate (loop->header);
1246 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1247 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1250 /* Return true when LOOP is if-convertible. This is a helper function
1251 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1252 in if_convertible_loop_p. */
1255 if_convertible_loop_p_1 (struct loop *loop,
1256 vec<loop_p> *loop_nest,
1257 vec<data_reference_p> *refs,
1258 vec<ddr_p> *ddrs, bool *any_mask_load_store)
1262 basic_block exit_bb = NULL;
1264 /* Don't if-convert the loop when the data dependences cannot be
1265 computed: the loop won't be vectorized in that case. */
1266 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
1270 calculate_dominance_info (CDI_DOMINATORS);
1271 calculate_dominance_info (CDI_POST_DOMINATORS);
1273 /* Allow statements that can be handled during if-conversion. */
1274 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1277 if (dump_file && (dump_flags & TDF_DETAILS))
1278 fprintf (dump_file, "Irreducible loop\n");
1282 for (i = 0; i < loop->num_nodes; i++)
1284 basic_block bb = ifc_bbs[i];
1286 if (!if_convertible_bb_p (loop, bb, exit_bb))
1289 if (bb_with_exit_edge_p (loop, bb))
1293 for (i = 0; i < loop->num_nodes; i++)
1295 basic_block bb = ifc_bbs[i];
1296 gimple_stmt_iterator gsi;
1298 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1299 switch (gimple_code (gsi_stmt (gsi)))
1312 if (flag_tree_loop_if_convert_stores)
1314 data_reference_p dr;
1316 for (i = 0; refs->iterate (i, &dr); i++)
1318 dr->aux = XNEW (struct ifc_dr);
1319 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1320 DR_RW_UNCONDITIONALLY (dr) = -1;
1322 predicate_bbs (loop);
1325 for (i = 0; i < loop->num_nodes; i++)
1327 basic_block bb = ifc_bbs[i];
1328 gimple_stmt_iterator itr;
1330 /* Check the if-convertibility of statements in predicated BBs. */
1331 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1332 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1333 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs,
1334 any_mask_load_store))
1338 if (flag_tree_loop_if_convert_stores)
1339 for (i = 0; i < loop->num_nodes; i++)
1340 free_bb_predicate (ifc_bbs[i]);
1342 /* Checking PHIs needs to be done after stmts, as the fact whether there
1343 are any masked loads or stores affects the tests. */
1344 for (i = 0; i < loop->num_nodes; i++)
1346 basic_block bb = ifc_bbs[i];
1349 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1350 if (!if_convertible_phi_p (loop, bb, itr.phi (),
1351 *any_mask_load_store))
1356 fprintf (dump_file, "Applying if-conversion\n");
1361 /* Return true when LOOP is if-convertible.
1362 LOOP is if-convertible if:
1364 - it has two or more basic blocks,
1365 - it has only one exit,
1366 - loop header is not the exit edge,
1367 - if its basic blocks and phi nodes are if convertible. */
1370 if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store)
1375 vec<data_reference_p> refs;
1378 /* Handle only innermost loop. */
1379 if (!loop || loop->inner)
1381 if (dump_file && (dump_flags & TDF_DETAILS))
1382 fprintf (dump_file, "not innermost loop\n");
1386 /* If only one block, no need for if-conversion. */
1387 if (loop->num_nodes <= 2)
1389 if (dump_file && (dump_flags & TDF_DETAILS))
1390 fprintf (dump_file, "less than 2 basic blocks\n");
1394 /* More than one loop exit is too much to handle. */
1395 if (!single_exit (loop))
1397 if (dump_file && (dump_flags & TDF_DETAILS))
1398 fprintf (dump_file, "multiple exits\n");
1402 /* If one of the loop header's edge is an exit edge then do not
1403 apply if-conversion. */
1404 FOR_EACH_EDGE (e, ei, loop->header->succs)
1405 if (loop_exit_edge_p (loop, e))
1410 auto_vec<loop_p, 3> loop_nest;
1411 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs,
1412 any_mask_load_store);
1414 if (flag_tree_loop_if_convert_stores)
1416 data_reference_p dr;
1419 for (i = 0; refs.iterate (i, &dr); i++)
1423 free_data_refs (refs);
1424 free_dependence_relations (ddrs);
1428 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1429 which is in predicated basic block.
1430 In fact, the following PHI pattern is searching:
1432 reduc_1 = PHI <..., reduc_2>
1436 reduc_2 = PHI <reduc_1, reduc_3>
1438 ARG_0 and ARG_1 are correspondent PHI arguments.
1439 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1440 EXTENDED is true if PHI has > 2 arguments. */
1443 is_cond_scalar_reduction (gimple phi, gimple *reduc, tree arg_0, tree arg_1,
1444 tree *op0, tree *op1, bool extended)
1446 tree lhs, r_op1, r_op2;
1448 gimple header_phi = NULL;
1449 enum tree_code reduction_op;
1450 basic_block bb = gimple_bb (phi);
1451 struct loop *loop = bb->loop_father;
1452 edge latch_e = loop_latch_edge (loop);
1453 imm_use_iterator imm_iter;
1454 use_operand_p use_p;
1457 bool result = false;
1458 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1461 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1464 header_phi = SSA_NAME_DEF_STMT (arg_0);
1465 stmt = SSA_NAME_DEF_STMT (arg_1);
1467 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1470 header_phi = SSA_NAME_DEF_STMT (arg_1);
1471 stmt = SSA_NAME_DEF_STMT (arg_0);
1475 if (gimple_bb (header_phi) != loop->header)
1478 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1481 if (gimple_code (stmt) != GIMPLE_ASSIGN
1482 || gimple_has_volatile_ops (stmt))
1485 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1488 if (!is_predicated (gimple_bb (stmt)))
1491 /* Check that stmt-block is predecessor of phi-block. */
1492 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1501 if (!has_single_use (lhs))
1504 reduction_op = gimple_assign_rhs_code (stmt);
1505 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1507 r_op1 = gimple_assign_rhs1 (stmt);
1508 r_op2 = gimple_assign_rhs2 (stmt);
1510 /* Make R_OP1 to hold reduction variable. */
1511 if (r_op2 == PHI_RESULT (header_phi)
1512 && reduction_op == PLUS_EXPR)
1518 else if (r_op1 != PHI_RESULT (header_phi))
1521 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1522 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1524 gimple use_stmt = USE_STMT (use_p);
1525 if (is_gimple_debug (use_stmt))
1527 if (use_stmt == stmt)
1529 if (gimple_code (use_stmt) != GIMPLE_PHI)
1533 *op0 = r_op1; *op1 = r_op2;
1538 /* Converts conditional scalar reduction into unconditional form, e.g.
1540 if (_5 != 0) goto bb_5 else goto bb_6
1546 # res_2 = PHI <res_13(4), res_6(5)>
1549 will be converted into sequence
1550 _ifc__1 = _5 != 0 ? 1 : 0;
1551 res_2 = res_13 + _ifc__1;
1552 Argument SWAP tells that arguments of conditional expression should be
1554 Returns rhs of resulting PHI assignment. */
1557 convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
1558 tree cond, tree op0, tree op1, bool swap)
1560 gimple_stmt_iterator stmt_it;
1563 tree rhs1 = gimple_assign_rhs1 (reduc);
1564 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1566 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1568 if (dump_file && (dump_flags & TDF_DETAILS))
1570 fprintf (dump_file, "Found cond scalar reduction.\n");
1571 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1574 /* Build cond expression using COND and constant operand
1575 of reduction rhs. */
1576 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1577 unshare_expr (cond),
1581 /* Create assignment stmt and insert it at GSI. */
1582 new_assign = gimple_build_assign (tmp, c);
1583 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1584 /* Build rhs for unconditional increment/decrement. */
1585 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1586 TREE_TYPE (rhs1), op0, tmp);
1588 /* Delete original reduction stmt. */
1589 stmt_it = gsi_for_stmt (reduc);
1590 gsi_remove (&stmt_it, true);
1591 release_defs (reduc);
1595 /* Helpers for PHI arguments hashtable map. */
1597 struct phi_args_hash_traits : default_hashmap_traits
1599 static inline hashval_t hash (tree);
1600 static inline bool equal_keys (tree, tree);
1604 phi_args_hash_traits::hash (tree value)
1606 return iterative_hash_expr (value, 0);
1610 phi_args_hash_traits::equal_keys (tree value1, tree value2)
1612 return operand_equal_p (value1, value2, 0);
1615 /* Produce condition for all occurrences of ARG in PHI node. */
1618 gen_phi_arg_condition (gphi *phi, vec<int> *occur,
1619 gimple_stmt_iterator *gsi)
1623 tree cond = NULL_TREE;
1627 len = occur->length ();
1628 gcc_assert (len > 0);
1629 for (i = 0; i < len; i++)
1631 e = gimple_phi_arg_edge (phi, (*occur)[i]);
1632 c = bb_predicate (e->src);
1633 if (is_true_predicate (c))
1635 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
1636 is_gimple_condexpr, NULL_TREE,
1637 true, GSI_SAME_STMT);
1638 if (cond != NULL_TREE)
1640 /* Must build OR expression. */
1641 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
1642 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1643 is_gimple_condexpr, NULL_TREE,
1644 true, GSI_SAME_STMT);
1649 gcc_assert (cond != NULL_TREE);
1653 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1654 This routine can handle PHI nodes with more than two arguments.
1657 S1: A = PHI <x1(1), x2(5)>
1659 S2: A = cond ? x1 : x2;
1661 The generated code is inserted at GSI that points to the top of
1662 basic block's statement list.
1663 If PHI node has more than two arguments a chain of conditional
1664 expression is produced. */
1668 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
1670 gimple new_stmt = NULL, reduc;
1671 tree rhs, res, arg0, arg1, op0, op1, scev;
1673 unsigned int index0;
1674 unsigned int max, args_len;
1679 res = gimple_phi_result (phi);
1680 if (virtual_operand_p (res))
1683 if ((rhs = degenerate_phi_result (phi))
1684 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1686 && !chrec_contains_undetermined (scev)
1688 && (rhs = gimple_phi_arg_def (phi, 0))))
1690 if (dump_file && (dump_flags & TDF_DETAILS))
1692 fprintf (dump_file, "Degenerate phi!\n");
1693 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1695 new_stmt = gimple_build_assign (res, rhs);
1696 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1697 update_stmt (new_stmt);
1701 bb = gimple_bb (phi);
1702 if (EDGE_COUNT (bb->preds) == 2)
1704 /* Predicate ordinary PHI node with 2 arguments. */
1705 edge first_edge, second_edge;
1706 basic_block true_bb;
1707 first_edge = EDGE_PRED (bb, 0);
1708 second_edge = EDGE_PRED (bb, 1);
1709 cond = bb_predicate (first_edge->src);
1710 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1712 edge tmp_edge = first_edge;
1713 first_edge = second_edge;
1714 second_edge = tmp_edge;
1716 if (EDGE_COUNT (first_edge->src->succs) > 1)
1718 cond = bb_predicate (second_edge->src);
1719 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1720 cond = TREE_OPERAND (cond, 0);
1722 first_edge = second_edge;
1725 cond = bb_predicate (first_edge->src);
1726 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1727 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1728 is_gimple_condexpr, NULL_TREE,
1729 true, GSI_SAME_STMT);
1730 true_bb = first_edge->src;
1731 if (EDGE_PRED (bb, 1)->src == true_bb)
1733 arg0 = gimple_phi_arg_def (phi, 1);
1734 arg1 = gimple_phi_arg_def (phi, 0);
1738 arg0 = gimple_phi_arg_def (phi, 0);
1739 arg1 = gimple_phi_arg_def (phi, 1);
1741 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
1743 /* Convert reduction stmt into vectorizable form. */
1744 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1745 true_bb != gimple_bb (reduc));
1747 /* Build new RHS using selected condition and arguments. */
1748 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1750 new_stmt = gimple_build_assign (res, rhs);
1751 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1752 update_stmt (new_stmt);
1754 if (dump_file && (dump_flags & TDF_DETAILS))
1756 fprintf (dump_file, "new phi replacement stmt\n");
1757 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1762 /* Create hashmap for PHI node which contain vector of argument indexes
1763 having the same value. */
1765 hash_map<tree, auto_vec<int>, phi_args_hash_traits> phi_arg_map;
1766 unsigned int num_args = gimple_phi_num_args (phi);
1768 /* Vector of different PHI argument values. */
1769 auto_vec<tree> args (num_args);
1771 /* Compute phi_arg_map. */
1772 for (i = 0; i < num_args; i++)
1776 arg = gimple_phi_arg_def (phi, i);
1777 if (!phi_arg_map.get (arg))
1778 args.quick_push (arg);
1779 phi_arg_map.get_or_insert (arg).safe_push (i);
1782 /* Determine element with max number of occurrences. */
1785 args_len = args.length ();
1786 for (i = 0; i < args_len; i++)
1789 if ((len = phi_arg_map.get (args[i])->length ()) > max)
1796 /* Put element with max number of occurences to the end of ARGS. */
1797 if (max_ind != -1 && max_ind +1 != (int) args_len)
1799 tree tmp = args[args_len - 1];
1800 args[args_len - 1] = args[max_ind];
1801 args[max_ind] = tmp;
1804 /* Handle one special case when number of arguments with different values
1805 is equal 2 and one argument has the only occurrence. Such PHI can be
1806 handled as if would have only 2 arguments. */
1807 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
1810 indexes = phi_arg_map.get (args[0]);
1811 index0 = (*indexes)[0];
1814 e = gimple_phi_arg_edge (phi, index0);
1815 cond = bb_predicate (e->src);
1816 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1819 cond = TREE_OPERAND (cond, 0);
1821 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1822 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1823 is_gimple_condexpr, NULL_TREE,
1824 true, GSI_SAME_STMT);
1825 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
1827 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1831 /* Convert reduction stmt into vectorizable form. */
1832 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1834 new_stmt = gimple_build_assign (res, rhs);
1835 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1836 update_stmt (new_stmt);
1842 tree type = TREE_TYPE (gimple_phi_result (phi));
1845 for (i = 0; i < args_len; i++)
1848 indexes = phi_arg_map.get (args[i]);
1849 if (i != args_len - 1)
1850 lhs = make_temp_ssa_name (type, NULL, "_ifc_");
1853 cond = gen_phi_arg_condition (phi, indexes, gsi);
1854 rhs = fold_build_cond_expr (type, unshare_expr (cond),
1856 new_stmt = gimple_build_assign (lhs, rhs);
1857 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1858 update_stmt (new_stmt);
1863 if (dump_file && (dump_flags & TDF_DETAILS))
1865 fprintf (dump_file, "new extended phi replacement stmt\n");
1866 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1870 /* Replaces in LOOP all the scalar phi nodes other than those in the
1871 LOOP->header block with conditional modify expressions. */
1874 predicate_all_scalar_phis (struct loop *loop)
1877 unsigned int orig_loop_num_nodes = loop->num_nodes;
1880 for (i = 1; i < orig_loop_num_nodes; i++)
1883 gimple_stmt_iterator gsi;
1884 gphi_iterator phi_gsi;
1887 if (bb == loop->header)
1890 if (EDGE_COUNT (bb->preds) == 1)
1893 phi_gsi = gsi_start_phis (bb);
1894 if (gsi_end_p (phi_gsi))
1897 gsi = gsi_after_labels (bb);
1898 while (!gsi_end_p (phi_gsi))
1900 phi = phi_gsi.phi ();
1901 predicate_scalar_phi (phi, &gsi);
1902 release_phi_node (phi);
1903 gsi_next (&phi_gsi);
1906 set_phi_nodes (bb, NULL);
1910 /* Insert in each basic block of LOOP the statements produced by the
1911 gimplification of the predicates. */
1914 insert_gimplified_predicates (loop_p loop, bool any_mask_load_store)
1918 for (i = 0; i < loop->num_nodes; i++)
1920 basic_block bb = ifc_bbs[i];
1922 if (!is_predicated (bb))
1923 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
1924 if (!is_predicated (bb))
1926 /* Do not insert statements for a basic block that is not
1927 predicated. Also make sure that the predicate of the
1928 basic block is set to true. */
1929 reset_bb_predicate (bb);
1933 stmts = bb_predicate_gimplified_stmts (bb);
1936 if (flag_tree_loop_if_convert_stores
1937 || any_mask_load_store)
1939 /* Insert the predicate of the BB just after the label,
1940 as the if-conversion of memory writes will use this
1942 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1943 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1947 /* Insert the predicate of the BB at the end of the BB
1948 as this would reduce the register pressure: the only
1949 use of this predicate will be in successor BBs. */
1950 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1953 || stmt_ends_bb_p (gsi_stmt (gsi)))
1954 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1956 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1959 /* Once the sequence is code generated, set it to NULL. */
1960 set_bb_predicate_gimplified_stmts (bb, NULL);
1965 /* Helper function for predicate_mem_writes. Returns index of existent
1966 mask if it was created for given SIZE and -1 otherwise. */
1969 mask_exists (int size, vec<int> vec)
1973 FOR_EACH_VEC_ELT (vec, ix, v)
1979 /* Predicate each write to memory in LOOP.
1981 This function transforms control flow constructs containing memory
1984 | for (i = 0; i < N; i++)
1988 into the following form that does not contain control flow:
1990 | for (i = 0; i < N; i++)
1991 | A[i] = cond ? expr : A[i];
1993 The original CFG looks like this:
2000 | if (i < N) goto bb_5 else goto bb_2
2004 | cond = some_computation;
2005 | if (cond) goto bb_3 else goto bb_4
2017 insert_gimplified_predicates inserts the computation of the COND
2018 expression at the beginning of the destination basic block:
2025 | if (i < N) goto bb_5 else goto bb_2
2029 | cond = some_computation;
2030 | if (cond) goto bb_3 else goto bb_4
2034 | cond = some_computation;
2043 predicate_mem_writes is then predicating the memory write as follows:
2050 | if (i < N) goto bb_5 else goto bb_2
2054 | if (cond) goto bb_3 else goto bb_4
2058 | cond = some_computation;
2059 | A[i] = cond ? expr : A[i];
2067 and finally combine_blocks removes the basic block boundaries making
2068 the loop vectorizable:
2072 | if (i < N) goto bb_5 else goto bb_1
2076 | cond = some_computation;
2077 | A[i] = cond ? expr : A[i];
2078 | if (i < N) goto bb_5 else goto bb_4
2087 predicate_mem_writes (loop_p loop)
2089 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2090 auto_vec<int, 1> vect_sizes;
2091 auto_vec<tree, 1> vect_masks;
2093 for (i = 1; i < orig_loop_num_nodes; i++)
2095 gimple_stmt_iterator gsi;
2096 basic_block bb = ifc_bbs[i];
2097 tree cond = bb_predicate (bb);
2102 if (is_true_predicate (cond))
2106 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2109 cond = TREE_OPERAND (cond, 0);
2112 vect_sizes.truncate (0);
2113 vect_masks.truncate (0);
2115 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2116 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
2118 else if (gimple_plf (stmt, GF_PLF_2))
2120 tree lhs = gimple_assign_lhs (stmt);
2121 tree rhs = gimple_assign_rhs1 (stmt);
2122 tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask;
2124 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
2125 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2126 mark_addressable (ref);
2127 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
2128 true, NULL_TREE, true,
2130 if (!vect_sizes.is_empty ()
2131 && (index = mask_exists (bitsize, vect_sizes)) != -1)
2132 /* Use created mask. */
2133 mask = vect_masks[index];
2136 masktype = build_nonstandard_integer_type (bitsize, 1);
2137 mask_op0 = build_int_cst (masktype, swap ? 0 : -1);
2138 mask_op1 = build_int_cst (masktype, swap ? -1 : 0);
2139 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2142 true, GSI_SAME_STMT);
2143 mask = fold_build_cond_expr (masktype, unshare_expr (cond),
2144 mask_op0, mask_op1);
2145 mask = ifc_temp_var (masktype, mask, &gsi);
2146 /* Save mask and its size for further use. */
2147 vect_sizes.safe_push (bitsize);
2148 vect_masks.safe_push (mask);
2150 ptr = build_int_cst (reference_alias_ptr_type (ref), 0);
2151 /* Copy points-to info if possible. */
2152 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2153 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2155 if (TREE_CODE (lhs) == SSA_NAME)
2158 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2160 gimple_call_set_lhs (new_stmt, lhs);
2164 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2166 gsi_replace (&gsi, new_stmt, true);
2168 else if (gimple_vdef (stmt))
2170 tree lhs = gimple_assign_lhs (stmt);
2171 tree rhs = gimple_assign_rhs1 (stmt);
2172 tree type = TREE_TYPE (lhs);
2174 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2175 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2182 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2183 is_gimple_condexpr, NULL_TREE,
2184 true, GSI_SAME_STMT);
2185 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2186 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2192 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2193 other than the exit and latch of the LOOP. Also resets the
2194 GIMPLE_DEBUG information. */
2197 remove_conditions_and_labels (loop_p loop)
2199 gimple_stmt_iterator gsi;
2202 for (i = 0; i < loop->num_nodes; i++)
2204 basic_block bb = ifc_bbs[i];
2206 if (bb_with_exit_edge_p (loop, bb)
2207 || bb == loop->latch)
2210 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2211 switch (gimple_code (gsi_stmt (gsi)))
2215 gsi_remove (&gsi, true);
2219 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2220 if (gimple_debug_bind_p (gsi_stmt (gsi)))
2222 gimple_debug_bind_reset_value (gsi_stmt (gsi));
2223 update_stmt (gsi_stmt (gsi));
2234 /* Combine all the basic blocks from LOOP into one or two super basic
2235 blocks. Replace PHI nodes with conditional modify expressions. */
2238 combine_blocks (struct loop *loop, bool any_mask_load_store)
2240 basic_block bb, exit_bb, merge_target_bb;
2241 unsigned int orig_loop_num_nodes = loop->num_nodes;
2246 predicate_bbs (loop);
2247 remove_conditions_and_labels (loop);
2248 insert_gimplified_predicates (loop, any_mask_load_store);
2249 predicate_all_scalar_phis (loop);
2251 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2252 predicate_mem_writes (loop);
2254 /* Merge basic blocks: first remove all the edges in the loop,
2255 except for those from the exit block. */
2257 for (i = 0; i < orig_loop_num_nodes; i++)
2260 free_bb_predicate (bb);
2261 if (bb_with_exit_edge_p (loop, bb))
2263 gcc_assert (exit_bb == NULL);
2267 gcc_assert (exit_bb != loop->latch);
2269 for (i = 1; i < orig_loop_num_nodes; i++)
2273 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2275 if (e->src == exit_bb)
2282 if (exit_bb != NULL)
2284 if (exit_bb != loop->header)
2286 /* Connect this node to loop header. */
2287 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2288 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2291 /* Redirect non-exit edges to loop->latch. */
2292 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2294 if (!loop_exit_edge_p (loop, e))
2295 redirect_edge_and_branch (e, loop->latch);
2297 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2301 /* If the loop does not have an exit, reconnect header and latch. */
2302 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2303 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2306 merge_target_bb = loop->header;
2307 for (i = 1; i < orig_loop_num_nodes; i++)
2309 gimple_stmt_iterator gsi;
2310 gimple_stmt_iterator last;
2314 if (bb == exit_bb || bb == loop->latch)
2317 /* Make stmts member of loop->header. */
2318 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2319 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
2321 /* Update stmt list. */
2322 last = gsi_last_bb (merge_target_bb);
2323 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
2324 set_bb_seq (bb, NULL);
2326 delete_basic_block (bb);
2329 /* If possible, merge loop header to the block with the exit edge.
2330 This reduces the number of basic blocks to two, to please the
2331 vectorizer that handles only loops with two nodes. */
2333 && exit_bb != loop->header
2334 && can_merge_blocks_p (loop->header, exit_bb))
2335 merge_blocks (loop->header, exit_bb);
2341 /* Version LOOP before if-converting it, the original loop
2342 will be then if-converted, the new copy of the loop will not,
2343 and the LOOP_VECTORIZED internal call will be guarding which
2344 loop to execute. The vectorizer pass will fold this
2345 internal call into either true or false. */
2348 version_loop_for_if_conversion (struct loop *loop)
2350 basic_block cond_bb;
2351 tree cond = make_ssa_name (boolean_type_node);
2352 struct loop *new_loop;
2354 gimple_stmt_iterator gsi;
2356 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2357 build_int_cst (integer_type_node, loop->num),
2359 gimple_call_set_lhs (g, cond);
2361 initialize_original_copy_tables ();
2362 new_loop = loop_version (loop, cond, &cond_bb,
2363 REG_BR_PROB_BASE, REG_BR_PROB_BASE,
2364 REG_BR_PROB_BASE, true);
2365 free_original_copy_tables ();
2366 if (new_loop == NULL)
2368 new_loop->dont_vectorize = true;
2369 new_loop->force_vectorize = false;
2370 gsi = gsi_last_bb (cond_bb);
2371 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2372 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2373 update_ssa (TODO_update_ssa);
2377 /* Performs splitting of critical edges if aggressive_if_conv is true.
2378 Returns false if loop won't be if converted and true otherwise. */
2381 ifcvt_split_critical_edges (struct loop *loop)
2385 unsigned int num = loop->num_nodes;
2395 if (!single_exit (loop))
2398 body = get_loop_body (loop);
2399 for (i = 0; i < num; i++)
2402 if (bb == loop->latch
2403 || bb_with_exit_edge_p (loop, bb))
2405 stmt = last_stmt (bb);
2406 /* Skip basic blocks not ending with conditional branch. */
2407 if (!(stmt && gimple_code (stmt) == GIMPLE_COND))
2409 FOR_EACH_EDGE (e, ei, bb->succs)
2410 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
2417 /* Assumes that lhs of DEF_STMT have multiple uses.
2418 Delete one use by (1) creation of copy DEF_STMT with
2419 unique lhs; (2) change original use of lhs in one
2420 use statement with newly created lhs. */
2423 ifcvt_split_def_stmt (gimple def_stmt, gimple use_stmt)
2428 gimple_stmt_iterator gsi;
2429 use_operand_p use_p;
2430 imm_use_iterator imm_iter;
2432 var = gimple_assign_lhs (def_stmt);
2433 copy_stmt = gimple_copy (def_stmt);
2434 lhs = make_temp_ssa_name (TREE_TYPE (var), NULL, "_ifc_");
2435 gimple_assign_set_lhs (copy_stmt, lhs);
2436 SSA_NAME_DEF_STMT (lhs) = copy_stmt;
2437 /* Insert copy of DEF_STMT. */
2438 gsi = gsi_for_stmt (def_stmt);
2439 gsi_insert_after (&gsi, copy_stmt, GSI_SAME_STMT);
2440 /* Change use of var to lhs in use_stmt. */
2441 if (dump_file && (dump_flags & TDF_DETAILS))
2443 fprintf (dump_file, "Change use of var ");
2444 print_generic_expr (dump_file, var, TDF_SLIM);
2445 fprintf (dump_file, " to ");
2446 print_generic_expr (dump_file, lhs, TDF_SLIM);
2447 fprintf (dump_file, "\n");
2449 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
2451 if (USE_STMT (use_p) != use_stmt)
2453 SET_USE (use_p, lhs);
2458 /* Traverse bool pattern recursively starting from VAR.
2459 Save its def and use statements to defuse_list if VAR does
2460 not have single use. */
2463 ifcvt_walk_pattern_tree (tree var, vec<gimple> *defuse_list,
2467 enum tree_code code;
2470 def_stmt = SSA_NAME_DEF_STMT (var);
2471 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2473 if (!has_single_use (var))
2475 /* Put def and use stmts into defuse_list. */
2476 defuse_list->safe_push (def_stmt);
2477 defuse_list->safe_push (use_stmt);
2478 if (dump_file && (dump_flags & TDF_DETAILS))
2480 fprintf (dump_file, "Multiple lhs uses in stmt\n");
2481 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
2484 rhs1 = gimple_assign_rhs1 (def_stmt);
2485 code = gimple_assign_rhs_code (def_stmt);
2489 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2492 if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2493 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2494 && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
2496 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2499 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2504 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2505 rhs2 = gimple_assign_rhs2 (def_stmt);
2506 ifcvt_walk_pattern_tree (rhs2, defuse_list, def_stmt);
2514 /* Returns true if STMT can be a root of bool pattern apllied
2518 stmt_is_root_of_bool_pattern (gimple stmt)
2520 enum tree_code code;
2523 code = gimple_assign_rhs_code (stmt);
2524 if (CONVERT_EXPR_CODE_P (code))
2526 lhs = gimple_assign_lhs (stmt);
2527 rhs = gimple_assign_rhs1 (stmt);
2528 if (TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
2530 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
2534 else if (code == COND_EXPR)
2536 rhs = gimple_assign_rhs1 (stmt);
2537 if (TREE_CODE (rhs) != SSA_NAME)
2544 /* Traverse all statements in BB which correspondent to loop header to
2545 find out all statements which can start bool pattern applied by
2546 vectorizer and convert multiple uses in it to conform pattern
2547 restrictions. Such case can occur if the same predicate is used both
2548 for phi node conversion and load/store mask. */
2551 ifcvt_repair_bool_pattern (basic_block bb)
2555 gimple_stmt_iterator gsi;
2556 vec<gimple> defuse_list = vNULL;
2557 vec<gimple> pattern_roots = vNULL;
2562 /* Collect all root pattern statements. */
2563 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2565 stmt = gsi_stmt (gsi);
2566 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2568 if (!stmt_is_root_of_bool_pattern (stmt))
2570 pattern_roots.safe_push (stmt);
2573 if (pattern_roots.is_empty ())
2576 /* Split all statements with multiple uses iteratively since splitting
2577 may create new multiple uses. */
2582 FOR_EACH_VEC_ELT (pattern_roots, ix, stmt)
2584 rhs = gimple_assign_rhs1 (stmt);
2585 ifcvt_walk_pattern_tree (rhs, &defuse_list, stmt);
2586 while (defuse_list.length () > 0)
2589 gimple def_stmt, use_stmt;
2590 use_stmt = defuse_list.pop ();
2591 def_stmt = defuse_list.pop ();
2592 ifcvt_split_def_stmt (def_stmt, use_stmt);
2597 if (dump_file && (dump_flags & TDF_DETAILS))
2598 fprintf (dump_file, "Repair bool pattern takes %d iterations. \n",
2602 /* Delete redundant statements produced by predication which prevents
2603 loop vectorization. */
2606 ifcvt_local_dce (basic_block bb)
2611 gimple_stmt_iterator gsi;
2612 vec<gimple> worklist;
2613 enum gimple_code code;
2614 use_operand_p use_p;
2615 imm_use_iterator imm_iter;
2617 worklist.create (64);
2618 /* Consider all phi as live statements. */
2619 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2621 phi = gsi_stmt (gsi);
2622 gimple_set_plf (phi, GF_PLF_2, true);
2623 worklist.safe_push (phi);
2625 /* Consider load/store statemnts, CALL and COND as live. */
2626 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2628 stmt = gsi_stmt (gsi);
2629 if (gimple_store_p (stmt)
2630 || gimple_assign_load_p (stmt)
2631 || is_gimple_debug (stmt))
2633 gimple_set_plf (stmt, GF_PLF_2, true);
2634 worklist.safe_push (stmt);
2637 code = gimple_code (stmt);
2638 if (code == GIMPLE_COND || code == GIMPLE_CALL)
2640 gimple_set_plf (stmt, GF_PLF_2, true);
2641 worklist.safe_push (stmt);
2644 gimple_set_plf (stmt, GF_PLF_2, false);
2646 if (code == GIMPLE_ASSIGN)
2648 tree lhs = gimple_assign_lhs (stmt);
2649 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2651 stmt1 = USE_STMT (use_p);
2652 if (gimple_bb (stmt1) != bb)
2654 gimple_set_plf (stmt, GF_PLF_2, true);
2655 worklist.safe_push (stmt);
2661 /* Propagate liveness through arguments of live stmt. */
2662 while (worklist.length () > 0)
2665 use_operand_p use_p;
2668 stmt = worklist.pop ();
2669 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2671 use = USE_FROM_PTR (use_p);
2672 if (TREE_CODE (use) != SSA_NAME)
2674 stmt1 = SSA_NAME_DEF_STMT (use);
2675 if (gimple_bb (stmt1) != bb
2676 || gimple_plf (stmt1, GF_PLF_2))
2678 gimple_set_plf (stmt1, GF_PLF_2, true);
2679 worklist.safe_push (stmt1);
2682 /* Delete dead statements. */
2683 gsi = gsi_start_bb (bb);
2684 while (!gsi_end_p (gsi))
2686 stmt = gsi_stmt (gsi);
2687 if (gimple_plf (stmt, GF_PLF_2))
2692 if (dump_file && (dump_flags & TDF_DETAILS))
2694 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
2695 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2697 gsi_remove (&gsi, true);
2698 release_defs (stmt);
2702 /* If-convert LOOP when it is legal. For the moment this pass has no
2703 profitability analysis. Returns non-zero todo flags when something
2707 tree_if_conversion (struct loop *loop)
2709 unsigned int todo = 0;
2711 bool any_mask_load_store = false;
2713 /* Set-up aggressive if-conversion for loops marked with simd pragma. */
2714 aggressive_if_conv = loop->force_vectorize;
2715 /* Check either outer loop was marked with simd pragma. */
2716 if (!aggressive_if_conv)
2718 struct loop *outer_loop = loop_outer (loop);
2719 if (outer_loop && outer_loop->force_vectorize)
2720 aggressive_if_conv = true;
2723 if (aggressive_if_conv)
2724 if (!ifcvt_split_critical_edges (loop))
2727 if (!if_convertible_loop_p (loop, &any_mask_load_store)
2728 || !dbg_cnt (if_conversion_tree))
2731 if (any_mask_load_store
2732 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
2733 || loop->dont_vectorize))
2736 if (any_mask_load_store && !version_loop_for_if_conversion (loop))
2739 /* Now all statements are if-convertible. Combine all the basic
2740 blocks into one huge basic block doing the if-conversion
2742 combine_blocks (loop, any_mask_load_store);
2744 /* Delete dead predicate computations and repair tree correspondent
2745 to bool pattern to delete multiple uses of preidcates. */
2746 if (aggressive_if_conv)
2748 ifcvt_local_dce (loop->header);
2749 ifcvt_repair_bool_pattern (loop->header);
2752 todo |= TODO_cleanup_cfg;
2753 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2755 mark_virtual_operands_for_renaming (cfun);
2756 todo |= TODO_update_ssa_only_virtuals;
2764 for (i = 0; i < loop->num_nodes; i++)
2765 free_bb_predicate (ifc_bbs[i]);
2770 free_dominance_info (CDI_POST_DOMINATORS);
2775 /* Tree if-conversion pass management. */
2779 const pass_data pass_data_if_conversion =
2781 GIMPLE_PASS, /* type */
2783 OPTGROUP_NONE, /* optinfo_flags */
2784 TV_NONE, /* tv_id */
2785 ( PROP_cfg | PROP_ssa ), /* properties_required */
2786 0, /* properties_provided */
2787 0, /* properties_destroyed */
2788 0, /* todo_flags_start */
2789 0, /* todo_flags_finish */
2792 class pass_if_conversion : public gimple_opt_pass
2795 pass_if_conversion (gcc::context *ctxt)
2796 : gimple_opt_pass (pass_data_if_conversion, ctxt)
2799 /* opt_pass methods: */
2800 virtual bool gate (function *);
2801 virtual unsigned int execute (function *);
2803 }; // class pass_if_conversion
2806 pass_if_conversion::gate (function *fun)
2808 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
2809 && flag_tree_loop_if_convert != 0)
2810 || flag_tree_loop_if_convert == 1
2811 || flag_tree_loop_if_convert_stores == 1);
2815 pass_if_conversion::execute (function *fun)
2820 if (number_of_loops (fun) <= 1)
2823 FOR_EACH_LOOP (loop, 0)
2824 if (flag_tree_loop_if_convert == 1
2825 || flag_tree_loop_if_convert_stores == 1
2826 || ((flag_tree_loop_vectorize || loop->force_vectorize)
2827 && !loop->dont_vectorize))
2828 todo |= tree_if_conversion (loop);
2830 #ifdef ENABLE_CHECKING
2833 FOR_EACH_BB_FN (bb, fun)
2834 gcc_assert (!bb->aux);
2844 make_pass_if_conversion (gcc::context *ctxt)
2846 return new pass_if_conversion (ctxt);