1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This pass implements tree level if-conversion transformation of loops.
23 Initial goal is to help vectorizer vectorize loops with conditions.
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
94 #include "basic-block.h"
95 #include "diagnostic.h"
96 #include "tree-flow.h"
97 #include "tree-dump.h"
99 #include "tree-chrec.h"
100 #include "tree-data-ref.h"
101 #include "tree-scalar-evolution.h"
102 #include "tree-pass.h"
105 /* local function prototypes */
106 static void main_tree_if_conversion (void);
107 static tree
tree_if_convert_stmt (struct loop
*loop
, tree
, tree
,
108 block_stmt_iterator
*);
109 static void tree_if_convert_cond_expr (struct loop
*, tree
, tree
,
110 block_stmt_iterator
*);
111 static bool if_convertible_phi_p (struct loop
*, basic_block
, tree
);
112 static bool if_convertible_modify_expr_p (struct loop
*, basic_block
, tree
);
113 static bool if_convertible_stmt_p (struct loop
*, basic_block
, tree
);
114 static bool if_convertible_bb_p (struct loop
*, basic_block
, bool);
115 static bool if_convertible_loop_p (struct loop
*, bool);
116 static void add_to_predicate_list (basic_block
, tree
);
117 static tree
add_to_dst_predicate_list (struct loop
* loop
, basic_block
, tree
, tree
,
118 block_stmt_iterator
*);
119 static void clean_predicate_lists (struct loop
*loop
);
120 static basic_block
find_phi_replacement_condition (basic_block
, tree
*,
121 block_stmt_iterator
*);
122 static void replace_phi_with_cond_modify_expr (tree
, tree
, basic_block
,
123 block_stmt_iterator
*);
124 static void process_phi_nodes (struct loop
*);
125 static void combine_blocks (struct loop
*);
126 static tree
ifc_temp_var (tree
, tree
);
127 static bool pred_blocks_visited_p (basic_block
, bitmap
*);
128 static basic_block
* get_loop_body_in_if_conv_order (const struct loop
*loop
);
129 static bool bb_with_exit_edge_p (struct loop
*, basic_block
);
131 /* List of basic blocks in if-conversion-suitable order. */
132 static basic_block
*ifc_bbs
;
135 Apply if-conversion to the LOOP. Return true if successful otherwise return
136 false. If false is returned then loop remains unchanged.
137 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
138 for vectorizer or not. If it is used for vectorizer, additional checks are
139 used. (Vectorization checks are not yet implemented). */
142 tree_if_conversion (struct loop
*loop
, bool for_vectorizer
)
145 block_stmt_iterator itr
;
151 /* if-conversion is not appropriate for all loops. First, check if loop is
152 if-convertible or not. */
153 if (!if_convertible_loop_p (loop
, for_vectorizer
))
155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
156 fprintf (dump_file
,"-------------------------\n");
162 free_dominance_info (CDI_POST_DOMINATORS
);
169 /* Do actual work now. */
170 for (i
= 0; i
< loop
->num_nodes
; i
++)
174 /* Update condition using predicate list. */
177 /* Process all statements in this basic block.
178 Remove conditional expression, if any, and annotate
179 destination basic block(s) appropriately. */
180 for (itr
= bsi_start (bb
); !bsi_end_p (itr
); /* empty */)
182 tree t
= bsi_stmt (itr
);
183 cond
= tree_if_convert_stmt (loop
, t
, cond
, &itr
);
184 if (!bsi_end_p (itr
))
188 /* If current bb has only one successor, then consider it as an
189 unconditional goto. */
190 if (single_succ_p (bb
))
192 basic_block bb_n
= single_succ (bb
);
193 if (cond
!= NULL_TREE
)
194 add_to_predicate_list (bb_n
, cond
);
199 /* Now, all statements are if-converted and basic blocks are
200 annotated appropriately. Combine all basic block into one huge
202 combine_blocks (loop
);
205 clean_predicate_lists (loop
);
213 /* if-convert stmt T which is part of LOOP.
214 If T is a MODIFY_EXPR than it is converted into conditional modify
215 expression using COND. For conditional expressions, add condition in the
216 destination basic block's predicate list and remove conditional
217 expression itself. BSI is the iterator used to traverse statements of
218 loop. It is used here when it is required to delete current statement. */
221 tree_if_convert_stmt (struct loop
* loop
, tree t
, tree cond
,
222 block_stmt_iterator
*bsi
)
224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
226 fprintf (dump_file
, "------if-convert stmt\n");
227 print_generic_stmt (dump_file
, t
, TDF_SLIM
);
228 print_generic_stmt (dump_file
, cond
, TDF_SLIM
);
231 switch (TREE_CODE (t
))
233 /* Labels are harmless here. */
238 /* This modify_expr is killing previous value of LHS. Appropriate value will
239 be selected by PHI node based on condition. It is possible that before
240 this transformation, PHI nodes was selecting default value and now it will
241 use this new value. This is OK because it does not change validity the
246 /* Unconditional goto */
247 add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t
, 1)), cond
);
253 /* Update destination blocks' predicate list and remove this
254 condition expression. */
255 tree_if_convert_cond_expr (loop
, t
, cond
, bsi
);
265 /* STMT is COND_EXPR. Update two destination's predicate list.
266 Remove COND_EXPR, if it is not the loop exit condition. Otherwise
267 update loop exit condition appropriately. BSI is the iterator
268 used to traverse statement list. STMT is part of loop LOOP. */
271 tree_if_convert_cond_expr (struct loop
*loop
, tree stmt
, tree cond
,
272 block_stmt_iterator
*bsi
)
274 tree c
, c2
, new_cond
;
275 edge true_edge
, false_edge
;
276 new_cond
= NULL_TREE
;
278 gcc_assert (TREE_CODE (stmt
) == COND_EXPR
);
280 c
= COND_EXPR_COND (stmt
);
282 /* Create temp. for condition. */
283 if (!is_gimple_condexpr (c
))
286 new_stmt
= ifc_temp_var (TREE_TYPE (c
), unshare_expr (c
));
287 bsi_insert_before (bsi
, new_stmt
, BSI_SAME_STMT
);
288 c
= TREE_OPERAND (new_stmt
, 0);
291 extract_true_false_edges_from_block (bb_for_stmt (stmt
),
292 &true_edge
, &false_edge
);
294 /* Add new condition into destination's predicate list. */
296 /* If 'c' is true then TRUE_EDGE is taken. */
297 new_cond
= add_to_dst_predicate_list (loop
, true_edge
->dest
, cond
,
298 unshare_expr (c
), bsi
);
300 if (!is_gimple_reg(c
) && is_gimple_condexpr (c
))
303 new_stmt
= ifc_temp_var (TREE_TYPE (c
), unshare_expr (c
));
304 bsi_insert_before (bsi
, new_stmt
, BSI_SAME_STMT
);
305 c
= TREE_OPERAND (new_stmt
, 0);
308 /* If 'c' is false then FALSE_EDGE is taken. */
309 c2
= invert_truthvalue (unshare_expr (c
));
310 add_to_dst_predicate_list (loop
, false_edge
->dest
, cond
, c2
, bsi
);
312 /* Now this conditional statement is redundant. Remove it.
313 But, do not remove exit condition! Update exit condition
314 using new condition. */
315 if (!bb_with_exit_edge_p (loop
, bb_for_stmt (stmt
)))
323 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
324 and it belongs to basic block BB.
325 PHI is not if-convertible
326 - if it has more than 2 arguments.
327 - Virtual PHI is immediately used in another PHI node. */
330 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, tree phi
)
332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
334 fprintf (dump_file
, "-------------------------\n");
335 print_generic_stmt (dump_file
, phi
, TDF_SLIM
);
338 if (bb
!= loop
->header
&& PHI_NUM_ARGS (phi
) != 2)
340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
341 fprintf (dump_file
, "More than two phi node args.\n");
345 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
348 dataflow_t df
= get_immediate_uses (phi
);
349 int num_uses
= num_immediate_uses (df
);
350 for (j
= 0; j
< num_uses
; j
++)
352 tree use
= immediate_use (df
, j
);
353 if (TREE_CODE (use
) == PHI_NODE
)
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
356 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
365 /* Return true, if M_EXPR is if-convertible.
366 MODIFY_EXPR is not if-convertible if,
369 - LHS is not var decl.
370 MODIFY_EXPR is part of block BB, which is inside loop LOOP.
374 if_convertible_modify_expr_p (struct loop
*loop
, basic_block bb
, tree m_expr
)
376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
378 fprintf (dump_file
, "-------------------------\n");
379 print_generic_stmt (dump_file
, m_expr
, TDF_SLIM
);
382 /* Be conservative and do not handle immovable expressions. */
383 if (movement_possibility (m_expr
) == MOVE_IMPOSSIBLE
)
385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
386 fprintf (dump_file
, "stmt is movable. Don't take risk\n");
390 /* See if it needs speculative loading or not. */
391 if (bb
!= loop
->header
392 && tree_could_trap_p (TREE_OPERAND (m_expr
, 1)))
394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
395 fprintf (dump_file
, "tree could trap...\n");
399 if (TREE_CODE (TREE_OPERAND (m_expr
, 1)) == CALL_EXPR
)
401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
402 fprintf (dump_file
, "CALL_EXPR \n");
406 if (TREE_CODE (TREE_OPERAND (m_expr
, 0)) != SSA_NAME
407 && bb
!= loop
->header
408 && !bb_with_exit_edge_p (loop
, bb
))
410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
412 fprintf (dump_file
, "LHS is not var\n");
413 print_generic_stmt (dump_file
, m_expr
, TDF_SLIM
);
422 /* Return true, iff STMT is if-convertible.
423 Statement is if-convertible if,
424 - It is if-convertible MODIFY_EXPR
425 - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
426 STMT is inside block BB, which is inside loop LOOP. */
429 if_convertible_stmt_p (struct loop
*loop
, basic_block bb
, tree stmt
)
431 switch (TREE_CODE (stmt
))
438 if (!if_convertible_modify_expr_p (loop
, bb
, stmt
))
447 /* Don't know what to do with 'em so don't do anything. */
448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
450 fprintf (dump_file
, "don't know what to do\n");
451 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
460 /* Return true, iff BB is if-convertible.
461 Note: This routine does _not_ check basic block statements and phis.
462 Basic block is not if-convertible if,
463 - Basic block is non-empty and it is after exit block (in BFS order).
464 - Basic block is after exit block but before latch.
465 - Basic block edge(s) is not normal.
466 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
467 BB is inside loop LOOP. */
470 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, bool exit_bb_seen
)
475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
476 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
480 if (bb
!= loop
->latch
)
482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
483 fprintf (dump_file
, "basic block after exit bb but before latch\n");
486 else if (!empty_block_p (bb
))
488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
489 fprintf (dump_file
, "non empty basic block after exit bb\n");
494 /* Be less adventurous and handle only normal edges. */
495 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
497 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
500 fprintf (dump_file
,"Difficult to handle edges\n");
507 /* Return true, iff LOOP is if-convertible.
508 LOOP is if-convertible if,
510 - It has two or more basic blocks.
511 - It has only one exit.
512 - Loop header is not the exit edge.
513 - If its basic blocks and phi nodes are if convertible. See above for
515 FOR_VECTORIZER enables vectorizer specific checks. For example, support
516 for vector conditions, data dependency checks etc.. (Not implemented yet). */
519 if_convertible_loop_p (struct loop
*loop
, bool for_vectorizer ATTRIBUTE_UNUSED
)
523 block_stmt_iterator itr
;
527 bool exit_bb_seen
= false;
529 /* Handle only inner most loop. */
530 if (!loop
|| loop
->inner
)
532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
533 fprintf (dump_file
, "not inner most loop\n");
537 /* If only one block, no need for if-conversion. */
538 if (loop
->num_nodes
<= 2)
540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
541 fprintf (dump_file
, "less than 2 basic blocks\n");
545 /* More than one loop exit is too much to handle. */
546 if (!loop
->single_exit
)
548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
549 fprintf (dump_file
, "multiple exits\n");
553 /* ??? Check target's vector conditional operation support for vectorizer. */
555 /* If one of the loop header's edge is exit edge then do not apply
557 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
559 if (loop_exit_edge_p (loop
, e
))
563 compute_immediate_uses (TDFA_USE_OPS
|TDFA_USE_VOPS
, NULL
);
565 calculate_dominance_info (CDI_DOMINATORS
);
566 calculate_dominance_info (CDI_POST_DOMINATORS
);
568 /* Allow statements that can be handled during if-conversion. */
569 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
,"Irreducible loop\n");
574 free_dominance_info (CDI_POST_DOMINATORS
);
578 for (i
= 0; i
< loop
->num_nodes
; i
++)
582 if (!if_convertible_bb_p (loop
, bb
, exit_bb_seen
))
585 /* Check statements. */
586 for (itr
= bsi_start (bb
); !bsi_end_p (itr
); bsi_next (&itr
))
587 if (!if_convertible_stmt_p (loop
, bb
, bsi_stmt (itr
)))
589 /* ??? Check data dependency for vectorizer. */
591 /* What about phi nodes ? */
592 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
593 if (!if_convertible_phi_p (loop
, bb
, phi
))
596 if (bb_with_exit_edge_p (loop
, bb
))
600 /* OK. Did not find any potential issues so go ahead in if-convert
601 this loop. Now there is no looking back. */
603 fprintf (dump_file
,"Applying if-conversion\n");
605 free_dominance_info (CDI_POST_DOMINATORS
);
609 /* Add condition COND into predicate list of basic block BB. */
612 add_to_predicate_list (basic_block bb
, tree new_cond
)
617 cond
= fold (build (TRUTH_OR_EXPR
, boolean_type_node
,
618 unshare_expr (cond
), new_cond
));
625 /* Add condition COND into BB's predicate list. PREV_COND is
626 existing condition. */
629 add_to_dst_predicate_list (struct loop
* loop
, basic_block bb
,
630 tree prev_cond
, tree cond
,
631 block_stmt_iterator
*bsi
)
633 tree new_cond
= NULL_TREE
;
635 if (!flow_bb_inside_loop_p (loop
, bb
))
638 if (prev_cond
== boolean_true_node
|| !prev_cond
)
639 new_cond
= unshare_expr (cond
);
643 tree tmp_stmt
= NULL_TREE
;
644 tree tmp_stmts1
= NULL_TREE
;
645 tree tmp_stmts2
= NULL_TREE
;
646 prev_cond
= force_gimple_operand (unshare_expr (prev_cond
),
647 &tmp_stmts1
, true, NULL
);
649 bsi_insert_before (bsi
, tmp_stmts1
, BSI_SAME_STMT
);
651 cond
= force_gimple_operand (unshare_expr (cond
),
652 &tmp_stmts2
, true, NULL
);
654 bsi_insert_before (bsi
, tmp_stmts2
, BSI_SAME_STMT
);
656 /* new_cond == prev_cond AND cond */
657 tmp
= build (TRUTH_AND_EXPR
, boolean_type_node
,
658 unshare_expr (prev_cond
), cond
);
659 tmp_stmt
= ifc_temp_var (boolean_type_node
, tmp
);
660 bsi_insert_before (bsi
, tmp_stmt
, BSI_SAME_STMT
);
661 new_cond
= TREE_OPERAND (tmp_stmt
, 0);
663 add_to_predicate_list (bb
, new_cond
);
667 /* During if-conversion aux field from basic block is used to hold predicate
668 list. Clean each basic block's predicate list for the given LOOP. */
671 clean_predicate_lists (struct loop
*loop
)
675 bb
= get_loop_body (loop
);
676 for (i
= 0; i
< loop
->num_nodes
; i
++)
682 /* Basic block BB has two predecessors. Using predecessor's aux field, set
683 appropriate condition COND for the PHI node replacement. Return true block
684 whose phi arguments are selected when cond is true. */
687 find_phi_replacement_condition (basic_block bb
, tree
*cond
,
688 block_stmt_iterator
*bsi
)
691 basic_block p1
= NULL
;
692 basic_block p2
= NULL
;
693 basic_block true_bb
= NULL
;
697 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
708 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
710 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
721 /* Create temp. for the condition. Vectorizer prefers to have gimple
722 value as condition. Various targets use different means to communicate
723 condition in vector compare operation. Using gimple value allows compiler
724 to emit vector compare and select RTL without exposing compare's result. */
725 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
729 new_stmt
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
));
730 bsi_insert_after (bsi
, new_stmt
, BSI_SAME_STMT
);
732 *cond
= TREE_OPERAND (new_stmt
, 0);
741 /* Replace PHI node with conditional modify expr using COND.
742 This routine does not handle PHI nodes with more than two arguments.
744 S1: A = PHI <x1(1), x2(5)
746 S2: A = cond ? x1 : x2;
747 S2 is inserted at the top of basic block's statement list.
748 When COND is true, phi arg from TRUE_BB is selected.
752 replace_phi_with_cond_modify_expr (tree phi
, tree cond
, basic_block true_bb
,
753 block_stmt_iterator
*bsi
)
760 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
762 /* If this is not filtered earlier, then now it is too late. */
763 gcc_assert (PHI_NUM_ARGS (phi
) == 2);
765 /* Find basic block and initialize iterator. */
766 bb
= bb_for_stmt (phi
);
768 new_stmt
= NULL_TREE
;
772 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
773 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
775 arg_0
= PHI_ARG_DEF (phi
, 1);
776 arg_1
= PHI_ARG_DEF (phi
, 0);
780 arg_0
= PHI_ARG_DEF (phi
, 0);
781 arg_1
= PHI_ARG_DEF (phi
, 1);
784 /* Build new RHS using selected condition and arguments. */
785 rhs
= build (COND_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
786 unshare_expr (cond
), unshare_expr (arg_0
),
787 unshare_expr (arg_1
));
789 /* Create new MODIFY expression using RHS. */
790 new_stmt
= build (MODIFY_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
791 unshare_expr (PHI_RESULT (phi
)), rhs
);
793 /* Make new statement definition of the original phi result. */
794 SSA_NAME_DEF_STMT (PHI_RESULT (phi
)) = new_stmt
;
796 /* Set basic block and insert using iterator. */
797 set_bb_for_stmt (new_stmt
, bb
);
799 bsi_insert_after (bsi
, new_stmt
, BSI_SAME_STMT
);
802 modify_stmt (new_stmt
);
804 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
806 fprintf (dump_file
, "new phi replacement stmt\n");
807 print_generic_stmt (dump_file
, new_stmt
, TDF_SLIM
);
811 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
815 process_phi_nodes (struct loop
*loop
)
818 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
821 /* Replace phi nodes with cond. modify expr. */
822 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
825 block_stmt_iterator bsi
;
826 basic_block true_bb
= NULL
;
829 if (bb
== loop
->header
)
832 phi
= phi_nodes (bb
);
833 bsi
= bsi_after_labels (bb
);
835 /* BB has two predecessors. Using predecessor's aux field, set
836 appropriate condition for the PHI node replacement. */
838 true_bb
= find_phi_replacement_condition (bb
, &cond
, &bsi
);
842 tree next
= PHI_CHAIN (phi
);
843 replace_phi_with_cond_modify_expr (phi
, cond
, true_bb
, &bsi
);
844 release_phi_node (phi
);
847 bb_ann (bb
)->phi_nodes
= NULL
;
852 /* Combine all basic block from the given LOOP into one or two super
853 basic block. Replace PHI nodes with conditional modify expression. */
856 combine_blocks (struct loop
*loop
)
858 basic_block bb
, exit_bb
, merge_target_bb
;
859 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
861 unsigned int n_exits
;
862 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
863 /* Process phi nodes to prepare blocks for merge. */
864 process_phi_nodes (loop
);
868 /* Merge basic blocks */
869 merge_target_bb
= loop
->header
;
870 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
873 block_stmt_iterator bsi
;
874 tree_stmt_iterator last
;
878 if (!exit_bb
&& bb_with_exit_edge_p (loop
, bb
))
886 /* Connect this node with loop header. */
887 new_e
= make_edge (ifc_bbs
[0], bb
, EDGE_FALLTHRU
);
888 set_immediate_dominator (CDI_DOMINATORS
, bb
, ifc_bbs
[0]);
890 if (exit_bb
!= loop
->latch
)
892 /* Redirect non-exit edge to loop->latch. */
893 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
895 if (!loop_exit_edge_p (loop
, e
))
897 redirect_edge_and_branch (e
, loop
->latch
);
898 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, bb
);
905 if (bb
== loop
->latch
&& empty_block_p (bb
))
908 /* It is time to remove this basic block. First remove edges. */
909 while (EDGE_COUNT (bb
->preds
) > 0)
910 remove_edge (EDGE_PRED (bb
, 0));
912 /* This is loop latch and loop does not have exit then do not
913 delete this basic block. Just remove its PREDS and reconnect
914 loop->header and loop->latch blocks. */
915 if (bb
== loop
->latch
&& n_exits
== 0)
917 exits
= NULL
; /* To suppress unused warning. */
918 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
919 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
923 while (EDGE_COUNT (bb
->succs
) > 0)
924 remove_edge (EDGE_SUCC (bb
, 0));
926 /* Remove labels and make stmts member of loop->header. */
927 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
929 if (TREE_CODE (bsi_stmt (bsi
)) == LABEL_EXPR
)
933 set_bb_for_stmt (bsi_stmt (bsi
), merge_target_bb
);
938 /* Update stmt list. */
939 last
= tsi_last (merge_target_bb
->stmt_list
);
940 tsi_link_after (&last
, bb
->stmt_list
, TSI_NEW_STMT
);
941 bb
->stmt_list
= NULL
;
943 /* Update dominator info. */
944 if (dom_computed
[CDI_DOMINATORS
])
945 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
946 if (dom_computed
[CDI_POST_DOMINATORS
])
947 delete_from_dominance_info (CDI_POST_DOMINATORS
, bb
);
949 /* Remove basic block. */
950 if (bb
== loop
->latch
)
951 loop
->latch
= merge_target_bb
;
952 remove_bb_from_loops (bb
);
956 /* Now if possible, merge loop header and block with exit edge.
957 This reduces number of basic blocks to 2. Auto vectorizer addresses
958 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
960 && loop
->header
!= loop
->latch
961 && exit_bb
!= loop
->latch
962 && empty_block_p (loop
->latch
))
964 if (can_merge_blocks_p (loop
->header
, exit_bb
))
966 remove_bb_from_loops (exit_bb
);
967 merge_blocks (loop
->header
, exit_bb
);
972 /* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
973 to the new variable. */
976 ifc_temp_var (tree type
, tree exp
)
978 const char *name
= "_ifc_";
979 tree var
, stmt
, new_name
;
981 if (is_gimple_reg (exp
))
984 /* Create new temporary variable. */
985 var
= create_tmp_var (type
, name
);
986 add_referenced_tmp_var (var
);
988 /* Build new statement to assign EXP to new variable. */
989 stmt
= build (MODIFY_EXPR
, type
, var
, exp
);
991 /* Get SSA name for the new variable and set make new statement
992 its definition statement. */
993 new_name
= make_ssa_name (var
, stmt
);
994 TREE_OPERAND (stmt
, 0) = new_name
;
995 SSA_NAME_DEF_STMT (new_name
) = stmt
;
1001 /* Return TRUE iff, all pred blocks of BB are visited.
1002 Bitmap VISITED keeps history of visited blocks. */
1005 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1009 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1010 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1016 /* Get body of a LOOP in suitable order for if-conversion.
1017 It is caller's responsibility to deallocate basic block
1018 list. If-conversion suitable order is, BFS order with one
1019 additional constraint. Select block in BFS block, if all
1020 pred are already selected. */
1022 static basic_block
*
1023 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1025 basic_block
*blocks
, *blocks_in_bfs_order
;
1028 unsigned int index
= 0;
1029 unsigned int visited_count
= 0;
1031 gcc_assert (loop
->num_nodes
);
1032 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1034 blocks
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1035 visited
= BITMAP_ALLOC (NULL
);
1037 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1040 while (index
< loop
->num_nodes
)
1042 bb
= blocks_in_bfs_order
[index
];
1044 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1046 free (blocks_in_bfs_order
);
1047 BITMAP_FREE (visited
);
1051 if (!bitmap_bit_p (visited
, bb
->index
))
1053 if (pred_blocks_visited_p (bb
, &visited
)
1054 || bb
== loop
->header
)
1056 /* This block is now visited. */
1057 bitmap_set_bit (visited
, bb
->index
);
1058 blocks
[visited_count
++] = bb
;
1062 if (index
== loop
->num_nodes
1063 && visited_count
!= loop
->num_nodes
)
1069 free (blocks_in_bfs_order
);
1070 BITMAP_FREE (visited
);
1074 /* Return true if one of the basic block BB edge is exit of LOOP. */
1077 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
1081 bool exit_edge_found
= false;
1083 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1084 if (loop_exit_edge_p (loop
, e
))
1086 exit_edge_found
= true;
1090 return exit_edge_found
;
1093 /* Tree if-conversion pass management. */
1096 main_tree_if_conversion (void)
1098 unsigned i
, loop_num
;
1104 loop_num
= current_loops
->num
;
1105 for (i
= 0; i
< loop_num
; i
++)
1107 loop
= current_loops
->parray
[i
];
1111 tree_if_conversion (loop
, true);
1117 gate_tree_if_conversion (void)
1119 return flag_tree_vectorize
!= 0;
1122 struct tree_opt_pass pass_if_conversion
=
1125 gate_tree_if_conversion
, /* gate */
1126 main_tree_if_conversion
, /* execute */
1129 0, /* static_pass_number */
1131 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1132 0, /* properties_provided */
1133 0, /* properties_destroyed */
1134 TODO_dump_func
, /* todo_flags_start */
1138 | TODO_verify_flow
, /* todo_flags_finish */