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 /* Return true when COND is a true predicate. */
136 is_true_predicate (tree cond
)
138 return (cond
== NULL_TREE
139 || cond
== boolean_true_node
140 || integer_onep (cond
));
143 /* Returns true when BB has a predicate that is not trivial: true or
147 is_predicated (basic_block bb
)
149 return !is_true_predicate ((tree
) bb
->aux
);
152 /* Add condition NEW_COND to the predicate list of basic block BB. */
155 add_to_predicate_list (basic_block bb
, tree new_cond
)
157 tree cond
= (tree
) bb
->aux
;
159 bb
->aux
= is_true_predicate (cond
) ? new_cond
:
160 fold_build2_loc (EXPR_LOCATION (cond
),
161 TRUTH_OR_EXPR
, boolean_type_node
,
165 /* Add the condition COND to the previous condition PREV_COND, and add
166 this to the predicate list of the destination of edge E. LOOP is
167 the loop to be if-converted. */
170 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
171 tree prev_cond
, tree cond
)
173 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
176 if (!is_true_predicate (prev_cond
))
177 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
180 add_to_predicate_list (e
->dest
, cond
);
183 /* Return true if one of the successor edges of BB exits LOOP. */
186 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
191 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
192 if (loop_exit_edge_p (loop
, e
))
198 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
199 and it belongs to basic block BB.
201 PHI is not if-convertible if:
202 - it has more than 2 arguments,
203 - virtual PHI is immediately used in another PHI node,
204 - virtual PHI on BB other than header. */
207 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
211 fprintf (dump_file
, "-------------------------\n");
212 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
215 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
218 fprintf (dump_file
, "More than two phi node args.\n");
222 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi
))))
224 imm_use_iterator imm_iter
;
227 if (bb
!= loop
->header
)
229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
230 fprintf (dump_file
, "Virtual phi not on loop header.\n");
233 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
235 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
238 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
247 /* Return true when STMT is if-convertible.
249 GIMPLE_ASSIGN statement is not if-convertible if,
252 - LHS is not var decl.
254 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
257 if_convertible_gimple_assign_stmt_p (struct loop
*loop
, basic_block bb
,
260 tree lhs
= gimple_assign_lhs (stmt
);
262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
264 fprintf (dump_file
, "-------------------------\n");
265 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
268 /* Some of these constrains might be too conservative. */
269 if (stmt_ends_bb_p (stmt
)
270 || gimple_has_volatile_ops (stmt
)
271 || (TREE_CODE (lhs
) == SSA_NAME
272 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
273 || gimple_has_side_effects (stmt
))
275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
276 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
280 if (gimple_assign_rhs_could_trap_p (stmt
))
282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
283 fprintf (dump_file
, "tree could trap...\n");
287 if (TREE_CODE (lhs
) != SSA_NAME
288 && bb
!= loop
->header
289 && !bb_with_exit_edge_p (loop
, bb
))
291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
293 fprintf (dump_file
, "LHS is not var\n");
294 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
302 /* Return true when STMT is if-convertible.
304 A statement is if-convertible if:
305 - it is an if-convertible GIMPLE_ASSGIN,
306 - it is a GIMPLE_LABEL or a GIMPLE_COND.
308 STMT is inside BB, which is inside loop LOOP. */
311 if_convertible_stmt_p (struct loop
*loop
, basic_block bb
, gimple stmt
)
313 switch (gimple_code (stmt
))
321 return if_convertible_gimple_assign_stmt_p (loop
, bb
, stmt
);
324 /* Don't know what to do with 'em so don't do anything. */
325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
327 fprintf (dump_file
, "don't know what to do\n");
328 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
337 /* Return true when BB is if-convertible. This routine does not check
338 basic block's statements and phis.
340 A basic block is not if-convertible if:
341 - it is non-empty and it is after the exit block (in BFS order),
342 - it is after the exit block but before the latch,
343 - its edges are not normal.
345 EXIT_BB is the basic block containing the exit of the LOOP. BB is
349 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
355 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
357 if (EDGE_COUNT (bb
->preds
) > 2
358 || EDGE_COUNT (bb
->succs
) > 2)
363 if (bb
!= loop
->latch
)
365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
366 fprintf (dump_file
, "basic block after exit bb but before latch\n");
369 else if (!empty_block_p (bb
))
371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "non empty basic block after exit bb\n");
375 else if (bb
== loop
->latch
377 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
379 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
380 fprintf (dump_file
, "latch is not dominated by exit_block\n");
385 /* Be less adventurous and handle only normal edges. */
386 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
388 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
391 fprintf (dump_file
, "Difficult to handle edges\n");
398 /* Return true when all predecessor blocks of BB are visited. The
399 VISITED bitmap keeps track of the visited blocks. */
402 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
406 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
407 if (!bitmap_bit_p (*visited
, e
->src
->index
))
413 /* Get body of a LOOP in suitable order for if-conversion. It is
414 caller's responsibility to deallocate basic block list.
415 If-conversion suitable order is, breadth first sort (BFS) order
416 with an additional constraint: select a block only if all its
417 predecessors are already selected. */
420 get_loop_body_in_if_conv_order (const struct loop
*loop
)
422 basic_block
*blocks
, *blocks_in_bfs_order
;
425 unsigned int index
= 0;
426 unsigned int visited_count
= 0;
428 gcc_assert (loop
->num_nodes
);
429 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
431 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
432 visited
= BITMAP_ALLOC (NULL
);
434 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
437 while (index
< loop
->num_nodes
)
439 bb
= blocks_in_bfs_order
[index
];
441 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
443 free (blocks_in_bfs_order
);
444 BITMAP_FREE (visited
);
449 if (!bitmap_bit_p (visited
, bb
->index
))
451 if (pred_blocks_visited_p (bb
, &visited
)
452 || bb
== loop
->header
)
454 /* This block is now visited. */
455 bitmap_set_bit (visited
, bb
->index
);
456 blocks
[visited_count
++] = bb
;
462 if (index
== loop
->num_nodes
463 && visited_count
!= loop
->num_nodes
)
467 free (blocks_in_bfs_order
);
468 BITMAP_FREE (visited
);
472 /* Returns true when the analysis of the predicates for all the basic
473 blocks in LOOP succeeded.
475 predicate_bbs first clears the ->aux fields of the basic blocks.
476 These fields are then initialized with the tree expressions
477 representing the predicates under which a basic block is executed
478 in the LOOP. As the loop->header is executed at each iteration, it
479 has the "true" predicate. Other statements executed under a
480 condition are predicated with that condition, for example
487 S1 will be predicated with "x", and S2 will be predicated with
491 predicate_bbs (loop_p loop
)
495 for (i
= 0; i
< loop
->num_nodes
; i
++)
496 ifc_bbs
[i
]->aux
= NULL
;
498 for (i
= 0; i
< loop
->num_nodes
; i
++)
500 basic_block bb
= ifc_bbs
[i
];
501 tree cond
= (tree
) bb
->aux
;
502 gimple_stmt_iterator itr
;
504 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
506 gimple stmt
= gsi_stmt (itr
);
508 switch (gimple_code (stmt
))
516 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
517 if (gimple_debug_bind_p (gsi_stmt (itr
)))
519 gimple_debug_bind_reset_value (gsi_stmt (itr
));
520 update_stmt (gsi_stmt (itr
));
527 edge true_edge
, false_edge
;
528 location_t loc
= gimple_location (stmt
);
529 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
531 gimple_cond_lhs (stmt
),
532 gimple_cond_rhs (stmt
));
534 extract_true_false_edges_from_block (gimple_bb (stmt
),
535 &true_edge
, &false_edge
);
537 /* Add new condition into destination's predicate list. */
539 /* If C is true, then TRUE_EDGE is taken. */
540 add_to_dst_predicate_list (loop
, true_edge
, cond
, c
);
542 /* If C is false, then FALSE_EDGE is taken. */
543 c2
= invert_truthvalue_loc (loc
, unshare_expr (c
));
544 add_to_dst_predicate_list (loop
, false_edge
, cond
, c2
);
551 /* Not handled yet in if-conversion. */
559 /* If current bb has only one successor, then consider it as an
560 unconditional goto. */
561 if (single_succ_p (bb
))
563 basic_block bb_n
= single_succ (bb
);
565 /* The successor bb inherits the predicate of its
566 predecessor. If there is no predicate in the predecessor
567 bb, then consider the successor bb as always executed. */
568 if (cond
== NULL_TREE
)
569 cond
= boolean_true_node
;
571 add_to_predicate_list (bb_n
, cond
);
575 /* The loop header is always executed. */
576 loop
->header
->aux
= boolean_true_node
;
581 /* Return true when LOOP is if-convertible.
582 LOOP is if-convertible if:
584 - it has two or more basic blocks,
585 - it has only one exit,
586 - loop header is not the exit edge,
587 - if its basic blocks and phi nodes are if convertible. */
590 if_convertible_loop_p (struct loop
*loop
)
595 basic_block exit_bb
= NULL
;
597 /* Handle only innermost loop. */
598 if (!loop
|| loop
->inner
)
600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
601 fprintf (dump_file
, "not innermost loop\n");
605 /* If only one block, no need for if-conversion. */
606 if (loop
->num_nodes
<= 2)
608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
609 fprintf (dump_file
, "less than 2 basic blocks\n");
613 /* More than one loop exit is too much to handle. */
614 if (!single_exit (loop
))
616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
617 fprintf (dump_file
, "multiple exits\n");
621 /* ??? Check target's vector conditional operation support for vectorizer. */
623 /* If one of the loop header's edge is exit edge then do not apply
625 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
627 if (loop_exit_edge_p (loop
, e
))
631 /* Don't if-convert the loop when the data dependences cannot be
632 computed: the loop won't be vectorized in that case. */
634 VEC (data_reference_p
, heap
) *refs
= VEC_alloc (data_reference_p
, heap
, 5);
635 VEC (ddr_p
, heap
) *ddrs
= VEC_alloc (ddr_p
, heap
, 25);
636 bool res
= compute_data_dependences_for_loop (loop
, true, &refs
, &ddrs
);
638 free_data_refs (refs
);
639 free_dependence_relations (ddrs
);
645 calculate_dominance_info (CDI_DOMINATORS
);
647 /* Allow statements that can be handled during if-conversion. */
648 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
652 fprintf (dump_file
, "Irreducible loop\n");
656 for (i
= 0; i
< loop
->num_nodes
; i
++)
658 basic_block bb
= ifc_bbs
[i
];
660 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
663 if (bb_with_exit_edge_p (loop
, bb
))
667 if (!predicate_bbs (loop
))
670 for (i
= 0; i
< loop
->num_nodes
; i
++)
672 basic_block bb
= ifc_bbs
[i
];
673 gimple_stmt_iterator itr
;
675 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
676 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
679 /* For non predicated BBs, don't check their statements. */
680 if (!is_predicated (bb
))
683 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
684 if (!if_convertible_stmt_p (loop
, bb
, gsi_stmt (itr
)))
689 fprintf (dump_file
, "Applying if-conversion\n");
694 /* During if-conversion, the bb->aux field is used to hold a predicate
695 list. This function cleans for all the basic blocks in the given
696 LOOP their predicate list. */
699 clean_predicate_lists (struct loop
*loop
)
702 basic_block
*bbs
= get_loop_body (loop
);
704 for (i
= 0; i
< loop
->num_nodes
; i
++)
710 /* Basic block BB has two predecessors. Using predecessor's bb->aux
711 field, set appropriate condition COND for the PHI node replacement.
712 Return true block whose phi arguments are selected when cond is
713 true. LOOP is the loop containing the if-converted region, GSI is
714 the place to insert the code for the if-conversion. */
717 find_phi_replacement_condition (struct loop
*loop
,
718 basic_block bb
, tree
*cond
,
719 gimple_stmt_iterator
*gsi
)
721 edge first_edge
, second_edge
;
724 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
725 first_edge
= EDGE_PRED (bb
, 0);
726 second_edge
= EDGE_PRED (bb
, 1);
728 /* Use condition based on following criteria:
734 S2 is preferred over S1. Make 'b' first_bb and use its condition.
736 2) Do not make loop header first_bb.
739 S1: x = !(c == d)? a : b;
744 S3: x = (c == d) ? b : a;
746 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
749 4) If pred B is dominated by pred A then use pred B's condition.
752 /* Select condition that is not TRUTH_NOT_EXPR. */
753 tmp_cond
= (tree
) (first_edge
->src
)->aux
;
754 gcc_assert (tmp_cond
);
756 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
760 tmp_edge
= first_edge
;
761 first_edge
= second_edge
;
762 second_edge
= tmp_edge
;
765 /* Check if FIRST_BB is loop header or not and make sure that
766 FIRST_BB does not dominate SECOND_BB. */
767 if (first_edge
->src
== loop
->header
768 || dominated_by_p (CDI_DOMINATORS
,
769 second_edge
->src
, first_edge
->src
))
771 *cond
= (tree
) (second_edge
->src
)->aux
;
773 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
774 *cond
= invert_truthvalue (*cond
);
776 /* Select non loop header bb. */
777 first_edge
= second_edge
;
780 *cond
= (tree
) (first_edge
->src
)->aux
;
782 /* Gimplify the condition: the vectorizer prefers to have gimple
783 values as conditions. Various targets use different means to
784 communicate conditions in vector compare operations. Using a
785 gimple value allows the compiler to emit vector compare and
786 select RTL without exposing compare's result. */
787 *cond
= force_gimple_operand_gsi (gsi
, unshare_expr (*cond
),
789 true, GSI_SAME_STMT
);
790 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
794 new_stmt
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
));
795 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
796 *cond
= gimple_assign_lhs (new_stmt
);
801 return first_edge
->src
;
804 /* Replace PHI node with conditional modify expr using COND. This
805 routine does not handle PHI nodes with more than two arguments.
808 S1: A = PHI <x1(1), x2(5)
810 S2: A = cond ? x1 : x2;
812 The generated code is inserted at GSI that points to the top of
813 basic block's statement list. When COND is true, phi arg from
814 TRUE_BB is selected. */
817 replace_phi_with_cond_gimple_assign_stmt (gimple phi
, tree cond
,
819 gimple_stmt_iterator
*gsi
)
826 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
827 && gimple_phi_num_args (phi
) == 2);
829 bb
= gimple_bb (phi
);
831 arg
= degenerate_phi_result (phi
);
837 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
838 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
840 arg_0
= gimple_phi_arg_def (phi
, 1);
841 arg_1
= gimple_phi_arg_def (phi
, 0);
845 arg_0
= gimple_phi_arg_def (phi
, 0);
846 arg_1
= gimple_phi_arg_def (phi
, 1);
849 /* Build new RHS using selected condition and arguments. */
850 rhs
= build3 (COND_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
851 unshare_expr (cond
), arg_0
, arg_1
);
854 new_stmt
= gimple_build_assign (PHI_RESULT (phi
), rhs
);
855 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
856 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
857 update_stmt (new_stmt
);
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
861 fprintf (dump_file
, "new phi replacement stmt\n");
862 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
866 /* Process phi nodes for the given LOOP. Replace phi nodes with
867 conditional modify expressions. */
870 process_phi_nodes (struct loop
*loop
)
873 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
876 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
879 tree cond
= NULL_TREE
;
880 gimple_stmt_iterator gsi
, phi_gsi
;
881 basic_block true_bb
= NULL
;
884 if (bb
== loop
->header
)
887 phi_gsi
= gsi_start_phis (bb
);
888 gsi
= gsi_after_labels (bb
);
890 /* BB has two predecessors. Using predecessor's aux field, set
891 appropriate condition for the PHI node replacement. */
892 if (!gsi_end_p (phi_gsi
))
893 true_bb
= find_phi_replacement_condition (loop
, bb
, &cond
, &gsi
);
895 while (!gsi_end_p (phi_gsi
))
897 phi
= gsi_stmt (phi_gsi
);
898 replace_phi_with_cond_gimple_assign_stmt (phi
, cond
, true_bb
, &gsi
);
899 release_phi_node (phi
);
902 set_phi_nodes (bb
, NULL
);
906 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
907 other than the exit and latch of the LOOP. */
910 remove_conditions_and_labels (loop_p loop
)
912 gimple_stmt_iterator gsi
;
915 for (i
= 0; i
< loop
->num_nodes
; i
++)
917 basic_block bb
= ifc_bbs
[i
];
919 if (bb_with_exit_edge_p (loop
, bb
)
920 || bb
== loop
->latch
)
923 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
924 if (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
925 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
)
926 gsi_remove (&gsi
, true);
932 /* Combine all the basic blocks from LOOP into one or two super basic
933 blocks. Replace PHI nodes with conditional modify expressions. */
936 combine_blocks (struct loop
*loop
)
938 basic_block bb
, exit_bb
, merge_target_bb
;
939 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
944 remove_conditions_and_labels (loop
);
946 /* Process phi nodes to prepare blocks for merge. */
947 process_phi_nodes (loop
);
949 /* Merge basic blocks: first remove all the edges in the loop,
950 except for those from the exit block. */
952 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
955 if (bb_with_exit_edge_p (loop
, bb
))
961 gcc_assert (exit_bb
!= loop
->latch
);
963 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
967 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
969 if (e
->src
== exit_bb
)
978 if (exit_bb
!= loop
->header
)
980 /* Connect this node to loop header. */
981 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
982 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
985 /* Redirect non-exit edges to loop->latch. */
986 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
988 if (!loop_exit_edge_p (loop
, e
))
989 redirect_edge_and_branch (e
, loop
->latch
);
991 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
995 /* If the loop does not have an exit, reconnect header and latch. */
996 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
997 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
1000 merge_target_bb
= loop
->header
;
1001 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1003 gimple_stmt_iterator gsi
;
1004 gimple_stmt_iterator last
;
1008 if (bb
== exit_bb
|| bb
== loop
->latch
)
1011 /* Make stmts member of loop->header. */
1012 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1013 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1015 /* Update stmt list. */
1016 last
= gsi_last_bb (merge_target_bb
);
1017 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1018 set_bb_seq (bb
, NULL
);
1020 delete_basic_block (bb
);
1023 /* If possible, merge loop header to the block with the exit edge.
1024 This reduces the number of basic blocks to two, to please the
1025 vectorizer that handles only loops with two nodes.
1027 FIXME: Call cleanup_tree_cfg. */
1029 && exit_bb
!= loop
->header
1030 && can_merge_blocks_p (loop
->header
, exit_bb
))
1031 merge_blocks (loop
->header
, exit_bb
);
1034 /* If-convert LOOP when it is legal. For the moment this pass has no
1035 profitability analysis. */
1038 tree_if_conversion (struct loop
*loop
)
1042 if (!if_convertible_loop_p (loop
))
1045 /* Now all statements are if-convertible. Combine all the basic
1046 blocks into one huge basic block doing the if-conversion
1048 combine_blocks (loop
);
1051 clean_predicate_lists (loop
);
1059 /* Tree if-conversion pass management. */
1062 main_tree_if_conversion (void)
1067 if (number_of_loops () <= 1)
1070 FOR_EACH_LOOP (li
, loop
, 0)
1071 tree_if_conversion (loop
);
1077 gate_tree_if_conversion (void)
1079 return flag_tree_vectorize
!= 0;
1082 struct gimple_opt_pass pass_if_conversion
=
1087 gate_tree_if_conversion
, /* gate */
1088 main_tree_if_conversion
, /* execute */
1091 0, /* static_pass_number */
1092 TV_NONE
, /* tv_id */
1093 PROP_cfg
| PROP_ssa
, /* properties_required */
1094 0, /* properties_provided */
1095 0, /* properties_destroyed */
1096 0, /* todo_flags_start */
1097 TODO_dump_func
| TODO_verify_stmts
| TODO_verify_flow
1098 /* todo_flags_finish */