1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 "diagnostic.h"
93 #include "tree-pretty-print.h"
94 #include "gimple-pretty-print.h"
95 #include "tree-flow.h"
96 #include "tree-dump.h"
98 #include "tree-chrec.h"
99 #include "tree-data-ref.h"
100 #include "tree-scalar-evolution.h"
101 #include "tree-pass.h"
103 /* List of basic blocks in if-conversion-suitable order. */
104 static basic_block
*ifc_bbs
;
106 /* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
107 to the new variable. */
110 ifc_temp_var (tree type
, tree exp
)
112 const char *name
= "_ifc_";
116 /* Create new temporary variable. */
117 var
= create_tmp_var (type
, name
);
118 add_referenced_var (var
);
120 /* Build new statement to assign EXP to new variable. */
121 stmt
= gimple_build_assign (var
, exp
);
123 /* Get SSA name for the new variable and set make new statement
124 its definition statement. */
125 new_name
= make_ssa_name (var
, stmt
);
126 gimple_assign_set_lhs (stmt
, new_name
);
127 SSA_NAME_DEF_STMT (new_name
) = stmt
;
133 /* Add condition NEW_COND to the predicate list of basic block BB. */
136 add_to_predicate_list (basic_block bb
, tree new_cond
)
138 tree cond
= (tree
) bb
->aux
;
141 cond
= fold_build2_loc (EXPR_LOCATION (cond
),
142 TRUTH_OR_EXPR
, boolean_type_node
,
143 unshare_expr (cond
), new_cond
);
150 /* Add the condition COND to the previous condition PREV_COND, and add
151 this to the predicate list of the destination of edge E. LOOP is
152 the loop to be if-converted. */
155 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
156 tree prev_cond
, tree cond
)
158 tree new_cond
= NULL_TREE
;
160 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
163 if (prev_cond
== boolean_true_node
|| !prev_cond
)
164 new_cond
= unshare_expr (cond
);
167 /* Add the condition COND to the e->aux field. In case the edge
168 destination is a PHI node, this condition will be added to
169 the block predicate to construct a complete condition. */
172 new_cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
173 unshare_expr (prev_cond
), cond
);
176 add_to_predicate_list (e
->dest
, new_cond
);
180 /* Return true if one of the successor edges of BB exits LOOP. */
183 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
188 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
189 if (loop_exit_edge_p (loop
, e
))
195 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
196 and it belongs to basic block BB.
198 PHI is not if-convertible if:
199 - it has more than 2 arguments,
200 - virtual PHI is immediately used in another PHI node,
201 - virtual PHI on BB other than header. */
204 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
208 fprintf (dump_file
, "-------------------------\n");
209 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
212 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
215 fprintf (dump_file
, "More than two phi node args.\n");
219 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi
))))
221 imm_use_iterator imm_iter
;
224 if (bb
!= loop
->header
)
226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
227 fprintf (dump_file
, "Virtual phi not on loop header.\n");
230 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
232 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
235 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
244 /* Return true when STMT is if-convertible.
246 GIMPLE_ASSIGN statement is not if-convertible if,
249 - LHS is not var decl.
251 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
254 if_convertible_gimple_assign_stmt_p (struct loop
*loop
, basic_block bb
,
257 tree lhs
= gimple_assign_lhs (stmt
);
259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
261 fprintf (dump_file
, "-------------------------\n");
262 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
265 /* Some of these constrains might be too conservative. */
266 if (stmt_ends_bb_p (stmt
)
267 || gimple_has_volatile_ops (stmt
)
268 || (TREE_CODE (lhs
) == SSA_NAME
269 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
270 || gimple_has_side_effects (stmt
))
272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
277 /* See if it needs speculative loading or not. */
278 if (bb
!= loop
->header
279 && gimple_assign_rhs_could_trap_p (stmt
))
281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
282 fprintf (dump_file
, "tree could trap...\n");
286 if (TREE_CODE (lhs
) != SSA_NAME
287 && bb
!= loop
->header
288 && !bb_with_exit_edge_p (loop
, bb
))
290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
292 fprintf (dump_file
, "LHS is not var\n");
293 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
301 /* Return true when STMT is if-convertible.
303 A statement is if-convertible if:
304 - it is an if-convertible GIMPLE_ASSGIN,
305 - it is a GIMPLE_LABEL or a GIMPLE_COND.
307 STMT is inside BB, which is inside loop LOOP. */
310 if_convertible_stmt_p (struct loop
*loop
, basic_block bb
, gimple stmt
)
312 switch (gimple_code (stmt
))
320 return if_convertible_gimple_assign_stmt_p (loop
, bb
, stmt
);
323 /* Don't know what to do with 'em so don't do anything. */
324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
326 fprintf (dump_file
, "don't know what to do\n");
327 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
336 /* Return true when BB is if-convertible. This routine does not check
337 basic block's statements and phis.
339 A basic block is not if-convertible if:
340 - it is non-empty and it is after the exit block (in BFS order),
341 - it is after the exit block but before the latch,
342 - its edges are not normal.
344 EXIT_BB is the basic block containing the exit of the LOOP. BB is
348 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
353 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
354 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
356 if (EDGE_COUNT (bb
->preds
) > 2
357 || EDGE_COUNT (bb
->succs
) > 2)
362 if (bb
!= loop
->latch
)
364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
365 fprintf (dump_file
, "basic block after exit bb but before latch\n");
368 else if (!empty_block_p (bb
))
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
371 fprintf (dump_file
, "non empty basic block after exit bb\n");
374 else if (bb
== loop
->latch
376 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
379 fprintf (dump_file
, "latch is not dominated by exit_block\n");
384 /* Be less adventurous and handle only normal edges. */
385 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
387 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
390 fprintf (dump_file
, "Difficult to handle edges\n");
397 /* Return true when all predecessor blocks of BB are visited. The
398 VISITED bitmap keeps track of the visited blocks. */
401 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
405 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
406 if (!bitmap_bit_p (*visited
, e
->src
->index
))
412 /* Get body of a LOOP in suitable order for if-conversion. It is
413 caller's responsibility to deallocate basic block list.
414 If-conversion suitable order is, breadth first sort (BFS) order
415 with an additional constraint: select a block only if all its
416 predecessors are already selected. */
419 get_loop_body_in_if_conv_order (const struct loop
*loop
)
421 basic_block
*blocks
, *blocks_in_bfs_order
;
424 unsigned int index
= 0;
425 unsigned int visited_count
= 0;
427 gcc_assert (loop
->num_nodes
);
428 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
430 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
431 visited
= BITMAP_ALLOC (NULL
);
433 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
436 while (index
< loop
->num_nodes
)
438 bb
= blocks_in_bfs_order
[index
];
440 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
442 free (blocks_in_bfs_order
);
443 BITMAP_FREE (visited
);
448 if (!bitmap_bit_p (visited
, bb
->index
))
450 if (pred_blocks_visited_p (bb
, &visited
)
451 || bb
== loop
->header
)
453 /* This block is now visited. */
454 bitmap_set_bit (visited
, bb
->index
);
455 blocks
[visited_count
++] = bb
;
461 if (index
== loop
->num_nodes
462 && visited_count
!= loop
->num_nodes
)
466 free (blocks_in_bfs_order
);
467 BITMAP_FREE (visited
);
471 /* Returns true when the analysis of the predicates for all the basic
472 blocks in LOOP succeeded.
474 predicate_bbs first clears the ->aux fields of the edges and basic
475 blocks. These fields are then initialized with the tree
476 expressions representing the predicates under which a basic block
477 is executed in the LOOP. As the loop->header is executed at each
478 iteration, it has the "true" predicate. Other statements executed
479 under a condition are predicated with that condition, for example
486 S1 will be predicated with "x", and S2 will be predicated with
490 predicate_bbs (loop_p loop
)
494 for (i
= 0; i
< loop
->num_nodes
; i
++)
498 basic_block bb
= ifc_bbs
[i
];
499 gimple_stmt_iterator itr
= gsi_start_phis (bb
);
501 if (!gsi_end_p (itr
))
502 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
508 for (i
= 0; i
< loop
->num_nodes
; i
++)
510 basic_block bb
= ifc_bbs
[i
];
511 tree cond
= (tree
) bb
->aux
;
512 gimple_stmt_iterator itr
;
514 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
516 gimple stmt
= gsi_stmt (itr
);
518 switch (gimple_code (stmt
))
526 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
527 if (gimple_debug_bind_p (gsi_stmt (itr
)))
529 gimple_debug_bind_reset_value (gsi_stmt (itr
));
530 update_stmt (gsi_stmt (itr
));
537 edge true_edge
, false_edge
;
538 location_t loc
= gimple_location (stmt
);
539 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
541 gimple_cond_lhs (stmt
),
542 gimple_cond_rhs (stmt
));
544 extract_true_false_edges_from_block (gimple_bb (stmt
),
545 &true_edge
, &false_edge
);
547 /* Add new condition into destination's predicate list. */
549 /* If C is true, then TRUE_EDGE is taken. */
550 add_to_dst_predicate_list (loop
, true_edge
, cond
, c
);
552 /* If C is false, then FALSE_EDGE is taken. */
553 c2
= invert_truthvalue_loc (loc
, unshare_expr (c
));
554 add_to_dst_predicate_list (loop
, false_edge
, cond
, c2
);
561 /* Not handled yet in if-conversion. */
569 /* If current bb has only one successor, then consider it as an
570 unconditional goto. */
571 if (single_succ_p (bb
))
573 basic_block bb_n
= single_succ (bb
);
575 /* The successor bb inherits the predicate of its
576 predecessor. If there is no predicate in the predecessor
577 bb, then consider the successor bb as always executed. */
578 if (cond
== NULL_TREE
)
579 cond
= boolean_true_node
;
581 add_to_predicate_list (bb_n
, cond
);
585 /* The loop header is always executed. */
586 loop
->header
->aux
= boolean_true_node
;
591 /* Return true when LOOP is if-convertible.
592 LOOP is if-convertible if:
594 - it has two or more basic blocks,
595 - it has only one exit,
596 - loop header is not the exit edge,
597 - if its basic blocks and phi nodes are if convertible. */
600 if_convertible_loop_p (struct loop
*loop
)
605 basic_block exit_bb
= NULL
;
607 /* Handle only innermost loop. */
608 if (!loop
|| loop
->inner
)
610 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
611 fprintf (dump_file
, "not innermost loop\n");
615 /* If only one block, no need for if-conversion. */
616 if (loop
->num_nodes
<= 2)
618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
619 fprintf (dump_file
, "less than 2 basic blocks\n");
623 /* More than one loop exit is too much to handle. */
624 if (!single_exit (loop
))
626 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
627 fprintf (dump_file
, "multiple exits\n");
631 /* ??? Check target's vector conditional operation support for vectorizer. */
633 /* If one of the loop header's edge is exit edge then do not apply
635 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
637 if (loop_exit_edge_p (loop
, e
))
641 /* Don't if-convert the loop when the data dependences cannot be
642 computed: the loop won't be vectorized in that case. */
644 VEC (data_reference_p
, heap
) *refs
= VEC_alloc (data_reference_p
, heap
, 5);
645 VEC (ddr_p
, heap
) *ddrs
= VEC_alloc (ddr_p
, heap
, 25);
646 bool res
= compute_data_dependences_for_loop (loop
, true, &refs
, &ddrs
);
648 free_data_refs (refs
);
649 free_dependence_relations (ddrs
);
655 calculate_dominance_info (CDI_DOMINATORS
);
657 /* Allow statements that can be handled during if-conversion. */
658 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
662 fprintf (dump_file
, "Irreducible loop\n");
666 for (i
= 0; i
< loop
->num_nodes
; i
++)
668 basic_block bb
= ifc_bbs
[i
];
670 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
673 if (bb_with_exit_edge_p (loop
, bb
))
677 if (!predicate_bbs (loop
))
680 for (i
= 0; i
< loop
->num_nodes
; i
++)
682 basic_block bb
= ifc_bbs
[i
];
683 gimple_stmt_iterator itr
;
685 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
686 if (!if_convertible_stmt_p (loop
, bb
, gsi_stmt (itr
)))
689 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
690 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
695 fprintf (dump_file
, "Applying if-conversion\n");
700 /* During if-conversion, the bb->aux field is used to hold a predicate
701 list. This function cleans for all the basic blocks in the given
702 LOOP their predicate list. It also cleans up the e->aux field of
703 all the successor edges: e->aux is used to hold the true and false
704 conditions for conditional expressions. */
707 clean_predicate_lists (struct loop
*loop
)
714 bb
= get_loop_body (loop
);
715 for (i
= 0; i
< loop
->num_nodes
; i
++)
718 FOR_EACH_EDGE (e
, ei
, bb
[i
]->succs
)
724 /* Basic block BB has two predecessors. Using predecessor's bb->aux
725 field, set appropriate condition COND for the PHI node replacement.
726 Return true block whose phi arguments are selected when cond is
727 true. LOOP is the loop containing the if-converted region, GSI is
728 the place to insert the code for the if-conversion. */
731 find_phi_replacement_condition (struct loop
*loop
,
732 basic_block bb
, tree
*cond
,
733 gimple_stmt_iterator
*gsi
)
735 edge first_edge
, second_edge
;
738 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
739 first_edge
= EDGE_PRED (bb
, 0);
740 second_edge
= EDGE_PRED (bb
, 1);
742 /* Use condition based on following criteria:
748 S2 is preferred over S1. Make 'b' first_bb and use its condition.
750 2) Do not make loop header first_bb.
753 S1: x = !(c == d)? a : b;
758 S3: x = (c == d) ? b : a;
760 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
763 4) If pred B is dominated by pred A then use pred B's condition.
766 /* Select condition that is not TRUTH_NOT_EXPR. */
767 tmp_cond
= (tree
) (first_edge
->src
)->aux
;
768 gcc_assert (tmp_cond
);
770 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
774 tmp_edge
= first_edge
;
775 first_edge
= second_edge
;
776 second_edge
= tmp_edge
;
779 /* Check if FIRST_BB is loop header or not and make sure that
780 FIRST_BB does not dominate SECOND_BB. */
781 if (first_edge
->src
== loop
->header
782 || dominated_by_p (CDI_DOMINATORS
,
783 second_edge
->src
, first_edge
->src
))
785 *cond
= (tree
) (second_edge
->src
)->aux
;
787 /* If there is a condition on an incoming edge, add it to the
788 incoming bb predicate. */
789 if (second_edge
->aux
)
790 *cond
= build2 (TRUTH_AND_EXPR
, boolean_type_node
,
791 *cond
, (tree
) second_edge
->aux
);
793 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
794 *cond
= invert_truthvalue (*cond
);
796 /* Select non loop header bb. */
797 first_edge
= second_edge
;
801 *cond
= (tree
) (first_edge
->src
)->aux
;
803 /* If there is a condition on an incoming edge, add it to the
804 incoming bb predicate. */
806 *cond
= build2 (TRUTH_AND_EXPR
, boolean_type_node
,
807 *cond
, (tree
) first_edge
->aux
);
810 /* Gimplify the condition: the vectorizer prefers to have gimple
811 values as conditions. Various targets use different means to
812 communicate conditions in vector compare operations. Using a
813 gimple value allows the compiler to emit vector compare and
814 select RTL without exposing compare's result. */
815 *cond
= force_gimple_operand_gsi (gsi
, unshare_expr (*cond
),
817 true, GSI_SAME_STMT
);
818 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
822 new_stmt
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
));
823 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
824 *cond
= gimple_assign_lhs (new_stmt
);
829 return first_edge
->src
;
832 /* Replace PHI node with conditional modify expr using COND. This
833 routine does not handle PHI nodes with more than two arguments.
836 S1: A = PHI <x1(1), x2(5)
838 S2: A = cond ? x1 : x2;
840 The generated code is inserted at GSI that points to the top of
841 basic block's statement list. When COND is true, phi arg from
842 TRUE_BB is selected. */
845 replace_phi_with_cond_gimple_assign_stmt (gimple phi
, tree cond
,
847 gimple_stmt_iterator
*gsi
)
854 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
855 && gimple_phi_num_args (phi
) == 2);
857 bb
= gimple_bb (phi
);
859 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
860 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
862 arg_0
= gimple_phi_arg_def (phi
, 1);
863 arg_1
= gimple_phi_arg_def (phi
, 0);
867 arg_0
= gimple_phi_arg_def (phi
, 0);
868 arg_1
= gimple_phi_arg_def (phi
, 1);
871 /* Build new RHS using selected condition and arguments. */
872 rhs
= build3 (COND_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
873 unshare_expr (cond
), unshare_expr (arg_0
),
874 unshare_expr (arg_1
));
876 new_stmt
= gimple_build_assign (unshare_expr (PHI_RESULT (phi
)), rhs
);
877 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
878 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
879 update_stmt (new_stmt
);
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 fprintf (dump_file
, "new phi replacement stmt\n");
884 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
888 /* Process phi nodes for the given LOOP. Replace phi nodes with
889 conditional modify expressions. */
892 process_phi_nodes (struct loop
*loop
)
895 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
898 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
901 tree cond
= NULL_TREE
;
902 gimple_stmt_iterator gsi
, phi_gsi
;
903 basic_block true_bb
= NULL
;
906 if (bb
== loop
->header
)
909 phi_gsi
= gsi_start_phis (bb
);
910 gsi
= gsi_after_labels (bb
);
912 /* BB has two predecessors. Using predecessor's aux field, set
913 appropriate condition for the PHI node replacement. */
914 if (!gsi_end_p (phi_gsi
))
915 true_bb
= find_phi_replacement_condition (loop
, bb
, &cond
, &gsi
);
917 while (!gsi_end_p (phi_gsi
))
919 phi
= gsi_stmt (phi_gsi
);
920 replace_phi_with_cond_gimple_assign_stmt (phi
, cond
, true_bb
, &gsi
);
921 release_phi_node (phi
);
924 set_phi_nodes (bb
, NULL
);
928 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
929 other than the exit and latch of the LOOP. */
932 remove_conditions_and_labels (loop_p loop
)
934 gimple_stmt_iterator gsi
;
937 for (i
= 0; i
< loop
->num_nodes
; i
++)
939 basic_block bb
= ifc_bbs
[i
];
941 if (bb_with_exit_edge_p (loop
, bb
)
942 || bb
== loop
->latch
)
945 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
946 if (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
947 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
)
948 gsi_remove (&gsi
, true);
954 /* Combine all the basic blocks from LOOP into one or two super basic
955 blocks. Replace PHI nodes with conditional modify expressions. */
958 combine_blocks (struct loop
*loop
)
960 basic_block bb
, exit_bb
, merge_target_bb
;
961 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
966 remove_conditions_and_labels (loop
);
968 /* Process phi nodes to prepare blocks for merge. */
969 process_phi_nodes (loop
);
971 /* Merge basic blocks: first remove all the edges in the loop,
972 except for those from the exit block. */
974 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
977 if (bb_with_exit_edge_p (loop
, bb
))
983 gcc_assert (exit_bb
!= loop
->latch
);
985 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
989 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
991 if (e
->src
== exit_bb
)
1000 if (exit_bb
!= loop
->header
)
1002 /* Connect this node to loop header. */
1003 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
1004 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
1007 /* Redirect non-exit edges to loop->latch. */
1008 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
1010 if (!loop_exit_edge_p (loop
, e
))
1011 redirect_edge_and_branch (e
, loop
->latch
);
1013 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
1017 /* If the loop does not have an exit, reconnect header and latch. */
1018 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
1019 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
1022 merge_target_bb
= loop
->header
;
1023 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1025 gimple_stmt_iterator gsi
;
1026 gimple_stmt_iterator last
;
1030 if (bb
== exit_bb
|| bb
== loop
->latch
)
1033 /* Make stmts member of loop->header. */
1034 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1035 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1037 /* Update stmt list. */
1038 last
= gsi_last_bb (merge_target_bb
);
1039 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1040 set_bb_seq (bb
, NULL
);
1042 delete_basic_block (bb
);
1045 /* If possible, merge loop header to the block with the exit edge.
1046 This reduces the number of basic blocks to two, to please the
1047 vectorizer that handles only loops with two nodes.
1049 FIXME: Call cleanup_tree_cfg. */
1051 && exit_bb
!= loop
->header
1052 && can_merge_blocks_p (loop
->header
, exit_bb
))
1053 merge_blocks (loop
->header
, exit_bb
);
1056 /* If-convert LOOP when it is legal. For the moment this pass has no
1057 profitability analysis. */
1060 tree_if_conversion (struct loop
*loop
)
1064 if (!if_convertible_loop_p (loop
))
1067 /* Now all statements are if-convertible. Combine all the basic
1068 blocks into one huge basic block doing the if-conversion
1070 combine_blocks (loop
);
1073 clean_predicate_lists (loop
);
1081 /* Tree if-conversion pass management. */
1084 main_tree_if_conversion (void)
1089 if (number_of_loops () <= 1)
1092 FOR_EACH_LOOP (li
, loop
, 0)
1093 tree_if_conversion (loop
);
1099 gate_tree_if_conversion (void)
1101 return flag_tree_vectorize
!= 0;
1104 struct gimple_opt_pass pass_if_conversion
=
1109 gate_tree_if_conversion
, /* gate */
1110 main_tree_if_conversion
, /* execute */
1113 0, /* static_pass_number */
1114 TV_NONE
, /* tv_id */
1115 PROP_cfg
| PROP_ssa
, /* properties_required */
1116 0, /* properties_provided */
1117 0, /* properties_destroyed */
1118 0, /* todo_flags_start */
1119 TODO_dump_func
| TODO_verify_stmts
| TODO_verify_flow
1120 /* todo_flags_finish */