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"
94 #include "fold-const.h"
95 #include "stor-layout.h"
98 #include "hard-reg-set.h"
100 #include "dominance.h"
102 #include "basic-block.h"
103 #include "gimple-pretty-print.h"
104 #include "tree-ssa-alias.h"
105 #include "internal-fn.h"
106 #include "gimple-fold.h"
107 #include "gimple-expr.h"
110 #include "gimplify.h"
111 #include "gimple-iterator.h"
112 #include "gimplify-me.h"
113 #include "gimple-ssa.h"
114 #include "tree-cfg.h"
115 #include "tree-phinodes.h"
116 #include "ssa-iterators.h"
117 #include "stringpool.h"
118 #include "tree-ssanames.h"
119 #include "tree-into-ssa.h"
120 #include "tree-ssa.h"
122 #include "tree-chrec.h"
123 #include "tree-data-ref.h"
124 #include "tree-scalar-evolution.h"
125 #include "tree-ssa-loop-ivopts.h"
126 #include "tree-ssa-address.h"
127 #include "tree-pass.h"
131 #include "statistics.h"
132 #include "insn-config.h"
137 #include "emit-rtl.h"
141 #include "insn-codes.h"
143 #include "hash-map.h"
145 /* List of basic blocks in if-conversion-suitable order. */
146 static basic_block *ifc_bbs;
148 /* Apply more aggressive (extended) if-conversion if true. */
149 static bool aggressive_if_conv;
151 /* Structure used to predicate basic blocks. This is attached to the
152 ->aux field of the BBs in the loop to be if-converted. */
153 typedef struct bb_predicate_s {
155 /* The condition under which this basic block is executed. */
158 /* PREDICATE is gimplified, and the sequence of statements is
159 recorded here, in order to avoid the duplication of computations
160 that occur in previous conditions. See PR44483. */
161 gimple_seq predicate_gimplified_stmts;
164 /* Returns true when the basic block BB has a predicate. */
167 bb_has_predicate (basic_block bb)
169 return bb->aux != NULL;
172 /* Returns the gimplified predicate for basic block BB. */
175 bb_predicate (basic_block bb)
177 return ((bb_predicate_p) bb->aux)->predicate;
180 /* Sets the gimplified predicate COND for basic block BB. */
183 set_bb_predicate (basic_block bb, tree cond)
185 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
186 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
187 || is_gimple_condexpr (cond));
188 ((bb_predicate_p) bb->aux)->predicate = cond;
191 /* Returns the sequence of statements of the gimplification of the
192 predicate for basic block BB. */
194 static inline gimple_seq
195 bb_predicate_gimplified_stmts (basic_block bb)
197 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts;
200 /* Sets the sequence of statements STMTS of the gimplification of the
201 predicate for basic block BB. */
204 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
206 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts;
209 /* Adds the sequence of statements STMTS to the sequence of statements
210 of the predicate for basic block BB. */
213 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
216 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts);
219 /* Initializes to TRUE the predicate of basic block BB. */
222 init_bb_predicate (basic_block bb)
224 bb->aux = XNEW (struct bb_predicate_s);
225 set_bb_predicate_gimplified_stmts (bb, NULL);
226 set_bb_predicate (bb, boolean_true_node);
229 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
230 but don't actually free it. */
233 release_bb_predicate (basic_block bb)
235 gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
238 gimple_stmt_iterator i;
240 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
241 free_stmt_operands (cfun, gsi_stmt (i));
242 set_bb_predicate_gimplified_stmts (bb, NULL);
246 /* Free the predicate of basic block BB. */
249 free_bb_predicate (basic_block bb)
251 if (!bb_has_predicate (bb))
254 release_bb_predicate (bb);
259 /* Reinitialize predicate of BB with the true predicate. */
262 reset_bb_predicate (basic_block bb)
264 if (!bb_has_predicate (bb))
265 init_bb_predicate (bb);
268 release_bb_predicate (bb);
269 set_bb_predicate (bb, boolean_true_node);
273 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
274 the expression EXPR. Inserts the statement created for this
275 computation before GSI and leaves the iterator GSI at the same
279 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
281 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
282 gimple stmt = gimple_build_assign (new_name, expr);
283 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
287 /* Return true when COND is a true predicate. */
290 is_true_predicate (tree cond)
292 return (cond == NULL_TREE
293 || cond == boolean_true_node
294 || integer_onep (cond));
297 /* Returns true when BB has a predicate that is not trivial: true or
301 is_predicated (basic_block bb)
303 return !is_true_predicate (bb_predicate (bb));
306 /* Parses the predicate COND and returns its comparison code and
307 operands OP0 and OP1. */
309 static enum tree_code
310 parse_predicate (tree cond, tree *op0, tree *op1)
314 if (TREE_CODE (cond) == SSA_NAME
315 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
317 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
319 *op0 = gimple_assign_rhs1 (s);
320 *op1 = gimple_assign_rhs2 (s);
321 return gimple_assign_rhs_code (s);
324 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
326 tree op = gimple_assign_rhs1 (s);
327 tree type = TREE_TYPE (op);
328 enum tree_code code = parse_predicate (op, op0, op1);
330 return code == ERROR_MARK ? ERROR_MARK
331 : invert_tree_comparison (code, HONOR_NANS (type));
337 if (COMPARISON_CLASS_P (cond))
339 *op0 = TREE_OPERAND (cond, 0);
340 *op1 = TREE_OPERAND (cond, 1);
341 return TREE_CODE (cond);
347 /* Returns the fold of predicate C1 OR C2 at location LOC. */
350 fold_or_predicates (location_t loc, tree c1, tree c2)
352 tree op1a, op1b, op2a, op2b;
353 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
354 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
356 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
358 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
364 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
367 /* Returns true if N is either a constant or a SSA_NAME. */
370 constant_or_ssa_name (tree n)
372 switch (TREE_CODE (n))
385 /* Returns either a COND_EXPR or the folded expression if the folded
386 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
387 a constant or a SSA_NAME. */
390 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
392 tree rhs1, lhs1, cond_expr;
394 /* If COND is comparison r != 0 and r has boolean type, convert COND
395 to SSA_NAME to accept by vect bool pattern. */
396 if (TREE_CODE (cond) == NE_EXPR)
398 tree op0 = TREE_OPERAND (cond, 0);
399 tree op1 = TREE_OPERAND (cond, 1);
400 if (TREE_CODE (op0) == SSA_NAME
401 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
402 && (integer_zerop (op1)))
405 cond_expr = fold_ternary (COND_EXPR, type, cond,
408 if (cond_expr == NULL_TREE)
409 return build3 (COND_EXPR, type, cond, rhs, lhs);
411 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
413 if (constant_or_ssa_name (cond_expr))
416 if (TREE_CODE (cond_expr) == ABS_EXPR)
418 rhs1 = TREE_OPERAND (cond_expr, 1);
419 STRIP_USELESS_TYPE_CONVERSION (rhs1);
420 if (constant_or_ssa_name (rhs1))
421 return build1 (ABS_EXPR, type, rhs1);
424 if (TREE_CODE (cond_expr) == MIN_EXPR
425 || TREE_CODE (cond_expr) == MAX_EXPR)
427 lhs1 = TREE_OPERAND (cond_expr, 0);
428 STRIP_USELESS_TYPE_CONVERSION (lhs1);
429 rhs1 = TREE_OPERAND (cond_expr, 1);
430 STRIP_USELESS_TYPE_CONVERSION (rhs1);
431 if (constant_or_ssa_name (rhs1)
432 && constant_or_ssa_name (lhs1))
433 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
435 return build3 (COND_EXPR, type, cond, rhs, lhs);
438 /* Add condition NC to the predicate list of basic block BB. LOOP is
439 the loop to be if-converted. Use predicate of cd-equivalent block
440 for join bb if it exists: we call basic blocks bb1 and bb2
441 cd-equivalent if they are executed under the same condition. */
444 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
449 if (is_true_predicate (nc))
452 /* If dominance tells us this basic block is always executed,
453 don't record any predicates for it. */
454 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
457 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
458 /* We use notion of cd equivalence to get simpler predicate for
459 join block, e.g. if join block has 2 predecessors with predicates
460 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
461 p1 & p2 | p1 & !p2. */
462 if (dom_bb != loop->header
463 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
465 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
466 bc = bb_predicate (dom_bb);
467 if (!is_true_predicate (bc))
468 set_bb_predicate (bb, bc);
470 gcc_assert (is_true_predicate (bb_predicate (bb)));
471 if (dump_file && (dump_flags & TDF_DETAILS))
472 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
473 dom_bb->index, bb->index);
477 if (!is_predicated (bb))
481 bc = bb_predicate (bb);
482 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
483 if (is_true_predicate (bc))
485 reset_bb_predicate (bb);
490 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
491 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
492 tp = &TREE_OPERAND (bc, 0);
495 if (!is_gimple_condexpr (*tp))
498 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
499 add_bb_predicate_gimplified_stmts (bb, stmts);
501 set_bb_predicate (bb, bc);
504 /* Add the condition COND to the previous condition PREV_COND, and add
505 this to the predicate list of the destination of edge E. LOOP is
506 the loop to be if-converted. */
509 add_to_dst_predicate_list (struct loop *loop, edge e,
510 tree prev_cond, tree cond)
512 if (!flow_bb_inside_loop_p (loop, e->dest))
515 if (!is_true_predicate (prev_cond))
516 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
519 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
520 add_to_predicate_list (loop, e->dest, cond);
523 /* Return true if one of the successor edges of BB exits LOOP. */
526 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
531 FOR_EACH_EDGE (e, ei, bb->succs)
532 if (loop_exit_edge_p (loop, e))
538 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
539 and it belongs to basic block BB.
541 PHI is not if-convertible if:
542 - it has more than 2 arguments.
544 When the flag_tree_loop_if_convert_stores is not set, PHI is not
546 - a virtual PHI is immediately used in another PHI node,
547 - there is a virtual PHI in a BB other than the loop->header.
548 When the aggressive_if_conv is set, PHI can have more than
552 if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi,
553 bool any_mask_load_store)
555 if (dump_file && (dump_flags & TDF_DETAILS))
557 fprintf (dump_file, "-------------------------\n");
558 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
561 if (bb != loop->header)
563 if (gimple_phi_num_args (phi) != 2
564 && !aggressive_if_conv)
566 if (dump_file && (dump_flags & TDF_DETAILS))
567 fprintf (dump_file, "More than two phi node args.\n");
572 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
575 /* When the flag_tree_loop_if_convert_stores is not set, check
576 that there are no memory writes in the branches of the loop to be
578 if (virtual_operand_p (gimple_phi_result (phi)))
580 imm_use_iterator imm_iter;
583 if (bb != loop->header)
585 if (dump_file && (dump_flags & TDF_DETAILS))
586 fprintf (dump_file, "Virtual phi not on loop->header.\n");
590 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
592 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
593 && USE_STMT (use_p) != (gimple) phi)
595 if (dump_file && (dump_flags & TDF_DETAILS))
596 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
605 /* Records the status of a data reference. This struct is attached to
606 each DR->aux field. */
609 /* -1 when not initialized, 0 when false, 1 when true. */
610 int written_at_least_once;
612 /* -1 when not initialized, 0 when false, 1 when true. */
613 int rw_unconditionally;
616 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
617 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
618 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
620 /* Returns true when the memory references of STMT are read or written
621 unconditionally. In other words, this function returns true when
622 for every data reference A in STMT there exist other accesses to
623 a data reference with the same base with predicates that add up (OR-up) to
624 the true predicate: this ensures that the data reference A is touched
625 (read or written) on every iteration of the if-converted loop. */
628 memrefs_read_or_written_unconditionally (gimple stmt,
629 vec<data_reference_p> drs)
632 data_reference_p a, b;
633 tree ca = bb_predicate (gimple_bb (stmt));
635 for (i = 0; drs.iterate (i, &a); i++)
636 if (DR_STMT (a) == stmt)
639 int x = DR_RW_UNCONDITIONALLY (a);
647 for (j = 0; drs.iterate (j, &b); j++)
649 tree ref_base_a = DR_REF (a);
650 tree ref_base_b = DR_REF (b);
652 if (DR_STMT (b) == stmt)
655 while (TREE_CODE (ref_base_a) == COMPONENT_REF
656 || TREE_CODE (ref_base_a) == IMAGPART_EXPR
657 || TREE_CODE (ref_base_a) == REALPART_EXPR)
658 ref_base_a = TREE_OPERAND (ref_base_a, 0);
660 while (TREE_CODE (ref_base_b) == COMPONENT_REF
661 || TREE_CODE (ref_base_b) == IMAGPART_EXPR
662 || TREE_CODE (ref_base_b) == REALPART_EXPR)
663 ref_base_b = TREE_OPERAND (ref_base_b, 0);
665 if (!operand_equal_p (ref_base_a, ref_base_b, 0))
667 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
669 if (DR_RW_UNCONDITIONALLY (b) == 1
670 || is_true_predicate (cb)
671 || is_true_predicate (ca
672 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
674 DR_RW_UNCONDITIONALLY (a) = 1;
675 DR_RW_UNCONDITIONALLY (b) = 1;
684 DR_RW_UNCONDITIONALLY (a) = 0;
692 /* Returns true when the memory references of STMT are unconditionally
693 written. In other words, this function returns true when for every
694 data reference A written in STMT, there exist other writes to the
695 same data reference with predicates that add up (OR-up) to the true
696 predicate: this ensures that the data reference A is written on
697 every iteration of the if-converted loop. */
700 write_memrefs_written_at_least_once (gimple stmt,
701 vec<data_reference_p> drs)
704 data_reference_p a, b;
705 tree ca = bb_predicate (gimple_bb (stmt));
707 for (i = 0; drs.iterate (i, &a); i++)
708 if (DR_STMT (a) == stmt
712 int x = DR_WRITTEN_AT_LEAST_ONCE (a);
720 for (j = 0; drs.iterate (j, &b); j++)
721 if (DR_STMT (b) != stmt
723 && same_data_refs_base_objects (a, b))
725 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
727 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
728 || is_true_predicate (cb)
729 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
732 DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
733 DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
741 DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
749 /* Return true when the memory references of STMT won't trap in the
750 if-converted code. There are two things that we have to check for:
752 - writes to memory occur to writable memory: if-conversion of
753 memory writes transforms the conditional memory writes into
754 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
755 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
756 be executed at all in the original code, it may be a readonly
757 memory. To check that A is not const-qualified, we check that
758 there exists at least an unconditional write to A in the current
761 - reads or writes to memory are valid memory accesses for every
762 iteration. To check that the memory accesses are correctly formed
763 and that we are allowed to read and write in these locations, we
764 check that the memory accesses to be if-converted occur at every
765 iteration unconditionally. */
768 ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs)
770 return write_memrefs_written_at_least_once (stmt, refs)
771 && memrefs_read_or_written_unconditionally (stmt, refs);
774 /* Wrapper around gimple_could_trap_p refined for the needs of the
775 if-conversion. Try to prove that the memory accesses of STMT could
776 not trap in the innermost loop containing STMT. */
779 ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs)
781 if (gimple_vuse (stmt)
782 && !gimple_could_trap_p_1 (stmt, false, false)
783 && ifcvt_memrefs_wont_trap (stmt, refs))
786 return gimple_could_trap_p (stmt);
789 /* Return true if STMT could be converted into a masked load or store
790 (conditional load or store based on a mask computed from bb predicate). */
793 ifcvt_can_use_mask_load_store (gimple stmt)
797 basic_block bb = gimple_bb (stmt);
800 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
801 || bb->loop_father->dont_vectorize
802 || !gimple_assign_single_p (stmt)
803 || gimple_has_volatile_ops (stmt))
806 /* Check whether this is a load or store. */
807 lhs = gimple_assign_lhs (stmt);
808 if (gimple_store_p (stmt))
810 if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
815 else if (gimple_assign_load_p (stmt))
818 ref = gimple_assign_rhs1 (stmt);
823 if (may_be_nonaddressable_p (ref))
826 /* Mask should be integer mode of the same size as the load/store
828 mode = TYPE_MODE (TREE_TYPE (lhs));
829 if (int_mode_for_mode (mode) == BLKmode
830 || VECTOR_MODE_P (mode))
833 if (can_vec_mask_load_store_p (mode, is_load))
839 /* Return true when STMT is if-convertible.
841 GIMPLE_ASSIGN statement is not if-convertible if,
844 - LHS is not var decl. */
847 if_convertible_gimple_assign_stmt_p (gimple stmt,
848 vec<data_reference_p> refs,
849 bool *any_mask_load_store)
851 tree lhs = gimple_assign_lhs (stmt);
854 if (dump_file && (dump_flags & TDF_DETAILS))
856 fprintf (dump_file, "-------------------------\n");
857 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
860 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
863 /* Some of these constrains might be too conservative. */
864 if (stmt_ends_bb_p (stmt)
865 || gimple_has_volatile_ops (stmt)
866 || (TREE_CODE (lhs) == SSA_NAME
867 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
868 || gimple_has_side_effects (stmt))
870 if (dump_file && (dump_flags & TDF_DETAILS))
871 fprintf (dump_file, "stmt not suitable for ifcvt\n");
875 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
876 in between if_convertible_loop_p and combine_blocks
877 we can perform loop versioning. */
878 gimple_set_plf (stmt, GF_PLF_2, false);
880 if (flag_tree_loop_if_convert_stores)
882 if (ifcvt_could_trap_p (stmt, refs))
884 if (ifcvt_can_use_mask_load_store (stmt))
886 gimple_set_plf (stmt, GF_PLF_2, true);
887 *any_mask_load_store = true;
890 if (dump_file && (dump_flags & TDF_DETAILS))
891 fprintf (dump_file, "tree could trap...\n");
897 if (gimple_assign_rhs_could_trap_p (stmt))
899 if (ifcvt_can_use_mask_load_store (stmt))
901 gimple_set_plf (stmt, GF_PLF_2, true);
902 *any_mask_load_store = true;
905 if (dump_file && (dump_flags & TDF_DETAILS))
906 fprintf (dump_file, "tree could trap...\n");
910 bb = gimple_bb (stmt);
912 if (TREE_CODE (lhs) != SSA_NAME
913 && bb != bb->loop_father->header
914 && !bb_with_exit_edge_p (bb->loop_father, bb))
916 if (ifcvt_can_use_mask_load_store (stmt))
918 gimple_set_plf (stmt, GF_PLF_2, true);
919 *any_mask_load_store = true;
922 if (dump_file && (dump_flags & TDF_DETAILS))
924 fprintf (dump_file, "LHS is not var\n");
925 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
933 /* Return true when STMT is if-convertible.
935 A statement is if-convertible if:
936 - it is an if-convertible GIMPLE_ASSIGN,
937 - it is a GIMPLE_LABEL or a GIMPLE_COND,
938 - it is builtins call. */
941 if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs,
942 bool *any_mask_load_store)
944 switch (gimple_code (stmt))
952 return if_convertible_gimple_assign_stmt_p (stmt, refs,
953 any_mask_load_store);
957 tree fndecl = gimple_call_fndecl (stmt);
960 int flags = gimple_call_flags (stmt);
961 if ((flags & ECF_CONST)
962 && !(flags & ECF_LOOPING_CONST_OR_PURE)
963 /* We can only vectorize some builtins at the moment,
964 so restrict if-conversion to those. */
965 && DECL_BUILT_IN (fndecl))
972 /* Don't know what to do with 'em so don't do anything. */
973 if (dump_file && (dump_flags & TDF_DETAILS))
975 fprintf (dump_file, "don't know what to do\n");
976 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
985 /* Assumes that BB has more than 1 predecessors.
986 Returns false if at least one successor is not on critical edge
987 and true otherwise. */
990 all_preds_critical_p (basic_block bb)
995 FOR_EACH_EDGE (e, ei, bb->preds)
996 if (EDGE_COUNT (e->src->succs) == 1)
1001 /* Returns true if at least one successor in on critical edge. */
1003 has_pred_critical_p (basic_block bb)
1008 FOR_EACH_EDGE (e, ei, bb->preds)
1009 if (EDGE_COUNT (e->src->succs) > 1)
1014 /* Return true when BB is if-convertible. This routine does not check
1015 basic block's statements and phis.
1017 A basic block is not if-convertible if:
1018 - it is non-empty and it is after the exit block (in BFS order),
1019 - it is after the exit block but before the latch,
1020 - its edges are not normal.
1022 Last restriction is valid if aggressive_if_conv is false.
1024 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1028 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
1033 if (dump_file && (dump_flags & TDF_DETAILS))
1034 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1036 if (EDGE_COUNT (bb->succs) > 2)
1039 if (EDGE_COUNT (bb->preds) > 2
1040 && !aggressive_if_conv)
1045 if (bb != loop->latch)
1047 if (dump_file && (dump_flags & TDF_DETAILS))
1048 fprintf (dump_file, "basic block after exit bb but before latch\n");
1051 else if (!empty_block_p (bb))
1053 if (dump_file && (dump_flags & TDF_DETAILS))
1054 fprintf (dump_file, "non empty basic block after exit bb\n");
1057 else if (bb == loop->latch
1059 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1061 if (dump_file && (dump_flags & TDF_DETAILS))
1062 fprintf (dump_file, "latch is not dominated by exit_block\n");
1067 /* Be less adventurous and handle only normal edges. */
1068 FOR_EACH_EDGE (e, ei, bb->succs)
1069 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1071 if (dump_file && (dump_flags & TDF_DETAILS))
1072 fprintf (dump_file, "Difficult to handle edges\n");
1076 /* At least one incoming edge has to be non-critical as otherwise edge
1077 predicates are not equal to basic-block predicates of the edge
1078 source. This check is skipped if aggressive_if_conv is true. */
1079 if (!aggressive_if_conv
1080 && EDGE_COUNT (bb->preds) > 1
1081 && bb != loop->header
1082 && all_preds_critical_p (bb))
1084 if (dump_file && (dump_flags & TDF_DETAILS))
1085 fprintf (dump_file, "only critical predecessors\n");
1092 /* Return true when all predecessor blocks of BB are visited. The
1093 VISITED bitmap keeps track of the visited blocks. */
1096 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1100 FOR_EACH_EDGE (e, ei, bb->preds)
1101 if (!bitmap_bit_p (*visited, e->src->index))
1107 /* Get body of a LOOP in suitable order for if-conversion. It is
1108 caller's responsibility to deallocate basic block list.
1109 If-conversion suitable order is, breadth first sort (BFS) order
1110 with an additional constraint: select a block only if all its
1111 predecessors are already selected. */
1113 static basic_block *
1114 get_loop_body_in_if_conv_order (const struct loop *loop)
1116 basic_block *blocks, *blocks_in_bfs_order;
1119 unsigned int index = 0;
1120 unsigned int visited_count = 0;
1122 gcc_assert (loop->num_nodes);
1123 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1125 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1126 visited = BITMAP_ALLOC (NULL);
1128 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1131 while (index < loop->num_nodes)
1133 bb = blocks_in_bfs_order [index];
1135 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1137 free (blocks_in_bfs_order);
1138 BITMAP_FREE (visited);
1143 if (!bitmap_bit_p (visited, bb->index))
1145 if (pred_blocks_visited_p (bb, &visited)
1146 || bb == loop->header)
1148 /* This block is now visited. */
1149 bitmap_set_bit (visited, bb->index);
1150 blocks[visited_count++] = bb;
1156 if (index == loop->num_nodes
1157 && visited_count != loop->num_nodes)
1161 free (blocks_in_bfs_order);
1162 BITMAP_FREE (visited);
1166 /* Returns true when the analysis of the predicates for all the basic
1167 blocks in LOOP succeeded.
1169 predicate_bbs first allocates the predicates of the basic blocks.
1170 These fields are then initialized with the tree expressions
1171 representing the predicates under which a basic block is executed
1172 in the LOOP. As the loop->header is executed at each iteration, it
1173 has the "true" predicate. Other statements executed under a
1174 condition are predicated with that condition, for example
1181 S1 will be predicated with "x", and
1182 S2 will be predicated with "!x". */
1185 predicate_bbs (loop_p loop)
1189 for (i = 0; i < loop->num_nodes; i++)
1190 init_bb_predicate (ifc_bbs[i]);
1192 for (i = 0; i < loop->num_nodes; i++)
1194 basic_block bb = ifc_bbs[i];
1198 /* The loop latch and loop exit block are always executed and
1199 have no extra conditions to be processed: skip them. */
1200 if (bb == loop->latch
1201 || bb_with_exit_edge_p (loop, bb))
1203 reset_bb_predicate (bb);
1207 cond = bb_predicate (bb);
1208 stmt = last_stmt (bb);
1209 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1212 edge true_edge, false_edge;
1213 location_t loc = gimple_location (stmt);
1214 tree c = build2_loc (loc, gimple_cond_code (stmt),
1216 gimple_cond_lhs (stmt),
1217 gimple_cond_rhs (stmt));
1219 /* Add new condition into destination's predicate list. */
1220 extract_true_false_edges_from_block (gimple_bb (stmt),
1221 &true_edge, &false_edge);
1223 /* If C is true, then TRUE_EDGE is taken. */
1224 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1227 /* If C is false, then FALSE_EDGE is taken. */
1228 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1230 add_to_dst_predicate_list (loop, false_edge,
1231 unshare_expr (cond), c2);
1236 /* If current bb has only one successor, then consider it as an
1237 unconditional goto. */
1238 if (single_succ_p (bb))
1240 basic_block bb_n = single_succ (bb);
1242 /* The successor bb inherits the predicate of its
1243 predecessor. If there is no predicate in the predecessor
1244 bb, then consider the successor bb as always executed. */
1245 if (cond == NULL_TREE)
1246 cond = boolean_true_node;
1248 add_to_predicate_list (loop, bb_n, cond);
1252 /* The loop header is always executed. */
1253 reset_bb_predicate (loop->header);
1254 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1255 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1258 /* Return true when LOOP is if-convertible. This is a helper function
1259 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1260 in if_convertible_loop_p. */
1263 if_convertible_loop_p_1 (struct loop *loop,
1264 vec<loop_p> *loop_nest,
1265 vec<data_reference_p> *refs,
1266 vec<ddr_p> *ddrs, bool *any_mask_load_store)
1270 basic_block exit_bb = NULL;
1272 /* Don't if-convert the loop when the data dependences cannot be
1273 computed: the loop won't be vectorized in that case. */
1274 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
1278 calculate_dominance_info (CDI_DOMINATORS);
1279 calculate_dominance_info (CDI_POST_DOMINATORS);
1281 /* Allow statements that can be handled during if-conversion. */
1282 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1285 if (dump_file && (dump_flags & TDF_DETAILS))
1286 fprintf (dump_file, "Irreducible loop\n");
1290 for (i = 0; i < loop->num_nodes; i++)
1292 basic_block bb = ifc_bbs[i];
1294 if (!if_convertible_bb_p (loop, bb, exit_bb))
1297 if (bb_with_exit_edge_p (loop, bb))
1301 for (i = 0; i < loop->num_nodes; i++)
1303 basic_block bb = ifc_bbs[i];
1304 gimple_stmt_iterator gsi;
1306 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1307 switch (gimple_code (gsi_stmt (gsi)))
1320 if (flag_tree_loop_if_convert_stores)
1322 data_reference_p dr;
1324 for (i = 0; refs->iterate (i, &dr); i++)
1326 dr->aux = XNEW (struct ifc_dr);
1327 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1328 DR_RW_UNCONDITIONALLY (dr) = -1;
1330 predicate_bbs (loop);
1333 for (i = 0; i < loop->num_nodes; i++)
1335 basic_block bb = ifc_bbs[i];
1336 gimple_stmt_iterator itr;
1338 /* Check the if-convertibility of statements in predicated BBs. */
1339 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1340 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1341 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs,
1342 any_mask_load_store))
1346 if (flag_tree_loop_if_convert_stores)
1347 for (i = 0; i < loop->num_nodes; i++)
1348 free_bb_predicate (ifc_bbs[i]);
1350 /* Checking PHIs needs to be done after stmts, as the fact whether there
1351 are any masked loads or stores affects the tests. */
1352 for (i = 0; i < loop->num_nodes; i++)
1354 basic_block bb = ifc_bbs[i];
1357 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1358 if (!if_convertible_phi_p (loop, bb, itr.phi (),
1359 *any_mask_load_store))
1364 fprintf (dump_file, "Applying if-conversion\n");
1369 /* Return true when LOOP is if-convertible.
1370 LOOP is if-convertible if:
1372 - it has two or more basic blocks,
1373 - it has only one exit,
1374 - loop header is not the exit edge,
1375 - if its basic blocks and phi nodes are if convertible. */
1378 if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store)
1383 vec<data_reference_p> refs;
1386 /* Handle only innermost loop. */
1387 if (!loop || loop->inner)
1389 if (dump_file && (dump_flags & TDF_DETAILS))
1390 fprintf (dump_file, "not innermost loop\n");
1394 /* If only one block, no need for if-conversion. */
1395 if (loop->num_nodes <= 2)
1397 if (dump_file && (dump_flags & TDF_DETAILS))
1398 fprintf (dump_file, "less than 2 basic blocks\n");
1402 /* More than one loop exit is too much to handle. */
1403 if (!single_exit (loop))
1405 if (dump_file && (dump_flags & TDF_DETAILS))
1406 fprintf (dump_file, "multiple exits\n");
1410 /* If one of the loop header's edge is an exit edge then do not
1411 apply if-conversion. */
1412 FOR_EACH_EDGE (e, ei, loop->header->succs)
1413 if (loop_exit_edge_p (loop, e))
1418 auto_vec<loop_p, 3> loop_nest;
1419 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs,
1420 any_mask_load_store);
1422 if (flag_tree_loop_if_convert_stores)
1424 data_reference_p dr;
1427 for (i = 0; refs.iterate (i, &dr); i++)
1431 free_data_refs (refs);
1432 free_dependence_relations (ddrs);
1436 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1437 which is in predicated basic block.
1438 In fact, the following PHI pattern is searching:
1440 reduc_1 = PHI <..., reduc_2>
1444 reduc_2 = PHI <reduc_1, reduc_3>
1446 ARG_0 and ARG_1 are correspondent PHI arguments.
1447 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1448 EXTENDED is true if PHI has > 2 arguments. */
1451 is_cond_scalar_reduction (gimple phi, gimple *reduc, tree arg_0, tree arg_1,
1452 tree *op0, tree *op1, bool extended)
1454 tree lhs, r_op1, r_op2;
1456 gimple header_phi = NULL;
1457 enum tree_code reduction_op;
1458 basic_block bb = gimple_bb (phi);
1459 struct loop *loop = bb->loop_father;
1460 edge latch_e = loop_latch_edge (loop);
1461 imm_use_iterator imm_iter;
1462 use_operand_p use_p;
1465 bool result = false;
1466 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1469 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1472 header_phi = SSA_NAME_DEF_STMT (arg_0);
1473 stmt = SSA_NAME_DEF_STMT (arg_1);
1475 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1478 header_phi = SSA_NAME_DEF_STMT (arg_1);
1479 stmt = SSA_NAME_DEF_STMT (arg_0);
1483 if (gimple_bb (header_phi) != loop->header)
1486 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1489 if (gimple_code (stmt) != GIMPLE_ASSIGN
1490 || gimple_has_volatile_ops (stmt))
1493 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1496 if (!is_predicated (gimple_bb (stmt)))
1499 /* Check that stmt-block is predecessor of phi-block. */
1500 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1509 if (!has_single_use (lhs))
1512 reduction_op = gimple_assign_rhs_code (stmt);
1513 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1515 r_op1 = gimple_assign_rhs1 (stmt);
1516 r_op2 = gimple_assign_rhs2 (stmt);
1518 /* Make R_OP1 to hold reduction variable. */
1519 if (r_op2 == PHI_RESULT (header_phi)
1520 && reduction_op == PLUS_EXPR)
1526 else if (r_op1 != PHI_RESULT (header_phi))
1529 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1530 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1532 gimple use_stmt = USE_STMT (use_p);
1533 if (is_gimple_debug (use_stmt))
1535 if (use_stmt == stmt)
1537 if (gimple_code (use_stmt) != GIMPLE_PHI)
1541 *op0 = r_op1; *op1 = r_op2;
1546 /* Converts conditional scalar reduction into unconditional form, e.g.
1548 if (_5 != 0) goto bb_5 else goto bb_6
1554 # res_2 = PHI <res_13(4), res_6(5)>
1557 will be converted into sequence
1558 _ifc__1 = _5 != 0 ? 1 : 0;
1559 res_2 = res_13 + _ifc__1;
1560 Argument SWAP tells that arguments of conditional expression should be
1562 Returns rhs of resulting PHI assignment. */
1565 convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
1566 tree cond, tree op0, tree op1, bool swap)
1568 gimple_stmt_iterator stmt_it;
1571 tree rhs1 = gimple_assign_rhs1 (reduc);
1572 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1574 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1576 if (dump_file && (dump_flags & TDF_DETAILS))
1578 fprintf (dump_file, "Found cond scalar reduction.\n");
1579 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1582 /* Build cond expression using COND and constant operand
1583 of reduction rhs. */
1584 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1585 unshare_expr (cond),
1589 /* Create assignment stmt and insert it at GSI. */
1590 new_assign = gimple_build_assign (tmp, c);
1591 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1592 /* Build rhs for unconditional increment/decrement. */
1593 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1594 TREE_TYPE (rhs1), op0, tmp);
1596 /* Delete original reduction stmt. */
1597 stmt_it = gsi_for_stmt (reduc);
1598 gsi_remove (&stmt_it, true);
1599 release_defs (reduc);
1603 /* Helpers for PHI arguments hashtable map. */
1605 struct phi_args_hash_traits : default_hashmap_traits
1607 static inline hashval_t hash (tree);
1608 static inline bool equal_keys (tree, tree);
1612 phi_args_hash_traits::hash (tree value)
1614 return iterative_hash_expr (value, 0);
1618 phi_args_hash_traits::equal_keys (tree value1, tree value2)
1620 return operand_equal_p (value1, value2, 0);
1623 /* Produce condition for all occurrences of ARG in PHI node. */
1626 gen_phi_arg_condition (gphi *phi, vec<int> *occur,
1627 gimple_stmt_iterator *gsi)
1631 tree cond = NULL_TREE;
1635 len = occur->length ();
1636 gcc_assert (len > 0);
1637 for (i = 0; i < len; i++)
1639 e = gimple_phi_arg_edge (phi, (*occur)[i]);
1640 c = bb_predicate (e->src);
1641 if (is_true_predicate (c))
1643 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
1644 is_gimple_condexpr, NULL_TREE,
1645 true, GSI_SAME_STMT);
1646 if (cond != NULL_TREE)
1648 /* Must build OR expression. */
1649 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
1650 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1651 is_gimple_condexpr, NULL_TREE,
1652 true, GSI_SAME_STMT);
1657 gcc_assert (cond != NULL_TREE);
1661 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1662 This routine can handle PHI nodes with more than two arguments.
1665 S1: A = PHI <x1(1), x2(5)>
1667 S2: A = cond ? x1 : x2;
1669 The generated code is inserted at GSI that points to the top of
1670 basic block's statement list.
1671 If PHI node has more than two arguments a chain of conditional
1672 expression is produced. */
1676 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
1678 gimple new_stmt = NULL, reduc;
1679 tree rhs, res, arg0, arg1, op0, op1, scev;
1681 unsigned int index0;
1682 unsigned int max, args_len;
1687 res = gimple_phi_result (phi);
1688 if (virtual_operand_p (res))
1691 if ((rhs = degenerate_phi_result (phi))
1692 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1694 && !chrec_contains_undetermined (scev)
1696 && (rhs = gimple_phi_arg_def (phi, 0))))
1698 if (dump_file && (dump_flags & TDF_DETAILS))
1700 fprintf (dump_file, "Degenerate phi!\n");
1701 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1703 new_stmt = gimple_build_assign (res, rhs);
1704 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1705 update_stmt (new_stmt);
1709 bb = gimple_bb (phi);
1710 if (EDGE_COUNT (bb->preds) == 2)
1712 /* Predicate ordinary PHI node with 2 arguments. */
1713 edge first_edge, second_edge;
1714 basic_block true_bb;
1715 first_edge = EDGE_PRED (bb, 0);
1716 second_edge = EDGE_PRED (bb, 1);
1717 cond = bb_predicate (first_edge->src);
1718 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1720 edge tmp_edge = first_edge;
1721 first_edge = second_edge;
1722 second_edge = tmp_edge;
1724 if (EDGE_COUNT (first_edge->src->succs) > 1)
1726 cond = bb_predicate (second_edge->src);
1727 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1728 cond = TREE_OPERAND (cond, 0);
1730 first_edge = second_edge;
1733 cond = bb_predicate (first_edge->src);
1734 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1735 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1736 is_gimple_condexpr, NULL_TREE,
1737 true, GSI_SAME_STMT);
1738 true_bb = first_edge->src;
1739 if (EDGE_PRED (bb, 1)->src == true_bb)
1741 arg0 = gimple_phi_arg_def (phi, 1);
1742 arg1 = gimple_phi_arg_def (phi, 0);
1746 arg0 = gimple_phi_arg_def (phi, 0);
1747 arg1 = gimple_phi_arg_def (phi, 1);
1749 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
1751 /* Convert reduction stmt into vectorizable form. */
1752 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1753 true_bb != gimple_bb (reduc));
1755 /* Build new RHS using selected condition and arguments. */
1756 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1758 new_stmt = gimple_build_assign (res, rhs);
1759 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1760 update_stmt (new_stmt);
1762 if (dump_file && (dump_flags & TDF_DETAILS))
1764 fprintf (dump_file, "new phi replacement stmt\n");
1765 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1770 /* Create hashmap for PHI node which contain vector of argument indexes
1771 having the same value. */
1773 hash_map<tree, auto_vec<int>, phi_args_hash_traits> phi_arg_map;
1774 unsigned int num_args = gimple_phi_num_args (phi);
1776 /* Vector of different PHI argument values. */
1777 auto_vec<tree> args (num_args);
1779 /* Compute phi_arg_map. */
1780 for (i = 0; i < num_args; i++)
1784 arg = gimple_phi_arg_def (phi, i);
1785 if (!phi_arg_map.get (arg))
1786 args.quick_push (arg);
1787 phi_arg_map.get_or_insert (arg).safe_push (i);
1790 /* Determine element with max number of occurrences. */
1793 args_len = args.length ();
1794 for (i = 0; i < args_len; i++)
1797 if ((len = phi_arg_map.get (args[i])->length ()) > max)
1804 /* Put element with max number of occurences to the end of ARGS. */
1805 if (max_ind != -1 && max_ind +1 != (int) args_len)
1807 tree tmp = args[args_len - 1];
1808 args[args_len - 1] = args[max_ind];
1809 args[max_ind] = tmp;
1812 /* Handle one special case when number of arguments with different values
1813 is equal 2 and one argument has the only occurrence. Such PHI can be
1814 handled as if would have only 2 arguments. */
1815 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
1818 indexes = phi_arg_map.get (args[0]);
1819 index0 = (*indexes)[0];
1822 e = gimple_phi_arg_edge (phi, index0);
1823 cond = bb_predicate (e->src);
1824 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1827 cond = TREE_OPERAND (cond, 0);
1829 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1830 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1831 is_gimple_condexpr, NULL_TREE,
1832 true, GSI_SAME_STMT);
1833 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
1835 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1839 /* Convert reduction stmt into vectorizable form. */
1840 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1842 new_stmt = gimple_build_assign (res, rhs);
1843 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1844 update_stmt (new_stmt);
1850 tree type = TREE_TYPE (gimple_phi_result (phi));
1853 for (i = 0; i < args_len; i++)
1856 indexes = phi_arg_map.get (args[i]);
1857 if (i != args_len - 1)
1858 lhs = make_temp_ssa_name (type, NULL, "_ifc_");
1861 cond = gen_phi_arg_condition (phi, indexes, gsi);
1862 rhs = fold_build_cond_expr (type, unshare_expr (cond),
1864 new_stmt = gimple_build_assign (lhs, rhs);
1865 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1866 update_stmt (new_stmt);
1871 if (dump_file && (dump_flags & TDF_DETAILS))
1873 fprintf (dump_file, "new extended phi replacement stmt\n");
1874 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1878 /* Replaces in LOOP all the scalar phi nodes other than those in the
1879 LOOP->header block with conditional modify expressions. */
1882 predicate_all_scalar_phis (struct loop *loop)
1885 unsigned int orig_loop_num_nodes = loop->num_nodes;
1888 for (i = 1; i < orig_loop_num_nodes; i++)
1891 gimple_stmt_iterator gsi;
1892 gphi_iterator phi_gsi;
1895 if (bb == loop->header)
1898 if (EDGE_COUNT (bb->preds) == 1)
1901 phi_gsi = gsi_start_phis (bb);
1902 if (gsi_end_p (phi_gsi))
1905 gsi = gsi_after_labels (bb);
1906 while (!gsi_end_p (phi_gsi))
1908 phi = phi_gsi.phi ();
1909 predicate_scalar_phi (phi, &gsi);
1910 release_phi_node (phi);
1911 gsi_next (&phi_gsi);
1914 set_phi_nodes (bb, NULL);
1918 /* Insert in each basic block of LOOP the statements produced by the
1919 gimplification of the predicates. */
1922 insert_gimplified_predicates (loop_p loop, bool any_mask_load_store)
1926 for (i = 0; i < loop->num_nodes; i++)
1928 basic_block bb = ifc_bbs[i];
1930 if (!is_predicated (bb))
1931 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
1932 if (!is_predicated (bb))
1934 /* Do not insert statements for a basic block that is not
1935 predicated. Also make sure that the predicate of the
1936 basic block is set to true. */
1937 reset_bb_predicate (bb);
1941 stmts = bb_predicate_gimplified_stmts (bb);
1944 if (flag_tree_loop_if_convert_stores
1945 || any_mask_load_store)
1947 /* Insert the predicate of the BB just after the label,
1948 as the if-conversion of memory writes will use this
1950 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1951 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1955 /* Insert the predicate of the BB at the end of the BB
1956 as this would reduce the register pressure: the only
1957 use of this predicate will be in successor BBs. */
1958 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1961 || stmt_ends_bb_p (gsi_stmt (gsi)))
1962 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1964 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1967 /* Once the sequence is code generated, set it to NULL. */
1968 set_bb_predicate_gimplified_stmts (bb, NULL);
1973 /* Helper function for predicate_mem_writes. Returns index of existent
1974 mask if it was created for given SIZE and -1 otherwise. */
1977 mask_exists (int size, vec<int> vec)
1981 FOR_EACH_VEC_ELT (vec, ix, v)
1987 /* Predicate each write to memory in LOOP.
1989 This function transforms control flow constructs containing memory
1992 | for (i = 0; i < N; i++)
1996 into the following form that does not contain control flow:
1998 | for (i = 0; i < N; i++)
1999 | A[i] = cond ? expr : A[i];
2001 The original CFG looks like this:
2008 | if (i < N) goto bb_5 else goto bb_2
2012 | cond = some_computation;
2013 | if (cond) goto bb_3 else goto bb_4
2025 insert_gimplified_predicates inserts the computation of the COND
2026 expression at the beginning of the destination basic block:
2033 | if (i < N) goto bb_5 else goto bb_2
2037 | cond = some_computation;
2038 | if (cond) goto bb_3 else goto bb_4
2042 | cond = some_computation;
2051 predicate_mem_writes is then predicating the memory write as follows:
2058 | if (i < N) goto bb_5 else goto bb_2
2062 | if (cond) goto bb_3 else goto bb_4
2066 | cond = some_computation;
2067 | A[i] = cond ? expr : A[i];
2075 and finally combine_blocks removes the basic block boundaries making
2076 the loop vectorizable:
2080 | if (i < N) goto bb_5 else goto bb_1
2084 | cond = some_computation;
2085 | A[i] = cond ? expr : A[i];
2086 | if (i < N) goto bb_5 else goto bb_4
2095 predicate_mem_writes (loop_p loop)
2097 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2098 auto_vec<int, 1> vect_sizes;
2099 auto_vec<tree, 1> vect_masks;
2101 for (i = 1; i < orig_loop_num_nodes; i++)
2103 gimple_stmt_iterator gsi;
2104 basic_block bb = ifc_bbs[i];
2105 tree cond = bb_predicate (bb);
2110 if (is_true_predicate (cond))
2114 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2117 cond = TREE_OPERAND (cond, 0);
2120 vect_sizes.truncate (0);
2121 vect_masks.truncate (0);
2123 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2124 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
2126 else if (gimple_plf (stmt, GF_PLF_2))
2128 tree lhs = gimple_assign_lhs (stmt);
2129 tree rhs = gimple_assign_rhs1 (stmt);
2130 tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask;
2132 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
2133 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2134 mark_addressable (ref);
2135 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
2136 true, NULL_TREE, true,
2138 if (!vect_sizes.is_empty ()
2139 && (index = mask_exists (bitsize, vect_sizes)) != -1)
2140 /* Use created mask. */
2141 mask = vect_masks[index];
2144 masktype = build_nonstandard_integer_type (bitsize, 1);
2145 mask_op0 = build_int_cst (masktype, swap ? 0 : -1);
2146 mask_op1 = build_int_cst (masktype, swap ? -1 : 0);
2147 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2150 true, GSI_SAME_STMT);
2151 mask = fold_build_cond_expr (masktype, unshare_expr (cond),
2152 mask_op0, mask_op1);
2153 mask = ifc_temp_var (masktype, mask, &gsi);
2154 /* Save mask and its size for further use. */
2155 vect_sizes.safe_push (bitsize);
2156 vect_masks.safe_push (mask);
2158 ptr = build_int_cst (reference_alias_ptr_type (ref), 0);
2159 /* Copy points-to info if possible. */
2160 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2161 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2163 if (TREE_CODE (lhs) == SSA_NAME)
2166 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2168 gimple_call_set_lhs (new_stmt, lhs);
2172 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2174 gsi_replace (&gsi, new_stmt, true);
2176 else if (gimple_vdef (stmt))
2178 tree lhs = gimple_assign_lhs (stmt);
2179 tree rhs = gimple_assign_rhs1 (stmt);
2180 tree type = TREE_TYPE (lhs);
2182 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2183 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2190 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2191 is_gimple_condexpr, NULL_TREE,
2192 true, GSI_SAME_STMT);
2193 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2194 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2200 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2201 other than the exit and latch of the LOOP. Also resets the
2202 GIMPLE_DEBUG information. */
2205 remove_conditions_and_labels (loop_p loop)
2207 gimple_stmt_iterator gsi;
2210 for (i = 0; i < loop->num_nodes; i++)
2212 basic_block bb = ifc_bbs[i];
2214 if (bb_with_exit_edge_p (loop, bb)
2215 || bb == loop->latch)
2218 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2219 switch (gimple_code (gsi_stmt (gsi)))
2223 gsi_remove (&gsi, true);
2227 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2228 if (gimple_debug_bind_p (gsi_stmt (gsi)))
2230 gimple_debug_bind_reset_value (gsi_stmt (gsi));
2231 update_stmt (gsi_stmt (gsi));
2242 /* Combine all the basic blocks from LOOP into one or two super basic
2243 blocks. Replace PHI nodes with conditional modify expressions. */
2246 combine_blocks (struct loop *loop, bool any_mask_load_store)
2248 basic_block bb, exit_bb, merge_target_bb;
2249 unsigned int orig_loop_num_nodes = loop->num_nodes;
2254 predicate_bbs (loop);
2255 remove_conditions_and_labels (loop);
2256 insert_gimplified_predicates (loop, any_mask_load_store);
2257 predicate_all_scalar_phis (loop);
2259 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2260 predicate_mem_writes (loop);
2262 /* Merge basic blocks: first remove all the edges in the loop,
2263 except for those from the exit block. */
2265 for (i = 0; i < orig_loop_num_nodes; i++)
2268 free_bb_predicate (bb);
2269 if (bb_with_exit_edge_p (loop, bb))
2271 gcc_assert (exit_bb == NULL);
2275 gcc_assert (exit_bb != loop->latch);
2277 for (i = 1; i < orig_loop_num_nodes; i++)
2281 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2283 if (e->src == exit_bb)
2290 if (exit_bb != NULL)
2292 if (exit_bb != loop->header)
2294 /* Connect this node to loop header. */
2295 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2296 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2299 /* Redirect non-exit edges to loop->latch. */
2300 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2302 if (!loop_exit_edge_p (loop, e))
2303 redirect_edge_and_branch (e, loop->latch);
2305 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2309 /* If the loop does not have an exit, reconnect header and latch. */
2310 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2311 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2314 merge_target_bb = loop->header;
2315 for (i = 1; i < orig_loop_num_nodes; i++)
2317 gimple_stmt_iterator gsi;
2318 gimple_stmt_iterator last;
2322 if (bb == exit_bb || bb == loop->latch)
2325 /* Make stmts member of loop->header. */
2326 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2327 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
2329 /* Update stmt list. */
2330 last = gsi_last_bb (merge_target_bb);
2331 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
2332 set_bb_seq (bb, NULL);
2334 delete_basic_block (bb);
2337 /* If possible, merge loop header to the block with the exit edge.
2338 This reduces the number of basic blocks to two, to please the
2339 vectorizer that handles only loops with two nodes. */
2341 && exit_bb != loop->header
2342 && can_merge_blocks_p (loop->header, exit_bb))
2343 merge_blocks (loop->header, exit_bb);
2349 /* Version LOOP before if-converting it, the original loop
2350 will be then if-converted, the new copy of the loop will not,
2351 and the LOOP_VECTORIZED internal call will be guarding which
2352 loop to execute. The vectorizer pass will fold this
2353 internal call into either true or false. */
2356 version_loop_for_if_conversion (struct loop *loop)
2358 basic_block cond_bb;
2359 tree cond = make_ssa_name (boolean_type_node);
2360 struct loop *new_loop;
2362 gimple_stmt_iterator gsi;
2364 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2365 build_int_cst (integer_type_node, loop->num),
2367 gimple_call_set_lhs (g, cond);
2369 initialize_original_copy_tables ();
2370 new_loop = loop_version (loop, cond, &cond_bb,
2371 REG_BR_PROB_BASE, REG_BR_PROB_BASE,
2372 REG_BR_PROB_BASE, true);
2373 free_original_copy_tables ();
2374 if (new_loop == NULL)
2376 new_loop->dont_vectorize = true;
2377 new_loop->force_vectorize = false;
2378 gsi = gsi_last_bb (cond_bb);
2379 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2380 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2381 update_ssa (TODO_update_ssa);
2385 /* Performs splitting of critical edges if aggressive_if_conv is true.
2386 Returns false if loop won't be if converted and true otherwise. */
2389 ifcvt_split_critical_edges (struct loop *loop)
2393 unsigned int num = loop->num_nodes;
2403 if (!single_exit (loop))
2406 body = get_loop_body (loop);
2407 for (i = 0; i < num; i++)
2410 if (bb == loop->latch
2411 || bb_with_exit_edge_p (loop, bb))
2413 stmt = last_stmt (bb);
2414 /* Skip basic blocks not ending with conditional branch. */
2415 if (!(stmt && gimple_code (stmt) == GIMPLE_COND))
2417 FOR_EACH_EDGE (e, ei, bb->succs)
2418 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
2425 /* Assumes that lhs of DEF_STMT have multiple uses.
2426 Delete one use by (1) creation of copy DEF_STMT with
2427 unique lhs; (2) change original use of lhs in one
2428 use statement with newly created lhs. */
2431 ifcvt_split_def_stmt (gimple def_stmt, gimple use_stmt)
2436 gimple_stmt_iterator gsi;
2437 use_operand_p use_p;
2438 imm_use_iterator imm_iter;
2440 var = gimple_assign_lhs (def_stmt);
2441 copy_stmt = gimple_copy (def_stmt);
2442 lhs = make_temp_ssa_name (TREE_TYPE (var), NULL, "_ifc_");
2443 gimple_assign_set_lhs (copy_stmt, lhs);
2444 SSA_NAME_DEF_STMT (lhs) = copy_stmt;
2445 /* Insert copy of DEF_STMT. */
2446 gsi = gsi_for_stmt (def_stmt);
2447 gsi_insert_after (&gsi, copy_stmt, GSI_SAME_STMT);
2448 /* Change use of var to lhs in use_stmt. */
2449 if (dump_file && (dump_flags & TDF_DETAILS))
2451 fprintf (dump_file, "Change use of var ");
2452 print_generic_expr (dump_file, var, TDF_SLIM);
2453 fprintf (dump_file, " to ");
2454 print_generic_expr (dump_file, lhs, TDF_SLIM);
2455 fprintf (dump_file, "\n");
2457 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
2459 if (USE_STMT (use_p) != use_stmt)
2461 SET_USE (use_p, lhs);
2466 /* Traverse bool pattern recursively starting from VAR.
2467 Save its def and use statements to defuse_list if VAR does
2468 not have single use. */
2471 ifcvt_walk_pattern_tree (tree var, vec<gimple> *defuse_list,
2475 enum tree_code code;
2478 def_stmt = SSA_NAME_DEF_STMT (var);
2479 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2481 if (!has_single_use (var))
2483 /* Put def and use stmts into defuse_list. */
2484 defuse_list->safe_push (def_stmt);
2485 defuse_list->safe_push (use_stmt);
2486 if (dump_file && (dump_flags & TDF_DETAILS))
2488 fprintf (dump_file, "Multiple lhs uses in stmt\n");
2489 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
2492 rhs1 = gimple_assign_rhs1 (def_stmt);
2493 code = gimple_assign_rhs_code (def_stmt);
2497 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2500 if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2501 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2502 && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
2504 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2507 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2512 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2513 rhs2 = gimple_assign_rhs2 (def_stmt);
2514 ifcvt_walk_pattern_tree (rhs2, defuse_list, def_stmt);
2522 /* Returns true if STMT can be a root of bool pattern apllied
2526 stmt_is_root_of_bool_pattern (gimple stmt)
2528 enum tree_code code;
2531 code = gimple_assign_rhs_code (stmt);
2532 if (CONVERT_EXPR_CODE_P (code))
2534 lhs = gimple_assign_lhs (stmt);
2535 rhs = gimple_assign_rhs1 (stmt);
2536 if (TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
2538 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
2542 else if (code == COND_EXPR)
2544 rhs = gimple_assign_rhs1 (stmt);
2545 if (TREE_CODE (rhs) != SSA_NAME)
2552 /* Traverse all statements in BB which correspondent to loop header to
2553 find out all statements which can start bool pattern applied by
2554 vectorizer and convert multiple uses in it to conform pattern
2555 restrictions. Such case can occur if the same predicate is used both
2556 for phi node conversion and load/store mask. */
2559 ifcvt_repair_bool_pattern (basic_block bb)
2563 gimple_stmt_iterator gsi;
2564 vec<gimple> defuse_list = vNULL;
2565 vec<gimple> pattern_roots = vNULL;
2570 /* Collect all root pattern statements. */
2571 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2573 stmt = gsi_stmt (gsi);
2574 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2576 if (!stmt_is_root_of_bool_pattern (stmt))
2578 pattern_roots.safe_push (stmt);
2581 if (pattern_roots.is_empty ())
2584 /* Split all statements with multiple uses iteratively since splitting
2585 may create new multiple uses. */
2590 FOR_EACH_VEC_ELT (pattern_roots, ix, stmt)
2592 rhs = gimple_assign_rhs1 (stmt);
2593 ifcvt_walk_pattern_tree (rhs, &defuse_list, stmt);
2594 while (defuse_list.length () > 0)
2597 gimple def_stmt, use_stmt;
2598 use_stmt = defuse_list.pop ();
2599 def_stmt = defuse_list.pop ();
2600 ifcvt_split_def_stmt (def_stmt, use_stmt);
2605 if (dump_file && (dump_flags & TDF_DETAILS))
2606 fprintf (dump_file, "Repair bool pattern takes %d iterations. \n",
2610 /* Delete redundant statements produced by predication which prevents
2611 loop vectorization. */
2614 ifcvt_local_dce (basic_block bb)
2619 gimple_stmt_iterator gsi;
2620 vec<gimple> worklist;
2621 enum gimple_code code;
2622 use_operand_p use_p;
2623 imm_use_iterator imm_iter;
2625 worklist.create (64);
2626 /* Consider all phi as live statements. */
2627 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2629 phi = gsi_stmt (gsi);
2630 gimple_set_plf (phi, GF_PLF_2, true);
2631 worklist.safe_push (phi);
2633 /* Consider load/store statemnts, CALL and COND as live. */
2634 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2636 stmt = gsi_stmt (gsi);
2637 if (gimple_store_p (stmt)
2638 || gimple_assign_load_p (stmt)
2639 || is_gimple_debug (stmt))
2641 gimple_set_plf (stmt, GF_PLF_2, true);
2642 worklist.safe_push (stmt);
2645 code = gimple_code (stmt);
2646 if (code == GIMPLE_COND || code == GIMPLE_CALL)
2648 gimple_set_plf (stmt, GF_PLF_2, true);
2649 worklist.safe_push (stmt);
2652 gimple_set_plf (stmt, GF_PLF_2, false);
2654 if (code == GIMPLE_ASSIGN)
2656 tree lhs = gimple_assign_lhs (stmt);
2657 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2659 stmt1 = USE_STMT (use_p);
2660 if (gimple_bb (stmt1) != bb)
2662 gimple_set_plf (stmt, GF_PLF_2, true);
2663 worklist.safe_push (stmt);
2669 /* Propagate liveness through arguments of live stmt. */
2670 while (worklist.length () > 0)
2673 use_operand_p use_p;
2676 stmt = worklist.pop ();
2677 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2679 use = USE_FROM_PTR (use_p);
2680 if (TREE_CODE (use) != SSA_NAME)
2682 stmt1 = SSA_NAME_DEF_STMT (use);
2683 if (gimple_bb (stmt1) != bb
2684 || gimple_plf (stmt1, GF_PLF_2))
2686 gimple_set_plf (stmt1, GF_PLF_2, true);
2687 worklist.safe_push (stmt1);
2690 /* Delete dead statements. */
2691 gsi = gsi_start_bb (bb);
2692 while (!gsi_end_p (gsi))
2694 stmt = gsi_stmt (gsi);
2695 if (gimple_plf (stmt, GF_PLF_2))
2700 if (dump_file && (dump_flags & TDF_DETAILS))
2702 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
2703 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2705 gsi_remove (&gsi, true);
2706 release_defs (stmt);
2710 /* If-convert LOOP when it is legal. For the moment this pass has no
2711 profitability analysis. Returns non-zero todo flags when something
2715 tree_if_conversion (struct loop *loop)
2717 unsigned int todo = 0;
2719 bool any_mask_load_store = false;
2721 /* Set-up aggressive if-conversion for loops marked with simd pragma. */
2722 aggressive_if_conv = loop->force_vectorize;
2723 /* Check either outer loop was marked with simd pragma. */
2724 if (!aggressive_if_conv)
2726 struct loop *outer_loop = loop_outer (loop);
2727 if (outer_loop && outer_loop->force_vectorize)
2728 aggressive_if_conv = true;
2731 if (aggressive_if_conv)
2732 if (!ifcvt_split_critical_edges (loop))
2735 if (!if_convertible_loop_p (loop, &any_mask_load_store)
2736 || !dbg_cnt (if_conversion_tree))
2739 if (any_mask_load_store
2740 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
2741 || loop->dont_vectorize))
2744 if (any_mask_load_store && !version_loop_for_if_conversion (loop))
2747 /* Now all statements are if-convertible. Combine all the basic
2748 blocks into one huge basic block doing the if-conversion
2750 combine_blocks (loop, any_mask_load_store);
2752 /* Delete dead predicate computations and repair tree correspondent
2753 to bool pattern to delete multiple uses of preidcates. */
2754 if (aggressive_if_conv)
2756 ifcvt_local_dce (loop->header);
2757 ifcvt_repair_bool_pattern (loop->header);
2760 todo |= TODO_cleanup_cfg;
2761 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2763 mark_virtual_operands_for_renaming (cfun);
2764 todo |= TODO_update_ssa_only_virtuals;
2772 for (i = 0; i < loop->num_nodes; i++)
2773 free_bb_predicate (ifc_bbs[i]);
2778 free_dominance_info (CDI_POST_DOMINATORS);
2783 /* Tree if-conversion pass management. */
2787 const pass_data pass_data_if_conversion =
2789 GIMPLE_PASS, /* type */
2791 OPTGROUP_NONE, /* optinfo_flags */
2792 TV_NONE, /* tv_id */
2793 ( PROP_cfg | PROP_ssa ), /* properties_required */
2794 0, /* properties_provided */
2795 0, /* properties_destroyed */
2796 0, /* todo_flags_start */
2797 0, /* todo_flags_finish */
2800 class pass_if_conversion : public gimple_opt_pass
2803 pass_if_conversion (gcc::context *ctxt)
2804 : gimple_opt_pass (pass_data_if_conversion, ctxt)
2807 /* opt_pass methods: */
2808 virtual bool gate (function *);
2809 virtual unsigned int execute (function *);
2811 }; // class pass_if_conversion
2814 pass_if_conversion::gate (function *fun)
2816 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
2817 && flag_tree_loop_if_convert != 0)
2818 || flag_tree_loop_if_convert == 1
2819 || flag_tree_loop_if_convert_stores == 1);
2823 pass_if_conversion::execute (function *fun)
2828 if (number_of_loops (fun) <= 1)
2831 FOR_EACH_LOOP (loop, 0)
2832 if (flag_tree_loop_if_convert == 1
2833 || flag_tree_loop_if_convert_stores == 1
2834 || ((flag_tree_loop_vectorize || loop->force_vectorize)
2835 && !loop->dont_vectorize))
2836 todo |= tree_if_conversion (loop);
2838 #ifdef ENABLE_CHECKING
2841 FOR_EACH_BB_FN (bb, fun)
2842 gcc_assert (!bb->aux);
2852 make_pass_if_conversion (gcc::context *ctxt)
2854 return new pass_if_conversion (ctxt);