1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007 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, 51 Franklin Street, Fifth Floor, 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"
93 #include "basic-block.h"
94 #include "diagnostic.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"
104 /* local function prototypes */
105 static unsigned int main_tree_if_conversion (void);
106 static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
107 block_stmt_iterator *);
108 static void tree_if_convert_cond_expr (struct loop *, tree, tree,
109 block_stmt_iterator *);
110 static bool if_convertible_phi_p (struct loop *, basic_block, tree);
111 static bool if_convertible_gimple_modify_stmt_p (struct loop *, basic_block,
113 static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
114 static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
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, edge,
119 block_stmt_iterator *);
120 static void clean_predicate_lists (struct loop *loop);
121 static basic_block find_phi_replacement_condition (struct loop *loop,
123 block_stmt_iterator *);
124 static void replace_phi_with_cond_gimple_modify_stmt (tree, tree, basic_block,
125 block_stmt_iterator *);
126 static void process_phi_nodes (struct loop *);
127 static void combine_blocks (struct loop *);
128 static tree ifc_temp_var (tree, tree);
129 static bool pred_blocks_visited_p (basic_block, bitmap *);
130 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
131 static bool bb_with_exit_edge_p (struct loop *, basic_block);
133 /* List of basic blocks in if-conversion-suitable order. */
134 static basic_block *ifc_bbs;
137 Apply if-conversion to the LOOP. Return true if successful otherwise return
138 false. If false is returned then loop remains unchanged.
139 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
140 for vectorizer or not. If it is used for vectorizer, additional checks are
141 used. (Vectorization checks are not yet implemented). */
144 tree_if_conversion (struct loop *loop, bool for_vectorizer)
147 block_stmt_iterator itr;
152 /* if-conversion is not appropriate for all loops. First, check if loop is
153 if-convertible or not. */
154 if (!if_convertible_loop_p (loop, for_vectorizer))
156 if (dump_file && (dump_flags & TDF_DETAILS))
157 fprintf (dump_file,"-------------------------\n");
163 free_dominance_info (CDI_POST_DOMINATORS);
167 /* Do actual work now. */
168 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);
198 /* Now, all statements are if-converted and basic blocks are
199 annotated appropriately. Combine all basic block into one huge
201 combine_blocks (loop);
204 clean_predicate_lists (loop);
211 /* if-convert stmt T which is part of LOOP.
212 If T is a GIMPLE_MODIFY_STMT than it is converted into conditional modify
213 expression using COND. For conditional expressions, add condition in the
214 destination basic block's predicate list and remove conditional
215 expression itself. BSI is the iterator used to traverse statements of
216 loop. It is used here when it is required to delete current statement. */
219 tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
220 block_stmt_iterator *bsi)
222 if (dump_file && (dump_flags & TDF_DETAILS))
224 fprintf (dump_file, "------if-convert stmt\n");
225 print_generic_stmt (dump_file, t, TDF_SLIM);
226 print_generic_stmt (dump_file, cond, TDF_SLIM);
229 switch (TREE_CODE (t))
231 /* Labels are harmless here. */
235 case GIMPLE_MODIFY_STMT:
236 /* This GIMPLE_MODIFY_STMT is killing previous value of LHS. Appropriate
237 value will be selected by PHI node based on condition. It is possible
238 that before this transformation, PHI nodes was selecting default
239 value and now it will use this new value. This is OK because it does
240 not change validity the program. */
244 /* Update destination blocks' predicate list and remove this
245 condition expression. */
246 tree_if_convert_cond_expr (loop, t, cond, bsi);
256 /* STMT is COND_EXPR. Update two destination's predicate list.
257 Remove COND_EXPR, if it is not the loop exit condition. Otherwise
258 update loop exit condition appropriately. BSI is the iterator
259 used to traverse statement list. STMT is part of loop LOOP. */
262 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
263 block_stmt_iterator *bsi)
266 edge true_edge, false_edge;
268 gcc_assert (TREE_CODE (stmt) == COND_EXPR);
270 c = COND_EXPR_COND (stmt);
272 extract_true_false_edges_from_block (bb_for_stmt (stmt),
273 &true_edge, &false_edge);
275 /* Add new condition into destination's predicate list. */
277 /* If 'c' is true then TRUE_EDGE is taken. */
278 add_to_dst_predicate_list (loop, true_edge, cond,
279 unshare_expr (c), bsi);
281 /* If 'c' is false then FALSE_EDGE is taken. */
282 c2 = invert_truthvalue (unshare_expr (c));
283 add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
285 /* Now this conditional statement is redundant. Remove it.
286 But, do not remove exit condition! Update exit condition
287 using new condition. */
288 if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
290 bsi_remove (bsi, true);
296 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
297 and it belongs to basic block BB.
298 PHI is not if-convertible
299 - if it has more than 2 arguments.
300 - Virtual PHI is immediately used in another PHI node. */
303 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
305 if (dump_file && (dump_flags & TDF_DETAILS))
307 fprintf (dump_file, "-------------------------\n");
308 print_generic_stmt (dump_file, phi, TDF_SLIM);
311 if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
313 if (dump_file && (dump_flags & TDF_DETAILS))
314 fprintf (dump_file, "More than two phi node args.\n");
318 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
320 imm_use_iterator imm_iter;
322 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
324 if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
326 if (dump_file && (dump_flags & TDF_DETAILS))
327 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
336 /* Return true, if M_EXPR is if-convertible.
337 GIMPLE_MODIFY_STMT is not if-convertible if,
340 - LHS is not var decl.
341 GIMPLE_MODIFY_STMT is part of block BB, which is inside loop LOOP.
345 if_convertible_gimple_modify_stmt_p (struct loop *loop, basic_block bb,
350 if (TREE_CODE (m_expr) != GIMPLE_MODIFY_STMT)
353 if (dump_file && (dump_flags & TDF_DETAILS))
355 fprintf (dump_file, "-------------------------\n");
356 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
359 lhs = GIMPLE_STMT_OPERAND (m_expr, 0);
360 rhs = GIMPLE_STMT_OPERAND (m_expr, 1);
362 /* Some of these constrains might be too conservative. */
363 if (stmt_ends_bb_p (m_expr) || stmt_ann (m_expr)->has_volatile_ops
364 || (TREE_CODE (lhs) == SSA_NAME
365 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
366 || TREE_SIDE_EFFECTS (rhs))
368 if (dump_file && (dump_flags & TDF_DETAILS))
369 fprintf (dump_file, "stmt not suitable for ifcvt\n");
373 /* See if it needs speculative loading or not. */
374 if (bb != loop->header
375 && tree_could_trap_p (GIMPLE_STMT_OPERAND (m_expr, 1)))
377 if (dump_file && (dump_flags & TDF_DETAILS))
378 fprintf (dump_file, "tree could trap...\n");
382 if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 1)) == CALL_EXPR)
384 if (dump_file && (dump_flags & TDF_DETAILS))
385 fprintf (dump_file, "CALL_EXPR \n");
389 if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 0)) != SSA_NAME
390 && bb != loop->header
391 && !bb_with_exit_edge_p (loop, bb))
393 if (dump_file && (dump_flags & TDF_DETAILS))
395 fprintf (dump_file, "LHS is not var\n");
396 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
405 /* Return true, iff STMT is if-convertible.
406 Statement is if-convertible if,
407 - It is if-convertible GIMPLE_MODIFY_STMT
408 - IT is LABEL_EXPR or COND_EXPR.
409 STMT is inside block BB, which is inside loop LOOP. */
412 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
414 switch (TREE_CODE (stmt))
419 case GIMPLE_MODIFY_STMT:
421 if (!if_convertible_gimple_modify_stmt_p (loop, bb, stmt))
429 /* Don't know what to do with 'em so don't do anything. */
430 if (dump_file && (dump_flags & TDF_DETAILS))
432 fprintf (dump_file, "don't know what to do\n");
433 print_generic_stmt (dump_file, stmt, TDF_SLIM);
442 /* Return true, iff BB is if-convertible.
443 Note: This routine does _not_ check basic block statements and phis.
444 Basic block is not if-convertible if,
445 - Basic block is non-empty and it is after exit block (in BFS order).
446 - Basic block is after exit block but before latch.
447 - Basic block edge(s) is not normal.
448 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
449 BB is inside loop LOOP. */
452 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
457 if (dump_file && (dump_flags & TDF_DETAILS))
458 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
462 if (bb != loop->latch)
464 if (dump_file && (dump_flags & TDF_DETAILS))
465 fprintf (dump_file, "basic block after exit bb but before latch\n");
468 else if (!empty_block_p (bb))
470 if (dump_file && (dump_flags & TDF_DETAILS))
471 fprintf (dump_file, "non empty basic block after exit bb\n");
474 else if (bb == loop->latch
476 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
478 if (dump_file && (dump_flags & TDF_DETAILS))
479 fprintf (dump_file, "latch is not dominated by exit_block\n");
484 /* Be less adventurous and handle only normal edges. */
485 FOR_EACH_EDGE (e, ei, bb->succs)
487 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
489 if (dump_file && (dump_flags & TDF_DETAILS))
490 fprintf (dump_file,"Difficult to handle edges\n");
497 /* Return true, iff LOOP is if-convertible.
498 LOOP is if-convertible if,
500 - It has two or more basic blocks.
501 - It has only one exit.
502 - Loop header is not the exit edge.
503 - If its basic blocks and phi nodes are if convertible. See above for
505 FOR_VECTORIZER enables vectorizer specific checks. For example, support
506 for vector conditions, data dependency checks etc.. (Not implemented yet). */
509 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
513 block_stmt_iterator itr;
517 basic_block exit_bb = NULL;
519 /* Handle only inner most loop. */
520 if (!loop || loop->inner)
522 if (dump_file && (dump_flags & TDF_DETAILS))
523 fprintf (dump_file, "not inner most loop\n");
527 /* If only one block, no need for if-conversion. */
528 if (loop->num_nodes <= 2)
530 if (dump_file && (dump_flags & TDF_DETAILS))
531 fprintf (dump_file, "less than 2 basic blocks\n");
535 /* More than one loop exit is too much to handle. */
536 if (!single_exit (loop))
538 if (dump_file && (dump_flags & TDF_DETAILS))
539 fprintf (dump_file, "multiple exits\n");
543 /* ??? Check target's vector conditional operation support for vectorizer. */
545 /* If one of the loop header's edge is exit edge then do not apply
547 FOR_EACH_EDGE (e, ei, loop->header->succs)
549 if (loop_exit_edge_p (loop, e))
553 calculate_dominance_info (CDI_DOMINATORS);
554 calculate_dominance_info (CDI_POST_DOMINATORS);
556 /* Allow statements that can be handled during if-conversion. */
557 ifc_bbs = get_loop_body_in_if_conv_order (loop);
560 if (dump_file && (dump_flags & TDF_DETAILS))
561 fprintf (dump_file,"Irreducible loop\n");
562 free_dominance_info (CDI_POST_DOMINATORS);
566 for (i = 0; i < loop->num_nodes; i++)
570 if (!if_convertible_bb_p (loop, bb, exit_bb))
573 /* Check statements. */
574 for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
575 if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
577 /* ??? Check data dependency for vectorizer. */
579 /* What about phi nodes ? */
580 phi = phi_nodes (bb);
582 /* Clear aux field of incoming edges to a bb with a phi node. */
584 FOR_EACH_EDGE (e, ei, bb->preds)
587 /* Check statements. */
588 for (; phi; phi = PHI_CHAIN (phi))
589 if (!if_convertible_phi_p (loop, bb, phi))
592 if (bb_with_exit_edge_p (loop, bb))
596 /* OK. Did not find any potential issues so go ahead in if-convert
597 this loop. Now there is no looking back. */
599 fprintf (dump_file,"Applying if-conversion\n");
601 free_dominance_info (CDI_POST_DOMINATORS);
605 /* Add condition COND into predicate list of basic block BB. */
608 add_to_predicate_list (basic_block bb, tree new_cond)
613 cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
614 unshare_expr (cond), new_cond);
621 /* Add condition COND into BB's predicate list. PREV_COND is
622 existing condition. */
625 add_to_dst_predicate_list (struct loop * loop, edge e,
626 tree prev_cond, tree cond,
627 block_stmt_iterator *bsi)
629 tree new_cond = NULL_TREE;
631 if (!flow_bb_inside_loop_p (loop, e->dest))
634 if (prev_cond == boolean_true_node || !prev_cond)
635 new_cond = unshare_expr (cond);
639 tree tmp_stmt = NULL_TREE;
641 prev_cond = force_gimple_operand_bsi (bsi, unshare_expr (prev_cond),
642 true, NULL, true, BSI_SAME_STMT);
644 cond = force_gimple_operand_bsi (bsi, unshare_expr (cond),
645 true, NULL, true, BSI_SAME_STMT);
647 /* Add the condition to aux field of the edge. In case edge
648 destination is a PHI node, this condition will be ANDed with
649 block predicate to construct complete condition. */
652 /* new_cond == prev_cond AND cond */
653 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
654 unshare_expr (prev_cond), cond);
655 tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
656 bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
657 new_cond = GIMPLE_STMT_OPERAND (tmp_stmt, 0);
659 add_to_predicate_list (e->dest, new_cond);
663 /* During if-conversion aux field from basic block structure is used to hold
664 predicate list. Clean each basic block's predicate list for the given LOOP.
665 Also clean aux field of successor edges, used to hold true and false
666 condition from conditional expression. */
669 clean_predicate_lists (struct loop *loop)
676 bb = get_loop_body (loop);
677 for (i = 0; i < loop->num_nodes; i++)
680 FOR_EACH_EDGE (e, ei, bb[i]->succs)
686 /* Basic block BB has two predecessors. Using predecessor's aux field, set
687 appropriate condition COND for the PHI node replacement. Return true block
688 whose phi arguments are selected when cond is true. */
691 find_phi_replacement_condition (struct loop *loop,
692 basic_block bb, tree *cond,
693 block_stmt_iterator *bsi)
695 edge first_edge, second_edge;
698 gcc_assert (EDGE_COUNT (bb->preds) == 2);
699 first_edge = EDGE_PRED (bb, 0);
700 second_edge = EDGE_PRED (bb, 1);
702 /* Use condition based on following criteria:
708 S2 is preferred over S1. Make 'b' first_bb and use its condition.
710 2) Do not make loop header first_bb.
713 S1: x = !(c == d)? a : b;
718 S3: x = (c == d) ? b : a;
720 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
723 4) If pred B is dominated by pred A then use pred B's condition.
726 /* Select condition that is not TRUTH_NOT_EXPR. */
727 tmp_cond = (first_edge->src)->aux;
728 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
732 tmp_edge = first_edge;
733 first_edge = second_edge;
734 second_edge = tmp_edge;
737 /* Check if FIRST_BB is loop header or not and make sure that
738 FIRST_BB does not dominate SECOND_BB. */
739 if (first_edge->src == loop->header
740 || dominated_by_p (CDI_DOMINATORS,
741 second_edge->src, first_edge->src))
743 *cond = (second_edge->src)->aux;
745 /* If there is a condition on an incoming edge,
746 AND it with the incoming bb predicate. */
747 if (second_edge->aux)
748 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
749 *cond, second_edge->aux);
751 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
752 /* We can be smart here and choose inverted
753 condition without switching bbs. */
754 *cond = invert_truthvalue (*cond);
756 /* Select non loop header bb. */
757 first_edge = second_edge;
761 /* FIRST_BB is not loop header */
762 *cond = (first_edge->src)->aux;
764 /* If there is a condition on an incoming edge,
765 AND it with the incoming bb predicate. */
767 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
768 *cond, first_edge->aux);
771 /* Create temp. for the condition. Vectorizer prefers to have gimple
772 value as condition. Various targets use different means to communicate
773 condition in vector compare operation. Using gimple value allows compiler
774 to emit vector compare and select RTL without exposing compare's result. */
775 *cond = force_gimple_operand_bsi (bsi, *cond, false, NULL_TREE,
776 true, BSI_SAME_STMT);
777 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
781 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
782 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
783 *cond = GIMPLE_STMT_OPERAND (new_stmt, 0);
788 return first_edge->src;
792 /* Replace PHI node with conditional modify expr using COND.
793 This routine does not handle PHI nodes with more than two arguments.
795 S1: A = PHI <x1(1), x2(5)
797 S2: A = cond ? x1 : x2;
798 S2 is inserted at the top of basic block's statement list.
799 When COND is true, phi arg from TRUE_BB is selected.
803 replace_phi_with_cond_gimple_modify_stmt (tree phi, tree cond,
805 block_stmt_iterator *bsi)
812 gcc_assert (TREE_CODE (phi) == PHI_NODE);
814 /* If this is not filtered earlier, then now it is too late. */
815 gcc_assert (PHI_NUM_ARGS (phi) == 2);
817 /* Find basic block and initialize iterator. */
818 bb = bb_for_stmt (phi);
820 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
821 if (EDGE_PRED (bb, 1)->src == true_bb)
823 arg_0 = PHI_ARG_DEF (phi, 1);
824 arg_1 = PHI_ARG_DEF (phi, 0);
828 arg_0 = PHI_ARG_DEF (phi, 0);
829 arg_1 = PHI_ARG_DEF (phi, 1);
832 /* Build new RHS using selected condition and arguments. */
833 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
834 unshare_expr (cond), unshare_expr (arg_0),
835 unshare_expr (arg_1));
837 /* Create new MODIFY expression using RHS. */
838 new_stmt = build_gimple_modify_stmt (unshare_expr (PHI_RESULT (phi)), rhs);
840 /* Make new statement definition of the original phi result. */
841 SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
843 /* Insert using iterator. */
844 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
845 update_stmt (new_stmt);
847 if (dump_file && (dump_flags & TDF_DETAILS))
849 fprintf (dump_file, "new phi replacement stmt\n");
850 print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
854 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
858 process_phi_nodes (struct loop *loop)
861 unsigned int orig_loop_num_nodes = loop->num_nodes;
864 /* Replace phi nodes with cond. modify expr. */
865 for (i = 1; i < orig_loop_num_nodes; i++)
868 block_stmt_iterator bsi;
869 basic_block true_bb = NULL;
872 if (bb == loop->header)
875 phi = phi_nodes (bb);
876 bsi = bsi_after_labels (bb);
878 /* BB has two predecessors. Using predecessor's aux field, set
879 appropriate condition for the PHI node replacement. */
881 true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
885 tree next = PHI_CHAIN (phi);
886 replace_phi_with_cond_gimple_modify_stmt (phi, cond, true_bb, &bsi);
887 release_phi_node (phi);
890 set_phi_nodes (bb, NULL_TREE);
895 /* Combine all basic block from the given LOOP into one or two super
896 basic block. Replace PHI nodes with conditional modify expression. */
899 combine_blocks (struct loop *loop)
901 basic_block bb, exit_bb, merge_target_bb;
902 unsigned int orig_loop_num_nodes = loop->num_nodes;
907 /* Process phi nodes to prepare blocks for merge. */
908 process_phi_nodes (loop);
910 /* Merge basic blocks. First remove all the edges in the loop, except
911 for those from the exit block. */
913 for (i = 0; i < orig_loop_num_nodes; i++)
916 if (bb_with_exit_edge_p (loop, bb))
922 gcc_assert (exit_bb != loop->latch);
924 for (i = 1; i < orig_loop_num_nodes; i++)
928 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
930 if (e->src == exit_bb)
939 if (exit_bb != loop->header)
941 /* Connect this node with loop header. */
942 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
943 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
946 /* Redirect non-exit edges to loop->latch. */
947 FOR_EACH_EDGE (e, ei, exit_bb->succs)
949 if (!loop_exit_edge_p (loop, e))
950 redirect_edge_and_branch (e, loop->latch);
952 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
956 /* If the loop does not have exit then reconnect header and latch. */
957 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
958 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
961 merge_target_bb = loop->header;
962 for (i = 1; i < orig_loop_num_nodes; i++)
964 block_stmt_iterator bsi;
965 tree_stmt_iterator last;
969 if (bb == exit_bb || bb == loop->latch)
972 /* Remove labels and make stmts member of loop->header. */
973 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
975 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
976 bsi_remove (&bsi, true);
979 set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
984 /* Update stmt list. */
985 last = tsi_last (bb_stmt_list (merge_target_bb));
986 tsi_link_after (&last, bb_stmt_list (bb), TSI_NEW_STMT);
987 set_bb_stmt_list (bb, NULL);
989 delete_basic_block (bb);
992 /* Now if possible, merge loop header and block with exit edge.
993 This reduces number of basic blocks to 2. Auto vectorizer addresses
994 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
996 && exit_bb != loop->header
997 && can_merge_blocks_p (loop->header, exit_bb))
998 merge_blocks (loop->header, exit_bb);
1001 /* Make new temp variable of type TYPE. Add GIMPLE_MODIFY_STMT to assign EXP
1002 to the new variable. */
1005 ifc_temp_var (tree type, tree exp)
1007 const char *name = "_ifc_";
1008 tree var, stmt, new_name;
1010 if (is_gimple_reg (exp))
1013 /* Create new temporary variable. */
1014 var = create_tmp_var (type, name);
1015 add_referenced_var (var);
1017 /* Build new statement to assign EXP to new variable. */
1018 stmt = build_gimple_modify_stmt (var, exp);
1020 /* Get SSA name for the new variable and set make new statement
1021 its definition statement. */
1022 new_name = make_ssa_name (var, stmt);
1023 GIMPLE_STMT_OPERAND (stmt, 0) = new_name;
1024 SSA_NAME_DEF_STMT (new_name) = stmt;
1030 /* Return TRUE iff, all pred blocks of BB are visited.
1031 Bitmap VISITED keeps history of visited blocks. */
1034 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1038 FOR_EACH_EDGE (e, ei, bb->preds)
1039 if (!bitmap_bit_p (*visited, e->src->index))
1045 /* Get body of a LOOP in suitable order for if-conversion.
1046 It is caller's responsibility to deallocate basic block
1047 list. If-conversion suitable order is, BFS order with one
1048 additional constraint. Select block in BFS block, if all
1049 pred are already selected. */
1051 static basic_block *
1052 get_loop_body_in_if_conv_order (const struct loop *loop)
1054 basic_block *blocks, *blocks_in_bfs_order;
1057 unsigned int index = 0;
1058 unsigned int visited_count = 0;
1060 gcc_assert (loop->num_nodes);
1061 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1063 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1064 visited = BITMAP_ALLOC (NULL);
1066 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1069 while (index < loop->num_nodes)
1071 bb = blocks_in_bfs_order [index];
1073 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1075 free (blocks_in_bfs_order);
1076 BITMAP_FREE (visited);
1080 if (!bitmap_bit_p (visited, bb->index))
1082 if (pred_blocks_visited_p (bb, &visited)
1083 || bb == loop->header)
1085 /* This block is now visited. */
1086 bitmap_set_bit (visited, bb->index);
1087 blocks[visited_count++] = bb;
1091 if (index == loop->num_nodes
1092 && visited_count != loop->num_nodes)
1098 free (blocks_in_bfs_order);
1099 BITMAP_FREE (visited);
1103 /* Return true if one of the basic block BB edge is exit of LOOP. */
1106 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1110 bool exit_edge_found = false;
1112 FOR_EACH_EDGE (e, ei, bb->succs)
1113 if (loop_exit_edge_p (loop, e))
1115 exit_edge_found = true;
1119 return exit_edge_found;
1122 /* Tree if-conversion pass management. */
1125 main_tree_if_conversion (void)
1130 if (number_of_loops () <= 1)
1133 FOR_EACH_LOOP (li, loop, 0)
1135 tree_if_conversion (loop, true);
1141 gate_tree_if_conversion (void)
1143 return flag_tree_vectorize != 0;
1146 struct tree_opt_pass pass_if_conversion =
1149 gate_tree_if_conversion, /* gate */
1150 main_tree_if_conversion, /* execute */
1153 0, /* static_pass_number */
1155 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1156 0, /* properties_provided */
1157 0, /* properties_destroyed */
1158 0, /* todo_flags_start */
1159 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
1160 /* todo_flags_finish */