1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2013 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"
89 #include "basic-block.h"
90 #include "gimple-pretty-print.h"
92 #include "gimple-ssa.h"
94 #include "tree-phinodes.h"
95 #include "ssa-iterators.h"
96 #include "tree-ssanames.h"
97 #include "tree-into-ssa.h"
100 #include "tree-chrec.h"
101 #include "tree-data-ref.h"
102 #include "tree-scalar-evolution.h"
103 #include "tree-pass.h"
106 /* List of basic blocks in if-conversion-suitable order. */
107 static basic_block
*ifc_bbs
;
109 /* Structure used to predicate basic blocks. This is attached to the
110 ->aux field of the BBs in the loop to be if-converted. */
111 typedef struct bb_predicate_s
{
113 /* The condition under which this basic block is executed. */
116 /* PREDICATE is gimplified, and the sequence of statements is
117 recorded here, in order to avoid the duplication of computations
118 that occur in previous conditions. See PR44483. */
119 gimple_seq predicate_gimplified_stmts
;
122 /* Returns true when the basic block BB has a predicate. */
125 bb_has_predicate (basic_block bb
)
127 return bb
->aux
!= NULL
;
130 /* Returns the gimplified predicate for basic block BB. */
133 bb_predicate (basic_block bb
)
135 return ((bb_predicate_p
) bb
->aux
)->predicate
;
138 /* Sets the gimplified predicate COND for basic block BB. */
141 set_bb_predicate (basic_block bb
, tree cond
)
143 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
144 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
145 || is_gimple_condexpr (cond
));
146 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
149 /* Returns the sequence of statements of the gimplification of the
150 predicate for basic block BB. */
152 static inline gimple_seq
153 bb_predicate_gimplified_stmts (basic_block bb
)
155 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
158 /* Sets the sequence of statements STMTS of the gimplification of the
159 predicate for basic block BB. */
162 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
164 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
167 /* Adds the sequence of statements STMTS to the sequence of statements
168 of the predicate for basic block BB. */
171 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
174 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
177 /* Initializes to TRUE the predicate of basic block BB. */
180 init_bb_predicate (basic_block bb
)
182 bb
->aux
= XNEW (struct bb_predicate_s
);
183 set_bb_predicate_gimplified_stmts (bb
, NULL
);
184 set_bb_predicate (bb
, boolean_true_node
);
187 /* Free the predicate of basic block BB. */
190 free_bb_predicate (basic_block bb
)
194 if (!bb_has_predicate (bb
))
197 /* Release the SSA_NAMEs created for the gimplification of the
199 stmts
= bb_predicate_gimplified_stmts (bb
);
202 gimple_stmt_iterator i
;
204 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
205 free_stmt_operands (gsi_stmt (i
));
212 /* Free the predicate of BB and reinitialize it with the true
216 reset_bb_predicate (basic_block bb
)
218 free_bb_predicate (bb
);
219 init_bb_predicate (bb
);
222 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
223 the expression EXPR. Inserts the statement created for this
224 computation before GSI and leaves the iterator GSI at the same
228 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
230 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
231 gimple stmt
= gimple_build_assign (new_name
, expr
);
232 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
236 /* Return true when COND is a true predicate. */
239 is_true_predicate (tree cond
)
241 return (cond
== NULL_TREE
242 || cond
== boolean_true_node
243 || integer_onep (cond
));
246 /* Returns true when BB has a predicate that is not trivial: true or
250 is_predicated (basic_block bb
)
252 return !is_true_predicate (bb_predicate (bb
));
255 /* Parses the predicate COND and returns its comparison code and
256 operands OP0 and OP1. */
258 static enum tree_code
259 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
263 if (TREE_CODE (cond
) == SSA_NAME
264 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
266 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
268 *op0
= gimple_assign_rhs1 (s
);
269 *op1
= gimple_assign_rhs2 (s
);
270 return gimple_assign_rhs_code (s
);
273 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
275 tree op
= gimple_assign_rhs1 (s
);
276 tree type
= TREE_TYPE (op
);
277 enum tree_code code
= parse_predicate (op
, op0
, op1
);
279 return code
== ERROR_MARK
? ERROR_MARK
280 : invert_tree_comparison (code
, HONOR_NANS (TYPE_MODE (type
)));
286 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
)
288 *op0
= TREE_OPERAND (cond
, 0);
289 *op1
= TREE_OPERAND (cond
, 1);
290 return TREE_CODE (cond
);
296 /* Returns the fold of predicate C1 OR C2 at location LOC. */
299 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
301 tree op1a
, op1b
, op2a
, op2b
;
302 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
303 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
305 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
307 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
313 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
316 /* Returns true if N is either a constant or a SSA_NAME. */
319 constant_or_ssa_name (tree n
)
321 switch (TREE_CODE (n
))
334 /* Returns either a COND_EXPR or the folded expression if the folded
335 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
336 a constant or a SSA_NAME. */
339 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
341 tree rhs1
, lhs1
, cond_expr
;
342 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
345 if (cond_expr
== NULL_TREE
)
346 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
348 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
350 if (constant_or_ssa_name (cond_expr
))
353 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
355 rhs1
= TREE_OPERAND (cond_expr
, 1);
356 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
357 if (constant_or_ssa_name (rhs1
))
358 return build1 (ABS_EXPR
, type
, rhs1
);
361 if (TREE_CODE (cond_expr
) == MIN_EXPR
362 || TREE_CODE (cond_expr
) == MAX_EXPR
)
364 lhs1
= TREE_OPERAND (cond_expr
, 0);
365 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
366 rhs1
= TREE_OPERAND (cond_expr
, 1);
367 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
368 if (constant_or_ssa_name (rhs1
)
369 && constant_or_ssa_name (lhs1
))
370 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
372 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
375 /* Add condition NC to the predicate list of basic block BB. */
378 add_to_predicate_list (basic_block bb
, tree nc
)
382 if (is_true_predicate (nc
))
385 if (!is_predicated (bb
))
389 bc
= bb_predicate (bb
);
390 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
391 if (is_true_predicate (bc
))
393 reset_bb_predicate (bb
);
398 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
399 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
400 tp
= &TREE_OPERAND (bc
, 0);
403 if (!is_gimple_condexpr (*tp
))
406 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
407 add_bb_predicate_gimplified_stmts (bb
, stmts
);
409 set_bb_predicate (bb
, bc
);
412 /* Add the condition COND to the previous condition PREV_COND, and add
413 this to the predicate list of the destination of edge E. LOOP is
414 the loop to be if-converted. */
417 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
418 tree prev_cond
, tree cond
)
420 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
423 if (!is_true_predicate (prev_cond
))
424 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
427 add_to_predicate_list (e
->dest
, cond
);
430 /* Return true if one of the successor edges of BB exits LOOP. */
433 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
438 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
439 if (loop_exit_edge_p (loop
, e
))
445 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
446 and it belongs to basic block BB.
448 PHI is not if-convertible if:
449 - it has more than 2 arguments.
451 When the flag_tree_loop_if_convert_stores is not set, PHI is not
453 - a virtual PHI is immediately used in another PHI node,
454 - there is a virtual PHI in a BB other than the loop->header. */
457 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
461 fprintf (dump_file
, "-------------------------\n");
462 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
465 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
468 fprintf (dump_file
, "More than two phi node args.\n");
472 if (flag_tree_loop_if_convert_stores
)
475 /* When the flag_tree_loop_if_convert_stores is not set, check
476 that there are no memory writes in the branches of the loop to be
478 if (virtual_operand_p (gimple_phi_result (phi
)))
480 imm_use_iterator imm_iter
;
483 if (bb
!= loop
->header
)
485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
486 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
490 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
492 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
495 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
504 /* Records the status of a data reference. This struct is attached to
505 each DR->aux field. */
508 /* -1 when not initialized, 0 when false, 1 when true. */
509 int written_at_least_once
;
511 /* -1 when not initialized, 0 when false, 1 when true. */
512 int rw_unconditionally
;
515 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
516 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
517 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
519 /* Returns true when the memory references of STMT are read or written
520 unconditionally. In other words, this function returns true when
521 for every data reference A in STMT there exist other accesses to
522 a data reference with the same base with predicates that add up (OR-up) to
523 the true predicate: this ensures that the data reference A is touched
524 (read or written) on every iteration of the if-converted loop. */
527 memrefs_read_or_written_unconditionally (gimple stmt
,
528 vec
<data_reference_p
> drs
)
531 data_reference_p a
, b
;
532 tree ca
= bb_predicate (gimple_bb (stmt
));
534 for (i
= 0; drs
.iterate (i
, &a
); i
++)
535 if (DR_STMT (a
) == stmt
)
538 int x
= DR_RW_UNCONDITIONALLY (a
);
546 for (j
= 0; drs
.iterate (j
, &b
); j
++)
548 tree ref_base_a
= DR_REF (a
);
549 tree ref_base_b
= DR_REF (b
);
551 if (DR_STMT (b
) == stmt
)
554 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
555 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
556 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
557 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
559 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
560 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
561 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
562 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
564 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
566 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
568 if (DR_RW_UNCONDITIONALLY (b
) == 1
569 || is_true_predicate (cb
)
570 || is_true_predicate (ca
571 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
573 DR_RW_UNCONDITIONALLY (a
) = 1;
574 DR_RW_UNCONDITIONALLY (b
) = 1;
583 DR_RW_UNCONDITIONALLY (a
) = 0;
591 /* Returns true when the memory references of STMT are unconditionally
592 written. In other words, this function returns true when for every
593 data reference A written in STMT, there exist other writes to the
594 same data reference with predicates that add up (OR-up) to the true
595 predicate: this ensures that the data reference A is written on
596 every iteration of the if-converted loop. */
599 write_memrefs_written_at_least_once (gimple stmt
,
600 vec
<data_reference_p
> drs
)
603 data_reference_p a
, b
;
604 tree ca
= bb_predicate (gimple_bb (stmt
));
606 for (i
= 0; drs
.iterate (i
, &a
); i
++)
607 if (DR_STMT (a
) == stmt
611 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
619 for (j
= 0; drs
.iterate (j
, &b
); j
++)
620 if (DR_STMT (b
) != stmt
622 && same_data_refs_base_objects (a
, b
))
624 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
626 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
627 || is_true_predicate (cb
)
628 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
631 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
632 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
640 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
648 /* Return true when the memory references of STMT won't trap in the
649 if-converted code. There are two things that we have to check for:
651 - writes to memory occur to writable memory: if-conversion of
652 memory writes transforms the conditional memory writes into
653 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
654 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
655 be executed at all in the original code, it may be a readonly
656 memory. To check that A is not const-qualified, we check that
657 there exists at least an unconditional write to A in the current
660 - reads or writes to memory are valid memory accesses for every
661 iteration. To check that the memory accesses are correctly formed
662 and that we are allowed to read and write in these locations, we
663 check that the memory accesses to be if-converted occur at every
664 iteration unconditionally. */
667 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
669 return write_memrefs_written_at_least_once (stmt
, refs
)
670 && memrefs_read_or_written_unconditionally (stmt
, refs
);
673 /* Wrapper around gimple_could_trap_p refined for the needs of the
674 if-conversion. Try to prove that the memory accesses of STMT could
675 not trap in the innermost loop containing STMT. */
678 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
680 if (gimple_vuse (stmt
)
681 && !gimple_could_trap_p_1 (stmt
, false, false)
682 && ifcvt_memrefs_wont_trap (stmt
, refs
))
685 return gimple_could_trap_p (stmt
);
688 /* Return true when STMT is if-convertible.
690 GIMPLE_ASSIGN statement is not if-convertible if,
693 - LHS is not var decl. */
696 if_convertible_gimple_assign_stmt_p (gimple stmt
,
697 vec
<data_reference_p
> refs
)
699 tree lhs
= gimple_assign_lhs (stmt
);
702 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
704 fprintf (dump_file
, "-------------------------\n");
705 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
708 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
711 /* Some of these constrains might be too conservative. */
712 if (stmt_ends_bb_p (stmt
)
713 || gimple_has_volatile_ops (stmt
)
714 || (TREE_CODE (lhs
) == SSA_NAME
715 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
716 || gimple_has_side_effects (stmt
))
718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
719 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
723 if (flag_tree_loop_if_convert_stores
)
725 if (ifcvt_could_trap_p (stmt
, refs
))
727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
728 fprintf (dump_file
, "tree could trap...\n");
734 if (gimple_assign_rhs_could_trap_p (stmt
))
736 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
737 fprintf (dump_file
, "tree could trap...\n");
741 bb
= gimple_bb (stmt
);
743 if (TREE_CODE (lhs
) != SSA_NAME
744 && bb
!= bb
->loop_father
->header
745 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
749 fprintf (dump_file
, "LHS is not var\n");
750 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
758 /* Return true when STMT is if-convertible.
760 A statement is if-convertible if:
761 - it is an if-convertible GIMPLE_ASSIGN,
762 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
765 if_convertible_stmt_p (gimple stmt
, vec
<data_reference_p
> refs
)
767 switch (gimple_code (stmt
))
775 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
779 tree fndecl
= gimple_call_fndecl (stmt
);
782 int flags
= gimple_call_flags (stmt
);
783 if ((flags
& ECF_CONST
)
784 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
785 /* We can only vectorize some builtins at the moment,
786 so restrict if-conversion to those. */
787 && DECL_BUILT_IN (fndecl
))
794 /* Don't know what to do with 'em so don't do anything. */
795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
797 fprintf (dump_file
, "don't know what to do\n");
798 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
807 /* Return true when BB is if-convertible. This routine does not check
808 basic block's statements and phis.
810 A basic block is not if-convertible if:
811 - it is non-empty and it is after the exit block (in BFS order),
812 - it is after the exit block but before the latch,
813 - its edges are not normal.
815 EXIT_BB is the basic block containing the exit of the LOOP. BB is
819 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
825 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
827 if (EDGE_COUNT (bb
->preds
) > 2
828 || EDGE_COUNT (bb
->succs
) > 2)
833 if (bb
!= loop
->latch
)
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
836 fprintf (dump_file
, "basic block after exit bb but before latch\n");
839 else if (!empty_block_p (bb
))
841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
842 fprintf (dump_file
, "non empty basic block after exit bb\n");
845 else if (bb
== loop
->latch
847 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
850 fprintf (dump_file
, "latch is not dominated by exit_block\n");
855 /* Be less adventurous and handle only normal edges. */
856 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
857 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
860 fprintf (dump_file
, "Difficult to handle edges\n");
864 /* At least one incoming edge has to be non-critical as otherwise edge
865 predicates are not equal to basic-block predicates of the edge
867 if (EDGE_COUNT (bb
->preds
) > 1
868 && bb
!= loop
->header
)
871 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
872 if (EDGE_COUNT (e
->src
->succs
) == 1)
876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
877 fprintf (dump_file
, "only critical predecessors\n");
885 /* Return true when all predecessor blocks of BB are visited. The
886 VISITED bitmap keeps track of the visited blocks. */
889 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
893 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
894 if (!bitmap_bit_p (*visited
, e
->src
->index
))
900 /* Get body of a LOOP in suitable order for if-conversion. It is
901 caller's responsibility to deallocate basic block list.
902 If-conversion suitable order is, breadth first sort (BFS) order
903 with an additional constraint: select a block only if all its
904 predecessors are already selected. */
907 get_loop_body_in_if_conv_order (const struct loop
*loop
)
909 basic_block
*blocks
, *blocks_in_bfs_order
;
912 unsigned int index
= 0;
913 unsigned int visited_count
= 0;
915 gcc_assert (loop
->num_nodes
);
916 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
918 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
919 visited
= BITMAP_ALLOC (NULL
);
921 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
924 while (index
< loop
->num_nodes
)
926 bb
= blocks_in_bfs_order
[index
];
928 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
930 free (blocks_in_bfs_order
);
931 BITMAP_FREE (visited
);
936 if (!bitmap_bit_p (visited
, bb
->index
))
938 if (pred_blocks_visited_p (bb
, &visited
)
939 || bb
== loop
->header
)
941 /* This block is now visited. */
942 bitmap_set_bit (visited
, bb
->index
);
943 blocks
[visited_count
++] = bb
;
949 if (index
== loop
->num_nodes
950 && visited_count
!= loop
->num_nodes
)
954 free (blocks_in_bfs_order
);
955 BITMAP_FREE (visited
);
959 /* Returns true when the analysis of the predicates for all the basic
960 blocks in LOOP succeeded.
962 predicate_bbs first allocates the predicates of the basic blocks.
963 These fields are then initialized with the tree expressions
964 representing the predicates under which a basic block is executed
965 in the LOOP. As the loop->header is executed at each iteration, it
966 has the "true" predicate. Other statements executed under a
967 condition are predicated with that condition, for example
974 S1 will be predicated with "x", and
975 S2 will be predicated with "!x". */
978 predicate_bbs (loop_p loop
)
982 for (i
= 0; i
< loop
->num_nodes
; i
++)
983 init_bb_predicate (ifc_bbs
[i
]);
985 for (i
= 0; i
< loop
->num_nodes
; i
++)
987 basic_block bb
= ifc_bbs
[i
];
989 gimple_stmt_iterator itr
;
991 /* The loop latch is always executed and has no extra conditions
992 to be processed: skip it. */
993 if (bb
== loop
->latch
)
995 reset_bb_predicate (loop
->latch
);
999 cond
= bb_predicate (bb
);
1001 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1003 gimple stmt
= gsi_stmt (itr
);
1005 switch (gimple_code (stmt
))
1016 edge true_edge
, false_edge
;
1017 location_t loc
= gimple_location (stmt
);
1018 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
1020 gimple_cond_lhs (stmt
),
1021 gimple_cond_rhs (stmt
));
1023 /* Add new condition into destination's predicate list. */
1024 extract_true_false_edges_from_block (gimple_bb (stmt
),
1025 &true_edge
, &false_edge
);
1027 /* If C is true, then TRUE_EDGE is taken. */
1028 add_to_dst_predicate_list (loop
, true_edge
,
1029 unshare_expr (cond
),
1032 /* If C is false, then FALSE_EDGE is taken. */
1033 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
,
1034 boolean_type_node
, unshare_expr (c
));
1035 add_to_dst_predicate_list (loop
, false_edge
,
1036 unshare_expr (cond
), c2
);
1043 /* Not handled yet in if-conversion. */
1048 /* If current bb has only one successor, then consider it as an
1049 unconditional goto. */
1050 if (single_succ_p (bb
))
1052 basic_block bb_n
= single_succ (bb
);
1054 /* The successor bb inherits the predicate of its
1055 predecessor. If there is no predicate in the predecessor
1056 bb, then consider the successor bb as always executed. */
1057 if (cond
== NULL_TREE
)
1058 cond
= boolean_true_node
;
1060 add_to_predicate_list (bb_n
, cond
);
1064 /* The loop header is always executed. */
1065 reset_bb_predicate (loop
->header
);
1066 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1067 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1072 /* Return true when LOOP is if-convertible. This is a helper function
1073 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1074 in if_convertible_loop_p. */
1077 if_convertible_loop_p_1 (struct loop
*loop
,
1078 vec
<loop_p
> *loop_nest
,
1079 vec
<data_reference_p
> *refs
,
1084 basic_block exit_bb
= NULL
;
1086 /* Don't if-convert the loop when the data dependences cannot be
1087 computed: the loop won't be vectorized in that case. */
1088 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1092 calculate_dominance_info (CDI_DOMINATORS
);
1094 /* Allow statements that can be handled during if-conversion. */
1095 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1099 fprintf (dump_file
, "Irreducible loop\n");
1103 for (i
= 0; i
< loop
->num_nodes
; i
++)
1105 basic_block bb
= ifc_bbs
[i
];
1107 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1110 if (bb_with_exit_edge_p (loop
, bb
))
1114 res
= predicate_bbs (loop
);
1118 if (flag_tree_loop_if_convert_stores
)
1120 data_reference_p dr
;
1122 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1124 dr
->aux
= XNEW (struct ifc_dr
);
1125 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1126 DR_RW_UNCONDITIONALLY (dr
) = -1;
1130 for (i
= 0; i
< loop
->num_nodes
; i
++)
1132 basic_block bb
= ifc_bbs
[i
];
1133 gimple_stmt_iterator itr
;
1135 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1136 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
1139 /* Check the if-convertibility of statements in predicated BBs. */
1140 if (is_predicated (bb
))
1141 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1142 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1147 fprintf (dump_file
, "Applying if-conversion\n");
1152 /* Return true when LOOP is if-convertible.
1153 LOOP is if-convertible if:
1155 - it has two or more basic blocks,
1156 - it has only one exit,
1157 - loop header is not the exit edge,
1158 - if its basic blocks and phi nodes are if convertible. */
1161 if_convertible_loop_p (struct loop
*loop
)
1166 vec
<data_reference_p
> refs
;
1168 vec
<loop_p
> loop_nest
;
1170 /* Handle only innermost loop. */
1171 if (!loop
|| loop
->inner
)
1173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1174 fprintf (dump_file
, "not innermost loop\n");
1178 /* If only one block, no need for if-conversion. */
1179 if (loop
->num_nodes
<= 2)
1181 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1182 fprintf (dump_file
, "less than 2 basic blocks\n");
1186 /* More than one loop exit is too much to handle. */
1187 if (!single_exit (loop
))
1189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1190 fprintf (dump_file
, "multiple exits\n");
1194 /* If one of the loop header's edge is an exit edge then do not
1195 apply if-conversion. */
1196 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1197 if (loop_exit_edge_p (loop
, e
))
1202 loop_nest
.create (3);
1203 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
);
1205 if (flag_tree_loop_if_convert_stores
)
1207 data_reference_p dr
;
1210 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1214 loop_nest
.release ();
1215 free_data_refs (refs
);
1216 free_dependence_relations (ddrs
);
1220 /* Basic block BB has two predecessors. Using predecessor's bb
1221 predicate, set an appropriate condition COND for the PHI node
1222 replacement. Return the true block whose phi arguments are
1223 selected when cond is true. LOOP is the loop containing the
1224 if-converted region, GSI is the place to insert the code for the
1228 find_phi_replacement_condition (basic_block bb
, tree
*cond
,
1229 gimple_stmt_iterator
*gsi
)
1231 edge first_edge
, second_edge
;
1234 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
1235 first_edge
= EDGE_PRED (bb
, 0);
1236 second_edge
= EDGE_PRED (bb
, 1);
1238 /* Prefer an edge with a not negated predicate.
1239 ??? That's a very weak cost model. */
1240 tmp_cond
= bb_predicate (first_edge
->src
);
1241 gcc_assert (tmp_cond
);
1242 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
1246 tmp_edge
= first_edge
;
1247 first_edge
= second_edge
;
1248 second_edge
= tmp_edge
;
1251 /* Check if the edge we take the condition from is not critical.
1252 We know that at least one non-critical edge exists. */
1253 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1255 *cond
= bb_predicate (second_edge
->src
);
1257 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
1258 *cond
= TREE_OPERAND (*cond
, 0);
1260 /* Select non loop header bb. */
1261 first_edge
= second_edge
;
1264 *cond
= bb_predicate (first_edge
->src
);
1266 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1267 *cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (*cond
),
1268 is_gimple_condexpr
, NULL_TREE
,
1269 true, GSI_SAME_STMT
);
1271 return first_edge
->src
;
1274 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1275 This routine does not handle PHI nodes with more than two
1279 S1: A = PHI <x1(1), x2(5)>
1281 S2: A = cond ? x1 : x2;
1283 The generated code is inserted at GSI that points to the top of
1284 basic block's statement list. When COND is true, phi arg from
1285 TRUE_BB is selected. */
1288 predicate_scalar_phi (gimple phi
, tree cond
,
1289 basic_block true_bb
,
1290 gimple_stmt_iterator
*gsi
)
1294 tree rhs
, res
, arg
, scev
;
1296 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1297 && gimple_phi_num_args (phi
) == 2);
1299 res
= gimple_phi_result (phi
);
1300 /* Do not handle virtual phi nodes. */
1301 if (virtual_operand_p (res
))
1304 bb
= gimple_bb (phi
);
1306 if ((arg
= degenerate_phi_result (phi
))
1307 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1309 && !chrec_contains_undetermined (scev
)
1311 && (arg
= gimple_phi_arg_def (phi
, 0))))
1316 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1317 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1319 arg_0
= gimple_phi_arg_def (phi
, 1);
1320 arg_1
= gimple_phi_arg_def (phi
, 0);
1324 arg_0
= gimple_phi_arg_def (phi
, 0);
1325 arg_1
= gimple_phi_arg_def (phi
, 1);
1328 /* Build new RHS using selected condition and arguments. */
1329 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1333 new_stmt
= gimple_build_assign (res
, rhs
);
1334 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
1335 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1336 update_stmt (new_stmt
);
1338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1340 fprintf (dump_file
, "new phi replacement stmt\n");
1341 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1345 /* Replaces in LOOP all the scalar phi nodes other than those in the
1346 LOOP->header block with conditional modify expressions. */
1349 predicate_all_scalar_phis (struct loop
*loop
)
1352 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1355 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1358 tree cond
= NULL_TREE
;
1359 gimple_stmt_iterator gsi
, phi_gsi
;
1360 basic_block true_bb
= NULL
;
1363 if (bb
== loop
->header
)
1366 phi_gsi
= gsi_start_phis (bb
);
1367 if (gsi_end_p (phi_gsi
))
1370 /* BB has two predecessors. Using predecessor's aux field, set
1371 appropriate condition for the PHI node replacement. */
1372 gsi
= gsi_after_labels (bb
);
1373 true_bb
= find_phi_replacement_condition (bb
, &cond
, &gsi
);
1375 while (!gsi_end_p (phi_gsi
))
1377 phi
= gsi_stmt (phi_gsi
);
1378 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1379 release_phi_node (phi
);
1380 gsi_next (&phi_gsi
);
1383 set_phi_nodes (bb
, NULL
);
1387 /* Insert in each basic block of LOOP the statements produced by the
1388 gimplification of the predicates. */
1391 insert_gimplified_predicates (loop_p loop
)
1395 for (i
= 0; i
< loop
->num_nodes
; i
++)
1397 basic_block bb
= ifc_bbs
[i
];
1400 if (!is_predicated (bb
))
1402 /* Do not insert statements for a basic block that is not
1403 predicated. Also make sure that the predicate of the
1404 basic block is set to true. */
1405 reset_bb_predicate (bb
);
1409 stmts
= bb_predicate_gimplified_stmts (bb
);
1412 if (flag_tree_loop_if_convert_stores
)
1414 /* Insert the predicate of the BB just after the label,
1415 as the if-conversion of memory writes will use this
1417 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1418 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1422 /* Insert the predicate of the BB at the end of the BB
1423 as this would reduce the register pressure: the only
1424 use of this predicate will be in successor BBs. */
1425 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1428 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1429 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1431 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1434 /* Once the sequence is code generated, set it to NULL. */
1435 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1440 /* Predicate each write to memory in LOOP.
1442 This function transforms control flow constructs containing memory
1445 | for (i = 0; i < N; i++)
1449 into the following form that does not contain control flow:
1451 | for (i = 0; i < N; i++)
1452 | A[i] = cond ? expr : A[i];
1454 The original CFG looks like this:
1461 | if (i < N) goto bb_5 else goto bb_2
1465 | cond = some_computation;
1466 | if (cond) goto bb_3 else goto bb_4
1478 insert_gimplified_predicates inserts the computation of the COND
1479 expression at the beginning of the destination basic block:
1486 | if (i < N) goto bb_5 else goto bb_2
1490 | cond = some_computation;
1491 | if (cond) goto bb_3 else goto bb_4
1495 | cond = some_computation;
1504 predicate_mem_writes is then predicating the memory write as follows:
1511 | if (i < N) goto bb_5 else goto bb_2
1515 | if (cond) goto bb_3 else goto bb_4
1519 | cond = some_computation;
1520 | A[i] = cond ? expr : A[i];
1528 and finally combine_blocks removes the basic block boundaries making
1529 the loop vectorizable:
1533 | if (i < N) goto bb_5 else goto bb_1
1537 | cond = some_computation;
1538 | A[i] = cond ? expr : A[i];
1539 | if (i < N) goto bb_5 else goto bb_4
1548 predicate_mem_writes (loop_p loop
)
1550 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1552 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1554 gimple_stmt_iterator gsi
;
1555 basic_block bb
= ifc_bbs
[i
];
1556 tree cond
= bb_predicate (bb
);
1560 if (is_true_predicate (cond
))
1564 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1567 cond
= TREE_OPERAND (cond
, 0);
1570 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1571 if ((stmt
= gsi_stmt (gsi
))
1572 && gimple_assign_single_p (stmt
)
1573 && gimple_vdef (stmt
))
1575 tree lhs
= gimple_assign_lhs (stmt
);
1576 tree rhs
= gimple_assign_rhs1 (stmt
);
1577 tree type
= TREE_TYPE (lhs
);
1579 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1580 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1587 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1588 is_gimple_condexpr
, NULL_TREE
,
1589 true, GSI_SAME_STMT
);
1590 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
1591 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1597 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1598 other than the exit and latch of the LOOP. Also resets the
1599 GIMPLE_DEBUG information. */
1602 remove_conditions_and_labels (loop_p loop
)
1604 gimple_stmt_iterator gsi
;
1607 for (i
= 0; i
< loop
->num_nodes
; i
++)
1609 basic_block bb
= ifc_bbs
[i
];
1611 if (bb_with_exit_edge_p (loop
, bb
)
1612 || bb
== loop
->latch
)
1615 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1616 switch (gimple_code (gsi_stmt (gsi
)))
1620 gsi_remove (&gsi
, true);
1624 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1625 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1627 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1628 update_stmt (gsi_stmt (gsi
));
1639 /* Combine all the basic blocks from LOOP into one or two super basic
1640 blocks. Replace PHI nodes with conditional modify expressions. */
1643 combine_blocks (struct loop
*loop
)
1645 basic_block bb
, exit_bb
, merge_target_bb
;
1646 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1651 remove_conditions_and_labels (loop
);
1652 insert_gimplified_predicates (loop
);
1653 predicate_all_scalar_phis (loop
);
1655 if (flag_tree_loop_if_convert_stores
)
1656 predicate_mem_writes (loop
);
1658 /* Merge basic blocks: first remove all the edges in the loop,
1659 except for those from the exit block. */
1661 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1664 free_bb_predicate (bb
);
1665 if (bb_with_exit_edge_p (loop
, bb
))
1667 gcc_assert (exit_bb
== NULL
);
1671 gcc_assert (exit_bb
!= loop
->latch
);
1673 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1677 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
1679 if (e
->src
== exit_bb
)
1686 if (exit_bb
!= NULL
)
1688 if (exit_bb
!= loop
->header
)
1690 /* Connect this node to loop header. */
1691 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
1692 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
1695 /* Redirect non-exit edges to loop->latch. */
1696 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
1698 if (!loop_exit_edge_p (loop
, e
))
1699 redirect_edge_and_branch (e
, loop
->latch
);
1701 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
1705 /* If the loop does not have an exit, reconnect header and latch. */
1706 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
1707 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
1710 merge_target_bb
= loop
->header
;
1711 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1713 gimple_stmt_iterator gsi
;
1714 gimple_stmt_iterator last
;
1718 if (bb
== exit_bb
|| bb
== loop
->latch
)
1721 /* Make stmts member of loop->header. */
1722 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1723 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1725 /* Update stmt list. */
1726 last
= gsi_last_bb (merge_target_bb
);
1727 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1728 set_bb_seq (bb
, NULL
);
1730 delete_basic_block (bb
);
1733 /* If possible, merge loop header to the block with the exit edge.
1734 This reduces the number of basic blocks to two, to please the
1735 vectorizer that handles only loops with two nodes. */
1737 && exit_bb
!= loop
->header
1738 && can_merge_blocks_p (loop
->header
, exit_bb
))
1739 merge_blocks (loop
->header
, exit_bb
);
1745 /* If-convert LOOP when it is legal. For the moment this pass has no
1746 profitability analysis. Returns true when something changed. */
1749 tree_if_conversion (struct loop
*loop
)
1751 bool changed
= false;
1754 if (!if_convertible_loop_p (loop
)
1755 || !dbg_cnt (if_conversion_tree
))
1758 /* Now all statements are if-convertible. Combine all the basic
1759 blocks into one huge basic block doing the if-conversion
1761 combine_blocks (loop
);
1763 if (flag_tree_loop_if_convert_stores
)
1764 mark_virtual_operands_for_renaming (cfun
);
1773 for (i
= 0; i
< loop
->num_nodes
; i
++)
1774 free_bb_predicate (ifc_bbs
[i
]);
1783 /* Tree if-conversion pass management. */
1786 main_tree_if_conversion (void)
1790 bool changed
= false;
1793 if (number_of_loops (cfun
) <= 1)
1796 FOR_EACH_LOOP (li
, loop
, 0)
1797 if (flag_tree_loop_if_convert
== 1
1798 || flag_tree_loop_if_convert_stores
== 1
1799 || flag_tree_loop_vectorize
1800 || loop
->force_vect
)
1801 changed
|= tree_if_conversion (loop
);
1804 todo
|= TODO_cleanup_cfg
;
1806 if (changed
&& flag_tree_loop_if_convert_stores
)
1807 todo
|= TODO_update_ssa_only_virtuals
;
1809 #ifdef ENABLE_CHECKING
1813 gcc_assert (!bb
->aux
);
1820 /* Returns true when the if-conversion pass is enabled. */
1823 gate_tree_if_conversion (void)
1825 return (((flag_tree_loop_vectorize
|| cfun
->has_force_vect_loops
)
1826 && flag_tree_loop_if_convert
!= 0)
1827 || flag_tree_loop_if_convert
== 1
1828 || flag_tree_loop_if_convert_stores
== 1);
1833 const pass_data pass_data_if_conversion
=
1835 GIMPLE_PASS
, /* type */
1837 OPTGROUP_NONE
, /* optinfo_flags */
1838 true, /* has_gate */
1839 true, /* has_execute */
1840 TV_NONE
, /* tv_id */
1841 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1842 0, /* properties_provided */
1843 0, /* properties_destroyed */
1844 0, /* todo_flags_start */
1845 ( TODO_verify_stmts
| TODO_verify_flow
1846 | TODO_verify_ssa
), /* todo_flags_finish */
1849 class pass_if_conversion
: public gimple_opt_pass
1852 pass_if_conversion (gcc::context
*ctxt
)
1853 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
1856 /* opt_pass methods: */
1857 bool gate () { return gate_tree_if_conversion (); }
1858 unsigned int execute () { return main_tree_if_conversion (); }
1860 }; // class pass_if_conversion
1865 make_pass_if_conversion (gcc::context
*ctxt
)
1867 return new pass_if_conversion (ctxt
);