1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Devang Patel <dpatel@apple.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass implements a tree level if-conversion of loops. Its
23 initial goal is to help the vectorizer to vectorize loops with
26 A short description of if-conversion:
28 o Decide if a loop is if-convertible or not.
29 o Walk all loop basic blocks in breadth first order (BFS order).
30 o Remove conditional statements (at the end of basic block)
31 and propagate condition into destination basic blocks'
33 o Replace modify expression with conditional modify expression
34 using current basic block's condition.
35 o Merge all basic blocks
36 o Replace phi nodes with conditional modify expr
37 o Merge all basic blocks into header
39 Sample transformation:
44 # i_23 = PHI <0(0), i_18(10)>;
47 if (j_15 > 41) goto <L1>; else goto <L17>;
54 # iftmp.2_4 = PHI <0(8), 42(2)>;
58 if (i_18 <= 15) goto <L19>; else goto <L18>;
68 # i_23 = PHI <0(0), i_18(10)>;
73 iftmp.2_4 = j_15 > 41 ? 42 : 0;
76 if (i_18 <= 15) goto <L19>; else goto <L18>;
86 #include "coretypes.h"
91 #include "basic-block.h"
92 #include "tree-pretty-print.h"
93 #include "gimple-pretty-print.h"
94 #include "tree-flow.h"
95 #include "tree-dump.h"
97 #include "tree-chrec.h"
98 #include "tree-data-ref.h"
99 #include "tree-scalar-evolution.h"
100 #include "tree-pass.h"
103 /* List of basic blocks in if-conversion-suitable order. */
104 static basic_block
*ifc_bbs
;
106 /* Structure used to predicate basic blocks. This is attached to the
107 ->aux field of the BBs in the loop to be if-converted. */
108 typedef struct bb_predicate_s
{
110 /* The condition under which this basic block is executed. */
113 /* PREDICATE is gimplified, and the sequence of statements is
114 recorded here, in order to avoid the duplication of computations
115 that occur in previous conditions. See PR44483. */
116 gimple_seq predicate_gimplified_stmts
;
119 /* Returns true when the basic block BB has a predicate. */
122 bb_has_predicate (basic_block bb
)
124 return bb
->aux
!= NULL
;
127 /* Returns the gimplified predicate for basic block BB. */
130 bb_predicate (basic_block bb
)
132 return ((bb_predicate_p
) bb
->aux
)->predicate
;
135 /* Sets the gimplified predicate COND for basic block BB. */
138 set_bb_predicate (basic_block bb
, tree cond
)
140 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
143 /* Returns the sequence of statements of the gimplification of the
144 predicate for basic block BB. */
146 static inline gimple_seq
147 bb_predicate_gimplified_stmts (basic_block bb
)
149 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
152 /* Sets the sequence of statements STMTS of the gimplification of the
153 predicate for basic block BB. */
156 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
158 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
161 /* Adds the sequence of statements STMTS to the sequence of statements
162 of the predicate for basic block BB. */
165 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
168 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
171 /* Initializes to TRUE the predicate of basic block BB. */
174 init_bb_predicate (basic_block bb
)
176 bb
->aux
= XNEW (struct bb_predicate_s
);
177 set_bb_predicate_gimplified_stmts (bb
, NULL
);
178 set_bb_predicate (bb
, boolean_true_node
);
181 /* Free the predicate of basic block BB. */
184 free_bb_predicate (basic_block bb
)
188 if (!bb_has_predicate (bb
))
191 /* Release the SSA_NAMEs created for the gimplification of the
193 stmts
= bb_predicate_gimplified_stmts (bb
);
196 gimple_stmt_iterator i
;
198 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
199 free_stmt_operands (gsi_stmt (i
));
206 /* Free the predicate of BB and reinitialize it with the true
210 reset_bb_predicate (basic_block bb
)
212 free_bb_predicate (bb
);
213 init_bb_predicate (bb
);
216 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
217 the expression EXPR. Inserts the statement created for this
218 computation before GSI and leaves the iterator GSI at the same
222 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
224 const char *name
= "_ifc_";
228 /* Create new temporary variable. */
229 var
= create_tmp_var (type
, name
);
230 add_referenced_var (var
);
232 /* Build new statement to assign EXPR to new variable. */
233 stmt
= gimple_build_assign (var
, expr
);
235 /* Get SSA name for the new variable and set make new statement
236 its definition statement. */
237 new_name
= make_ssa_name (var
, stmt
);
238 gimple_assign_set_lhs (stmt
, new_name
);
239 SSA_NAME_DEF_STMT (new_name
) = stmt
;
242 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
243 return gimple_assign_lhs (stmt
);
246 /* Return true when COND is a true predicate. */
249 is_true_predicate (tree cond
)
251 return (cond
== NULL_TREE
252 || cond
== boolean_true_node
253 || integer_onep (cond
));
256 /* Returns true when BB has a predicate that is not trivial: true or
260 is_predicated (basic_block bb
)
262 return !is_true_predicate (bb_predicate (bb
));
265 /* Parses the predicate COND and returns its comparison code and
266 operands OP0 and OP1. */
268 static enum tree_code
269 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
273 if (TREE_CODE (cond
) == SSA_NAME
274 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
276 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
278 *op0
= gimple_assign_rhs1 (s
);
279 *op1
= gimple_assign_rhs2 (s
);
280 return gimple_assign_rhs_code (s
);
283 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
285 tree op
= gimple_assign_rhs1 (s
);
286 tree type
= TREE_TYPE (op
);
287 enum tree_code code
= parse_predicate (op
, op0
, op1
);
289 return code
== ERROR_MARK
? ERROR_MARK
290 : invert_tree_comparison (code
, HONOR_NANS (TYPE_MODE (type
)));
296 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
)
298 *op0
= TREE_OPERAND (cond
, 0);
299 *op1
= TREE_OPERAND (cond
, 1);
300 return TREE_CODE (cond
);
306 /* Returns the fold of predicate C1 OR C2 at location LOC. */
309 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
311 tree op1a
, op1b
, op2a
, op2b
;
312 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
313 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
315 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
317 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
323 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
326 /* Add condition NC to the predicate list of basic block BB. */
329 add_to_predicate_list (basic_block bb
, tree nc
)
333 if (is_true_predicate (nc
))
336 if (!is_predicated (bb
))
340 bc
= bb_predicate (bb
);
341 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
344 if (!is_gimple_condexpr (bc
))
347 bc
= force_gimple_operand (bc
, &stmts
, true, NULL_TREE
);
348 add_bb_predicate_gimplified_stmts (bb
, stmts
);
351 if (is_true_predicate (bc
))
352 reset_bb_predicate (bb
);
354 set_bb_predicate (bb
, bc
);
357 /* Add the condition COND to the previous condition PREV_COND, and add
358 this to the predicate list of the destination of edge E. LOOP is
359 the loop to be if-converted. */
362 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
363 tree prev_cond
, tree cond
)
365 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
368 if (!is_true_predicate (prev_cond
))
369 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
372 add_to_predicate_list (e
->dest
, cond
);
375 /* Return true if one of the successor edges of BB exits LOOP. */
378 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
383 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
384 if (loop_exit_edge_p (loop
, e
))
390 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
391 and it belongs to basic block BB.
393 PHI is not if-convertible if:
394 - it has more than 2 arguments.
396 When the flag_tree_loop_if_convert_stores is not set, PHI is not
398 - a virtual PHI is immediately used in another PHI node,
399 - there is a virtual PHI in a BB other than the loop->header. */
402 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
406 fprintf (dump_file
, "-------------------------\n");
407 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
410 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
412 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
413 fprintf (dump_file
, "More than two phi node args.\n");
417 if (flag_tree_loop_if_convert_stores
)
420 /* When the flag_tree_loop_if_convert_stores is not set, check
421 that there are no memory writes in the branches of the loop to be
423 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi
))))
425 imm_use_iterator imm_iter
;
428 if (bb
!= loop
->header
)
430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
431 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
435 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
437 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
440 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
449 /* Records the status of a data reference. This struct is attached to
450 each DR->aux field. */
453 /* -1 when not initialized, 0 when false, 1 when true. */
454 int written_at_least_once
;
456 /* -1 when not initialized, 0 when false, 1 when true. */
457 int rw_unconditionally
;
460 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
461 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
462 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
464 /* Returns true when the memory references of STMT are read or written
465 unconditionally. In other words, this function returns true when
466 for every data reference A in STMT there exist other accesses to
467 a data reference with the same base with predicates that add up (OR-up) to
468 the true predicate: this ensures that the data reference A is touched
469 (read or written) on every iteration of the if-converted loop. */
472 memrefs_read_or_written_unconditionally (gimple stmt
,
473 VEC (data_reference_p
, heap
) *drs
)
476 data_reference_p a
, b
;
477 tree ca
= bb_predicate (gimple_bb (stmt
));
479 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, a
); i
++)
480 if (DR_STMT (a
) == stmt
)
483 int x
= DR_RW_UNCONDITIONALLY (a
);
491 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, b
); j
++)
493 tree ref_base_a
= DR_REF (a
);
494 tree ref_base_b
= DR_REF (b
);
496 if (DR_STMT (b
) == stmt
)
499 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
500 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
501 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
502 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
504 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
505 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
506 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
507 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
509 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
511 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
513 if (DR_RW_UNCONDITIONALLY (b
) == 1
514 || is_true_predicate (cb
)
515 || is_true_predicate (ca
516 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
518 DR_RW_UNCONDITIONALLY (a
) = 1;
519 DR_RW_UNCONDITIONALLY (b
) = 1;
528 DR_RW_UNCONDITIONALLY (a
) = 0;
536 /* Returns true when the memory references of STMT are unconditionally
537 written. In other words, this function returns true when for every
538 data reference A written in STMT, there exist other writes to the
539 same data reference with predicates that add up (OR-up) to the true
540 predicate: this ensures that the data reference A is written on
541 every iteration of the if-converted loop. */
544 write_memrefs_written_at_least_once (gimple stmt
,
545 VEC (data_reference_p
, heap
) *drs
)
548 data_reference_p a
, b
;
549 tree ca
= bb_predicate (gimple_bb (stmt
));
551 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, a
); i
++)
552 if (DR_STMT (a
) == stmt
556 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
564 for (j
= 0; VEC_iterate (data_reference_p
, drs
, j
, b
); j
++)
565 if (DR_STMT (b
) != stmt
567 && same_data_refs_base_objects (a
, b
))
569 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
571 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
572 || is_true_predicate (cb
)
573 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
576 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
577 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
585 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
593 /* Return true when the memory references of STMT won't trap in the
594 if-converted code. There are two things that we have to check for:
596 - writes to memory occur to writable memory: if-conversion of
597 memory writes transforms the conditional memory writes into
598 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
599 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
600 be executed at all in the original code, it may be a readonly
601 memory. To check that A is not const-qualified, we check that
602 there exists at least an unconditional write to A in the current
605 - reads or writes to memory are valid memory accesses for every
606 iteration. To check that the memory accesses are correctly formed
607 and that we are allowed to read and write in these locations, we
608 check that the memory accesses to be if-converted occur at every
609 iteration unconditionally. */
612 ifcvt_memrefs_wont_trap (gimple stmt
, VEC (data_reference_p
, heap
) *refs
)
614 return write_memrefs_written_at_least_once (stmt
, refs
)
615 && memrefs_read_or_written_unconditionally (stmt
, refs
);
618 /* Wrapper around gimple_could_trap_p refined for the needs of the
619 if-conversion. Try to prove that the memory accesses of STMT could
620 not trap in the innermost loop containing STMT. */
623 ifcvt_could_trap_p (gimple stmt
, VEC (data_reference_p
, heap
) *refs
)
625 if (gimple_vuse (stmt
)
626 && !gimple_could_trap_p_1 (stmt
, false, false)
627 && ifcvt_memrefs_wont_trap (stmt
, refs
))
630 return gimple_could_trap_p (stmt
);
633 /* Return true when STMT is if-convertible.
635 GIMPLE_ASSIGN statement is not if-convertible if,
638 - LHS is not var decl. */
641 if_convertible_gimple_assign_stmt_p (gimple stmt
,
642 VEC (data_reference_p
, heap
) *refs
)
644 tree lhs
= gimple_assign_lhs (stmt
);
647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
649 fprintf (dump_file
, "-------------------------\n");
650 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
653 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
656 /* Some of these constrains might be too conservative. */
657 if (stmt_ends_bb_p (stmt
)
658 || gimple_has_volatile_ops (stmt
)
659 || (TREE_CODE (lhs
) == SSA_NAME
660 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
661 || gimple_has_side_effects (stmt
))
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
664 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
668 if (flag_tree_loop_if_convert_stores
)
670 if (ifcvt_could_trap_p (stmt
, refs
))
672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
673 fprintf (dump_file
, "tree could trap...\n");
679 if (gimple_assign_rhs_could_trap_p (stmt
))
681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
682 fprintf (dump_file
, "tree could trap...\n");
686 bb
= gimple_bb (stmt
);
688 if (TREE_CODE (lhs
) != SSA_NAME
689 && bb
!= bb
->loop_father
->header
690 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
694 fprintf (dump_file
, "LHS is not var\n");
695 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
703 /* Return true when STMT is if-convertible.
705 A statement is if-convertible if:
706 - it is an if-convertible GIMPLE_ASSGIN,
707 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
710 if_convertible_stmt_p (gimple stmt
, VEC (data_reference_p
, heap
) *refs
)
712 switch (gimple_code (stmt
))
720 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
724 tree fndecl
= gimple_call_fndecl (stmt
);
727 int flags
= gimple_call_flags (stmt
);
728 if ((flags
& ECF_CONST
)
729 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
730 /* We can only vectorize some builtins at the moment,
731 so restrict if-conversion to those. */
732 && DECL_BUILT_IN (fndecl
))
739 /* Don't know what to do with 'em so don't do anything. */
740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
742 fprintf (dump_file
, "don't know what to do\n");
743 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
752 /* Return true when BB post-dominates all its predecessors. */
755 bb_postdominates_preds (basic_block bb
)
759 for (i
= 0; i
< EDGE_COUNT (bb
->preds
); i
++)
760 if (!dominated_by_p (CDI_POST_DOMINATORS
, EDGE_PRED (bb
, i
)->src
, bb
))
766 /* Return true when BB is if-convertible. This routine does not check
767 basic block's statements and phis.
769 A basic block is not if-convertible if:
770 - it is non-empty and it is after the exit block (in BFS order),
771 - it is after the exit block but before the latch,
772 - its edges are not normal.
774 EXIT_BB is the basic block containing the exit of the LOOP. BB is
778 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
783 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
784 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
786 if (EDGE_COUNT (bb
->preds
) > 2
787 || EDGE_COUNT (bb
->succs
) > 2)
792 if (bb
!= loop
->latch
)
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 fprintf (dump_file
, "basic block after exit bb but before latch\n");
798 else if (!empty_block_p (bb
))
800 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
801 fprintf (dump_file
, "non empty basic block after exit bb\n");
804 else if (bb
== loop
->latch
806 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
809 fprintf (dump_file
, "latch is not dominated by exit_block\n");
814 /* Be less adventurous and handle only normal edges. */
815 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
817 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
819 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
820 fprintf (dump_file
, "Difficult to handle edges\n");
824 if (EDGE_COUNT (bb
->preds
) == 2
825 && bb
!= loop
->header
826 && !bb_postdominates_preds (bb
))
832 /* Return true when all predecessor blocks of BB are visited. The
833 VISITED bitmap keeps track of the visited blocks. */
836 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
840 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
841 if (!bitmap_bit_p (*visited
, e
->src
->index
))
847 /* Get body of a LOOP in suitable order for if-conversion. It is
848 caller's responsibility to deallocate basic block list.
849 If-conversion suitable order is, breadth first sort (BFS) order
850 with an additional constraint: select a block only if all its
851 predecessors are already selected. */
854 get_loop_body_in_if_conv_order (const struct loop
*loop
)
856 basic_block
*blocks
, *blocks_in_bfs_order
;
859 unsigned int index
= 0;
860 unsigned int visited_count
= 0;
862 gcc_assert (loop
->num_nodes
);
863 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
865 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
866 visited
= BITMAP_ALLOC (NULL
);
868 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
871 while (index
< loop
->num_nodes
)
873 bb
= blocks_in_bfs_order
[index
];
875 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
877 free (blocks_in_bfs_order
);
878 BITMAP_FREE (visited
);
883 if (!bitmap_bit_p (visited
, bb
->index
))
885 if (pred_blocks_visited_p (bb
, &visited
)
886 || bb
== loop
->header
)
888 /* This block is now visited. */
889 bitmap_set_bit (visited
, bb
->index
);
890 blocks
[visited_count
++] = bb
;
896 if (index
== loop
->num_nodes
897 && visited_count
!= loop
->num_nodes
)
901 free (blocks_in_bfs_order
);
902 BITMAP_FREE (visited
);
906 /* Returns true when the analysis of the predicates for all the basic
907 blocks in LOOP succeeded.
909 predicate_bbs first allocates the predicates of the basic blocks.
910 These fields are then initialized with the tree expressions
911 representing the predicates under which a basic block is executed
912 in the LOOP. As the loop->header is executed at each iteration, it
913 has the "true" predicate. Other statements executed under a
914 condition are predicated with that condition, for example
921 S1 will be predicated with "x", and
922 S2 will be predicated with "!x". */
925 predicate_bbs (loop_p loop
)
929 for (i
= 0; i
< loop
->num_nodes
; i
++)
930 init_bb_predicate (ifc_bbs
[i
]);
932 for (i
= 0; i
< loop
->num_nodes
; i
++)
934 basic_block bb
= ifc_bbs
[i
];
936 gimple_stmt_iterator itr
;
938 /* The loop latch is always executed and has no extra conditions
939 to be processed: skip it. */
940 if (bb
== loop
->latch
)
942 reset_bb_predicate (loop
->latch
);
946 cond
= bb_predicate (bb
);
948 && bb
!= loop
->header
)
952 cond
= force_gimple_operand (cond
, &stmts
, true, NULL_TREE
);
953 add_bb_predicate_gimplified_stmts (bb
, stmts
);
956 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
958 gimple stmt
= gsi_stmt (itr
);
960 switch (gimple_code (stmt
))
971 edge true_edge
, false_edge
;
972 location_t loc
= gimple_location (stmt
);
973 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
975 gimple_cond_lhs (stmt
),
976 gimple_cond_rhs (stmt
));
978 /* Add new condition into destination's predicate list. */
979 extract_true_false_edges_from_block (gimple_bb (stmt
),
980 &true_edge
, &false_edge
);
982 /* If C is true, then TRUE_EDGE is taken. */
983 add_to_dst_predicate_list (loop
, true_edge
, cond
, unshare_expr (c
));
985 /* If C is false, then FALSE_EDGE is taken. */
986 c2
= invert_truthvalue_loc (loc
, unshare_expr (c
));
987 tem
= canonicalize_cond_expr_cond (c2
);
990 add_to_dst_predicate_list (loop
, false_edge
, cond
, c2
);
997 /* Not handled yet in if-conversion. */
1002 /* If current bb has only one successor, then consider it as an
1003 unconditional goto. */
1004 if (single_succ_p (bb
))
1006 basic_block bb_n
= single_succ (bb
);
1008 /* The successor bb inherits the predicate of its
1009 predecessor. If there is no predicate in the predecessor
1010 bb, then consider the successor bb as always executed. */
1011 if (cond
== NULL_TREE
)
1012 cond
= boolean_true_node
;
1014 add_to_predicate_list (bb_n
, cond
);
1018 /* The loop header is always executed. */
1019 reset_bb_predicate (loop
->header
);
1020 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1021 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1026 /* Return true when LOOP is if-convertible. This is a helper function
1027 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1028 in if_convertible_loop_p. */
1031 if_convertible_loop_p_1 (struct loop
*loop
,
1032 VEC (loop_p
, heap
) **loop_nest
,
1033 VEC (data_reference_p
, heap
) **refs
,
1034 VEC (ddr_p
, heap
) **ddrs
)
1038 basic_block exit_bb
= NULL
;
1040 /* Don't if-convert the loop when the data dependences cannot be
1041 computed: the loop won't be vectorized in that case. */
1042 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1046 calculate_dominance_info (CDI_DOMINATORS
);
1047 calculate_dominance_info (CDI_POST_DOMINATORS
);
1049 /* Allow statements that can be handled during if-conversion. */
1050 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1054 fprintf (dump_file
, "Irreducible loop\n");
1058 for (i
= 0; i
< loop
->num_nodes
; i
++)
1060 basic_block bb
= ifc_bbs
[i
];
1062 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1065 if (bb_with_exit_edge_p (loop
, bb
))
1069 res
= predicate_bbs (loop
);
1073 if (flag_tree_loop_if_convert_stores
)
1075 data_reference_p dr
;
1077 for (i
= 0; VEC_iterate (data_reference_p
, *refs
, i
, dr
); i
++)
1079 dr
->aux
= XNEW (struct ifc_dr
);
1080 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1081 DR_RW_UNCONDITIONALLY (dr
) = -1;
1085 for (i
= 0; i
< loop
->num_nodes
; i
++)
1087 basic_block bb
= ifc_bbs
[i
];
1088 gimple_stmt_iterator itr
;
1090 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1091 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
1094 /* Check the if-convertibility of statements in predicated BBs. */
1095 if (is_predicated (bb
))
1096 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1097 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1102 fprintf (dump_file
, "Applying if-conversion\n");
1107 /* Return true when LOOP is if-convertible.
1108 LOOP is if-convertible if:
1110 - it has two or more basic blocks,
1111 - it has only one exit,
1112 - loop header is not the exit edge,
1113 - if its basic blocks and phi nodes are if convertible. */
1116 if_convertible_loop_p (struct loop
*loop
)
1121 VEC (data_reference_p
, heap
) *refs
;
1122 VEC (ddr_p
, heap
) *ddrs
;
1123 VEC (loop_p
, heap
) *loop_nest
;
1125 /* Handle only innermost loop. */
1126 if (!loop
|| loop
->inner
)
1128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1129 fprintf (dump_file
, "not innermost loop\n");
1133 /* If only one block, no need for if-conversion. */
1134 if (loop
->num_nodes
<= 2)
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1137 fprintf (dump_file
, "less than 2 basic blocks\n");
1141 /* More than one loop exit is too much to handle. */
1142 if (!single_exit (loop
))
1144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1145 fprintf (dump_file
, "multiple exits\n");
1149 /* If one of the loop header's edge is an exit edge then do not
1150 apply if-conversion. */
1151 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1152 if (loop_exit_edge_p (loop
, e
))
1155 refs
= VEC_alloc (data_reference_p
, heap
, 5);
1156 ddrs
= VEC_alloc (ddr_p
, heap
, 25);
1157 loop_nest
= VEC_alloc (loop_p
, heap
, 3);
1158 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
);
1160 if (flag_tree_loop_if_convert_stores
)
1162 data_reference_p dr
;
1165 for (i
= 0; VEC_iterate (data_reference_p
, refs
, i
, dr
); i
++)
1169 VEC_free (loop_p
, heap
, loop_nest
);
1170 free_data_refs (refs
);
1171 free_dependence_relations (ddrs
);
1175 /* Basic block BB has two predecessors. Using predecessor's bb
1176 predicate, set an appropriate condition COND for the PHI node
1177 replacement. Return the true block whose phi arguments are
1178 selected when cond is true. LOOP is the loop containing the
1179 if-converted region, GSI is the place to insert the code for the
1183 find_phi_replacement_condition (struct loop
*loop
,
1184 basic_block bb
, tree
*cond
,
1185 gimple_stmt_iterator
*gsi
)
1187 edge first_edge
, second_edge
;
1190 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
1191 first_edge
= EDGE_PRED (bb
, 0);
1192 second_edge
= EDGE_PRED (bb
, 1);
1194 /* Use condition based on following criteria:
1200 S2 is preferred over S1. Make 'b' first_bb and use its condition.
1202 2) Do not make loop header first_bb.
1205 S1: x = !(c == d)? a : b;
1208 S22: x = t1 ? b : a;
1210 S3: x = (c == d) ? b : a;
1212 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
1215 4) If pred B is dominated by pred A then use pred B's condition.
1218 /* Select condition that is not TRUTH_NOT_EXPR. */
1219 tmp_cond
= bb_predicate (first_edge
->src
);
1220 gcc_assert (tmp_cond
);
1222 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
1226 tmp_edge
= first_edge
;
1227 first_edge
= second_edge
;
1228 second_edge
= tmp_edge
;
1231 /* Check if FIRST_BB is loop header or not and make sure that
1232 FIRST_BB does not dominate SECOND_BB. */
1233 if (first_edge
->src
== loop
->header
1234 || dominated_by_p (CDI_DOMINATORS
,
1235 second_edge
->src
, first_edge
->src
))
1237 *cond
= bb_predicate (second_edge
->src
);
1239 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
1240 *cond
= invert_truthvalue (*cond
);
1242 /* Select non loop header bb. */
1243 first_edge
= second_edge
;
1246 *cond
= bb_predicate (first_edge
->src
);
1248 /* Gimplify the condition: the vectorizer prefers to have gimple
1249 values as conditions. Various targets use different means to
1250 communicate conditions in vector compare operations. Using a
1251 gimple value allows the compiler to emit vector compare and
1252 select RTL without exposing compare's result. */
1253 *cond
= force_gimple_operand_gsi (gsi
, unshare_expr (*cond
),
1255 true, GSI_SAME_STMT
);
1256 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
1257 *cond
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
), gsi
);
1261 return first_edge
->src
;
1264 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1265 This routine does not handle PHI nodes with more than two
1269 S1: A = PHI <x1(1), x2(5)
1271 S2: A = cond ? x1 : x2;
1273 The generated code is inserted at GSI that points to the top of
1274 basic block's statement list. When COND is true, phi arg from
1275 TRUE_BB is selected. */
1278 predicate_scalar_phi (gimple phi
, tree cond
,
1279 basic_block true_bb
,
1280 gimple_stmt_iterator
*gsi
)
1284 tree rhs
, res
, arg
, scev
;
1286 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1287 && gimple_phi_num_args (phi
) == 2);
1289 res
= gimple_phi_result (phi
);
1290 /* Do not handle virtual phi nodes. */
1291 if (!is_gimple_reg (SSA_NAME_VAR (res
)))
1294 bb
= gimple_bb (phi
);
1296 if ((arg
= degenerate_phi_result (phi
))
1297 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1299 && !chrec_contains_undetermined (scev
)
1301 && (arg
= gimple_phi_arg_def (phi
, 0))))
1306 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1307 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1309 arg_0
= gimple_phi_arg_def (phi
, 1);
1310 arg_1
= gimple_phi_arg_def (phi
, 0);
1314 arg_0
= gimple_phi_arg_def (phi
, 0);
1315 arg_1
= gimple_phi_arg_def (phi
, 1);
1318 gcc_checking_assert (bb
== bb
->loop_father
->header
1319 || bb_postdominates_preds (bb
));
1321 /* Build new RHS using selected condition and arguments. */
1322 rhs
= build3 (COND_EXPR
, TREE_TYPE (res
),
1323 unshare_expr (cond
), arg_0
, arg_1
);
1326 new_stmt
= gimple_build_assign (res
, rhs
);
1327 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
1328 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1329 update_stmt (new_stmt
);
1331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1333 fprintf (dump_file
, "new phi replacement stmt\n");
1334 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1338 /* Replaces in LOOP all the scalar phi nodes other than those in the
1339 LOOP->header block with conditional modify expressions. */
1342 predicate_all_scalar_phis (struct loop
*loop
)
1345 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1348 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1351 tree cond
= NULL_TREE
;
1352 gimple_stmt_iterator gsi
, phi_gsi
;
1353 basic_block true_bb
= NULL
;
1356 if (bb
== loop
->header
)
1359 phi_gsi
= gsi_start_phis (bb
);
1360 if (gsi_end_p (phi_gsi
))
1363 /* BB has two predecessors. Using predecessor's aux field, set
1364 appropriate condition for the PHI node replacement. */
1365 gsi
= gsi_after_labels (bb
);
1366 true_bb
= find_phi_replacement_condition (loop
, bb
, &cond
, &gsi
);
1368 while (!gsi_end_p (phi_gsi
))
1370 phi
= gsi_stmt (phi_gsi
);
1371 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1372 release_phi_node (phi
);
1373 gsi_next (&phi_gsi
);
1376 set_phi_nodes (bb
, NULL
);
1380 /* Insert in each basic block of LOOP the statements produced by the
1381 gimplification of the predicates. */
1384 insert_gimplified_predicates (loop_p loop
)
1388 for (i
= 0; i
< loop
->num_nodes
; i
++)
1390 basic_block bb
= ifc_bbs
[i
];
1393 if (!is_predicated (bb
))
1395 /* Do not insert statements for a basic block that is not
1396 predicated. Also make sure that the predicate of the
1397 basic block is set to true. */
1398 reset_bb_predicate (bb
);
1402 stmts
= bb_predicate_gimplified_stmts (bb
);
1405 if (flag_tree_loop_if_convert_stores
)
1407 /* Insert the predicate of the BB just after the label,
1408 as the if-conversion of memory writes will use this
1410 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1411 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1415 /* Insert the predicate of the BB at the end of the BB
1416 as this would reduce the register pressure: the only
1417 use of this predicate will be in successor BBs. */
1418 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1421 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1422 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1424 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1427 /* Once the sequence is code generated, set it to NULL. */
1428 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1433 /* Predicate each write to memory in LOOP.
1435 This function transforms control flow constructs containing memory
1438 | for (i = 0; i < N; i++)
1442 into the following form that does not contain control flow:
1444 | for (i = 0; i < N; i++)
1445 | A[i] = cond ? expr : A[i];
1447 The original CFG looks like this:
1454 | if (i < N) goto bb_5 else goto bb_2
1458 | cond = some_computation;
1459 | if (cond) goto bb_3 else goto bb_4
1471 insert_gimplified_predicates inserts the computation of the COND
1472 expression at the beginning of the destination basic block:
1479 | if (i < N) goto bb_5 else goto bb_2
1483 | cond = some_computation;
1484 | if (cond) goto bb_3 else goto bb_4
1488 | cond = some_computation;
1497 predicate_mem_writes is then predicating the memory write as follows:
1504 | if (i < N) goto bb_5 else goto bb_2
1508 | if (cond) goto bb_3 else goto bb_4
1512 | cond = some_computation;
1513 | A[i] = cond ? expr : A[i];
1521 and finally combine_blocks removes the basic block boundaries making
1522 the loop vectorizable:
1526 | if (i < N) goto bb_5 else goto bb_1
1530 | cond = some_computation;
1531 | A[i] = cond ? expr : A[i];
1532 | if (i < N) goto bb_5 else goto bb_4
1541 predicate_mem_writes (loop_p loop
)
1543 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1545 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1547 gimple_stmt_iterator gsi
;
1548 basic_block bb
= ifc_bbs
[i
];
1549 tree cond
= bb_predicate (bb
);
1552 if (is_true_predicate (cond
))
1555 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1556 if ((stmt
= gsi_stmt (gsi
))
1557 && gimple_assign_single_p (stmt
)
1558 && gimple_vdef (stmt
))
1560 tree lhs
= gimple_assign_lhs (stmt
);
1561 tree rhs
= gimple_assign_rhs1 (stmt
);
1562 tree type
= TREE_TYPE (lhs
);
1564 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1565 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1566 rhs
= build3 (COND_EXPR
, type
, unshare_expr (cond
), rhs
, lhs
);
1567 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1573 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1574 other than the exit and latch of the LOOP. Also resets the
1575 GIMPLE_DEBUG information. */
1578 remove_conditions_and_labels (loop_p loop
)
1580 gimple_stmt_iterator gsi
;
1583 for (i
= 0; i
< loop
->num_nodes
; i
++)
1585 basic_block bb
= ifc_bbs
[i
];
1587 if (bb_with_exit_edge_p (loop
, bb
)
1588 || bb
== loop
->latch
)
1591 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1592 switch (gimple_code (gsi_stmt (gsi
)))
1596 gsi_remove (&gsi
, true);
1600 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1601 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1603 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1604 update_stmt (gsi_stmt (gsi
));
1615 /* Combine all the basic blocks from LOOP into one or two super basic
1616 blocks. Replace PHI nodes with conditional modify expressions. */
1619 combine_blocks (struct loop
*loop
)
1621 basic_block bb
, exit_bb
, merge_target_bb
;
1622 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1627 remove_conditions_and_labels (loop
);
1628 insert_gimplified_predicates (loop
);
1629 predicate_all_scalar_phis (loop
);
1631 if (flag_tree_loop_if_convert_stores
)
1632 predicate_mem_writes (loop
);
1634 /* Merge basic blocks: first remove all the edges in the loop,
1635 except for those from the exit block. */
1637 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1640 free_bb_predicate (bb
);
1641 if (bb_with_exit_edge_p (loop
, bb
))
1647 gcc_assert (exit_bb
!= loop
->latch
);
1649 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1653 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
1655 if (e
->src
== exit_bb
)
1662 if (exit_bb
!= NULL
)
1664 if (exit_bb
!= loop
->header
)
1666 /* Connect this node to loop header. */
1667 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
1668 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
1671 /* Redirect non-exit edges to loop->latch. */
1672 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
1674 if (!loop_exit_edge_p (loop
, e
))
1675 redirect_edge_and_branch (e
, loop
->latch
);
1677 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
1681 /* If the loop does not have an exit, reconnect header and latch. */
1682 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
1683 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
1686 merge_target_bb
= loop
->header
;
1687 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1689 gimple_stmt_iterator gsi
;
1690 gimple_stmt_iterator last
;
1694 if (bb
== exit_bb
|| bb
== loop
->latch
)
1697 /* Make stmts member of loop->header. */
1698 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1699 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1701 /* Update stmt list. */
1702 last
= gsi_last_bb (merge_target_bb
);
1703 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1704 set_bb_seq (bb
, NULL
);
1706 delete_basic_block (bb
);
1709 /* If possible, merge loop header to the block with the exit edge.
1710 This reduces the number of basic blocks to two, to please the
1711 vectorizer that handles only loops with two nodes. */
1713 && exit_bb
!= loop
->header
1714 && can_merge_blocks_p (loop
->header
, exit_bb
))
1715 merge_blocks (loop
->header
, exit_bb
);
1721 /* If-convert LOOP when it is legal. For the moment this pass has no
1722 profitability analysis. Returns true when something changed. */
1725 tree_if_conversion (struct loop
*loop
)
1727 bool changed
= false;
1730 if (!if_convertible_loop_p (loop
)
1731 || !dbg_cnt (if_conversion_tree
))
1734 /* Now all statements are if-convertible. Combine all the basic
1735 blocks into one huge basic block doing the if-conversion
1737 combine_blocks (loop
);
1739 if (flag_tree_loop_if_convert_stores
)
1740 mark_sym_for_renaming (gimple_vop (cfun
));
1749 for (i
= 0; i
< loop
->num_nodes
; i
++)
1750 free_bb_predicate (ifc_bbs
[i
]);
1759 /* Tree if-conversion pass management. */
1762 main_tree_if_conversion (void)
1766 bool changed
= false;
1769 if (number_of_loops () <= 1)
1772 FOR_EACH_LOOP (li
, loop
, 0)
1773 changed
|= tree_if_conversion (loop
);
1776 todo
|= TODO_cleanup_cfg
;
1778 if (changed
&& flag_tree_loop_if_convert_stores
)
1779 todo
|= TODO_update_ssa_only_virtuals
;
1781 free_dominance_info (CDI_POST_DOMINATORS
);
1786 /* Returns true when the if-conversion pass is enabled. */
1789 gate_tree_if_conversion (void)
1791 return ((flag_tree_vectorize
&& flag_tree_loop_if_convert
!= 0)
1792 || flag_tree_loop_if_convert
== 1
1793 || flag_tree_loop_if_convert_stores
== 1);
1796 struct gimple_opt_pass pass_if_conversion
=
1801 gate_tree_if_conversion
, /* gate */
1802 main_tree_if_conversion
, /* execute */
1805 0, /* static_pass_number */
1806 TV_NONE
, /* tv_id */
1807 PROP_cfg
| PROP_ssa
, /* properties_required */
1808 0, /* properties_provided */
1809 0, /* properties_destroyed */
1810 0, /* todo_flags_start */
1811 TODO_dump_func
| TODO_verify_stmts
| TODO_verify_flow
1812 /* todo_flags_finish */