2005-05-19 Paul Brook <paul@codesourcery.com>
[official-gcc.git] / gcc / tree-if-conv.c
blobdecd9cde6afec22666fe220b2586d1f84c43af3c
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
10 version.
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
15 for more details.
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
20 02111-1307, USA. */
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'
31 predicate list.
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:
40 INPUT
41 -----
43 # i_23 = PHI <0(0), i_18(10)>;
44 <L0>:;
45 j_15 = A[i_23];
46 if (j_15 > 41) goto <L1>; else goto <L17>;
48 <L17>:;
49 goto <bb 3> (<L3>);
51 <L1>:;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
54 <L3>:;
55 A[i_23] = iftmp.2_4;
56 i_18 = i_23 + 1;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
59 <L19>:;
60 goto <bb 1> (<L0>);
62 <L18>:;
64 OUTPUT
65 ------
67 # i_23 = PHI <0(0), i_18(10)>;
68 <L0>:;
69 j_15 = A[i_23];
71 <L3>:;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
73 A[i_23] = iftmp.2_4;
74 i_18 = i_23 + 1;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
77 <L19>:;
78 goto <bb 1> (<L0>);
80 <L18>:;
83 #include "config.h"
84 #include "system.h"
85 #include "coretypes.h"
86 #include "tm.h"
87 #include "errors.h"
88 #include "tree.h"
89 #include "c-common.h"
90 #include "flags.h"
91 #include "timevar.h"
92 #include "varray.h"
93 #include "rtl.h"
94 #include "basic-block.h"
95 #include "diagnostic.h"
96 #include "tree-flow.h"
97 #include "tree-dump.h"
98 #include "cfgloop.h"
99 #include "tree-chrec.h"
100 #include "tree-data-ref.h"
101 #include "tree-scalar-evolution.h"
102 #include "tree-pass.h"
103 #include "target.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 (struct loop *loop,
121 basic_block, tree *,
122 block_stmt_iterator *);
123 static void replace_phi_with_cond_modify_expr (tree, tree, basic_block,
124 block_stmt_iterator *);
125 static void process_phi_nodes (struct loop *);
126 static void combine_blocks (struct loop *);
127 static tree ifc_temp_var (tree, tree);
128 static bool pred_blocks_visited_p (basic_block, bitmap *);
129 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
130 static bool bb_with_exit_edge_p (struct loop *, basic_block);
132 /* List of basic blocks in if-conversion-suitable order. */
133 static basic_block *ifc_bbs;
135 /* Main entry point.
136 Apply if-conversion to the LOOP. Return true if successful otherwise return
137 false. If false is returned then loop remains unchanged.
138 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
139 for vectorizer or not. If it is used for vectorizer, additional checks are
140 used. (Vectorization checks are not yet implemented). */
142 static bool
143 tree_if_conversion (struct loop *loop, bool for_vectorizer)
145 basic_block bb;
146 block_stmt_iterator itr;
147 tree cond;
148 unsigned int i;
150 ifc_bbs = NULL;
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");
158 if (ifc_bbs)
160 free (ifc_bbs);
161 ifc_bbs = NULL;
163 free_dominance_info (CDI_POST_DOMINATORS);
164 return false;
167 cond = NULL_TREE;
169 /* Do actual work now. */
170 for (i = 0; i < loop->num_nodes; i++)
172 bb = ifc_bbs [i];
174 /* Update condition using predicate list. */
175 cond = bb->aux;
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))
185 bsi_next (&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);
195 cond = NULL_TREE;
199 /* Now, all statements are if-converted and basic blocks are
200 annotated appropriately. Combine all basic block into one huge
201 basic block. */
202 combine_blocks (loop);
204 /* clean up */
205 clean_predicate_lists (loop);
206 free (ifc_bbs);
207 ifc_bbs = NULL;
209 return true;
212 /* if-convert stmt T which is part of LOOP.
213 If T is a MODIFY_EXPR than it is converted into conditional modify
214 expression using COND. For conditional expressions, add condition in the
215 destination basic block's predicate list and remove conditional
216 expression itself. BSI is the iterator used to traverse statements of
217 loop. It is used here when it is required to delete current statement. */
219 static tree
220 tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
221 block_stmt_iterator *bsi)
223 if (dump_file && (dump_flags & TDF_DETAILS))
225 fprintf (dump_file, "------if-convert stmt\n");
226 print_generic_stmt (dump_file, t, TDF_SLIM);
227 print_generic_stmt (dump_file, cond, TDF_SLIM);
230 switch (TREE_CODE (t))
232 /* Labels are harmless here. */
233 case LABEL_EXPR:
234 break;
236 case MODIFY_EXPR:
237 /* This modify_expr is killing previous value of LHS. Appropriate value will
238 be selected by PHI node based on condition. It is possible that before
239 this transformation, PHI nodes was selecting default value and now it will
240 use this new value. This is OK because it does not change validity the
241 program. */
242 break;
244 case COND_EXPR:
245 /* Update destination blocks' predicate list and remove this
246 condition expression. */
247 tree_if_convert_cond_expr (loop, t, cond, bsi);
248 cond = NULL_TREE;
249 break;
251 default:
252 gcc_unreachable ();
254 return cond;
257 /* STMT is COND_EXPR. Update two destination's predicate list.
258 Remove COND_EXPR, if it is not the loop exit condition. Otherwise
259 update loop exit condition appropriately. BSI is the iterator
260 used to traverse statement list. STMT is part of loop LOOP. */
262 static void
263 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
264 block_stmt_iterator *bsi)
266 tree c, c2;
267 edge true_edge, false_edge;
269 gcc_assert (TREE_CODE (stmt) == COND_EXPR);
271 c = COND_EXPR_COND (stmt);
273 extract_true_false_edges_from_block (bb_for_stmt (stmt),
274 &true_edge, &false_edge);
276 /* Add new condition into destination's predicate list. */
278 /* If 'c' is true then TRUE_EDGE is taken. */
279 add_to_dst_predicate_list (loop, true_edge->dest, cond,
280 unshare_expr (c), bsi);
282 /* If 'c' is false then FALSE_EDGE is taken. */
283 c2 = invert_truthvalue (unshare_expr (c));
284 add_to_dst_predicate_list (loop, false_edge->dest, cond, c2, bsi);
286 /* Now this conditional statement is redundant. Remove it.
287 But, do not remove exit condition! Update exit condition
288 using new condition. */
289 if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
291 bsi_remove (bsi);
292 cond = NULL_TREE;
294 return;
297 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
298 and it belongs to basic block BB.
299 PHI is not if-convertible
300 - if it has more than 2 arguments.
301 - Virtual PHI is immediately used in another PHI node. */
303 static bool
304 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
306 if (dump_file && (dump_flags & TDF_DETAILS))
308 fprintf (dump_file, "-------------------------\n");
309 print_generic_stmt (dump_file, phi, TDF_SLIM);
312 if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
314 if (dump_file && (dump_flags & TDF_DETAILS))
315 fprintf (dump_file, "More than two phi node args.\n");
316 return false;
319 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
321 imm_use_iterator imm_iter;
322 use_operand_p use_p;
323 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
325 if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
327 if (dump_file && (dump_flags & TDF_DETAILS))
328 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
329 return false;
334 return true;
337 /* Return true, if M_EXPR is if-convertible.
338 MODIFY_EXPR is not if-convertible if,
339 - It is not movable.
340 - It could trap.
341 - LHS is not var decl.
342 MODIFY_EXPR is part of block BB, which is inside loop LOOP.
345 static bool
346 if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
348 if (dump_file && (dump_flags & TDF_DETAILS))
350 fprintf (dump_file, "-------------------------\n");
351 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
354 /* Be conservative and do not handle immovable expressions. */
355 if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
357 if (dump_file && (dump_flags & TDF_DETAILS))
358 fprintf (dump_file, "stmt is movable. Don't take risk\n");
359 return false;
362 /* See if it needs speculative loading or not. */
363 if (bb != loop->header
364 && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
366 if (dump_file && (dump_flags & TDF_DETAILS))
367 fprintf (dump_file, "tree could trap...\n");
368 return false;
371 if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
373 if (dump_file && (dump_flags & TDF_DETAILS))
374 fprintf (dump_file, "CALL_EXPR \n");
375 return false;
378 if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
379 && bb != loop->header
380 && !bb_with_exit_edge_p (loop, bb))
382 if (dump_file && (dump_flags & TDF_DETAILS))
384 fprintf (dump_file, "LHS is not var\n");
385 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
387 return false;
391 return true;
394 /* Return true, iff STMT is if-convertible.
395 Statement is if-convertible if,
396 - It is if-convertible MODIFY_EXPR
397 - IT is LABEL_EXPR or COND_EXPR.
398 STMT is inside block BB, which is inside loop LOOP. */
400 static bool
401 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
403 switch (TREE_CODE (stmt))
405 case LABEL_EXPR:
406 break;
408 case MODIFY_EXPR:
410 if (!if_convertible_modify_expr_p (loop, bb, stmt))
411 return false;
412 break;
414 case COND_EXPR:
415 break;
417 default:
418 /* Don't know what to do with 'em so don't do anything. */
419 if (dump_file && (dump_flags & TDF_DETAILS))
421 fprintf (dump_file, "don't know what to do\n");
422 print_generic_stmt (dump_file, stmt, TDF_SLIM);
424 return false;
425 break;
428 return true;
431 /* Return true, iff BB is if-convertible.
432 Note: This routine does _not_ check basic block statements and phis.
433 Basic block is not if-convertible if,
434 - Basic block is non-empty and it is after exit block (in BFS order).
435 - Basic block is after exit block but before latch.
436 - Basic block edge(s) is not normal.
437 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
438 BB is inside loop LOOP. */
440 static bool
441 if_convertible_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
443 edge e;
444 edge_iterator ei;
446 if (dump_file && (dump_flags & TDF_DETAILS))
447 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
449 if (exit_bb_seen)
451 if (bb != loop->latch)
453 if (dump_file && (dump_flags & TDF_DETAILS))
454 fprintf (dump_file, "basic block after exit bb but before latch\n");
455 return false;
457 else if (!empty_block_p (bb))
459 if (dump_file && (dump_flags & TDF_DETAILS))
460 fprintf (dump_file, "non empty basic block after exit bb\n");
461 return false;
465 /* Be less adventurous and handle only normal edges. */
466 FOR_EACH_EDGE (e, ei, bb->succs)
467 if (e->flags &
468 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
470 if (dump_file && (dump_flags & TDF_DETAILS))
471 fprintf (dump_file,"Difficult to handle edges\n");
472 return false;
475 return true;
478 /* Return true, iff LOOP is if-convertible.
479 LOOP is if-convertible if,
480 - It is innermost.
481 - It has two or more basic blocks.
482 - It has only one exit.
483 - Loop header is not the exit edge.
484 - If its basic blocks and phi nodes are if convertible. See above for
485 more info.
486 FOR_VECTORIZER enables vectorizer specific checks. For example, support
487 for vector conditions, data dependency checks etc.. (Not implemented yet). */
489 static bool
490 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
492 tree phi;
493 basic_block bb;
494 block_stmt_iterator itr;
495 unsigned int i;
496 edge e;
497 edge_iterator ei;
498 bool exit_bb_seen = false;
500 /* Handle only inner most loop. */
501 if (!loop || loop->inner)
503 if (dump_file && (dump_flags & TDF_DETAILS))
504 fprintf (dump_file, "not inner most loop\n");
505 return false;
508 /* If only one block, no need for if-conversion. */
509 if (loop->num_nodes <= 2)
511 if (dump_file && (dump_flags & TDF_DETAILS))
512 fprintf (dump_file, "less than 2 basic blocks\n");
513 return false;
516 /* More than one loop exit is too much to handle. */
517 if (!loop->single_exit)
519 if (dump_file && (dump_flags & TDF_DETAILS))
520 fprintf (dump_file, "multiple exits\n");
521 return false;
524 /* ??? Check target's vector conditional operation support for vectorizer. */
526 /* If one of the loop header's edge is exit edge then do not apply
527 if-conversion. */
528 FOR_EACH_EDGE (e, ei, loop->header->succs)
530 if (loop_exit_edge_p (loop, e))
531 return false;
534 calculate_dominance_info (CDI_DOMINATORS);
535 calculate_dominance_info (CDI_POST_DOMINATORS);
537 /* Allow statements that can be handled during if-conversion. */
538 ifc_bbs = get_loop_body_in_if_conv_order (loop);
539 if (!ifc_bbs)
541 if (dump_file && (dump_flags & TDF_DETAILS))
542 fprintf (dump_file,"Irreducible loop\n");
543 free_dominance_info (CDI_POST_DOMINATORS);
544 return false;
547 for (i = 0; i < loop->num_nodes; i++)
549 bb = ifc_bbs[i];
551 if (!if_convertible_bb_p (loop, bb, exit_bb_seen))
552 return false;
554 /* Check statements. */
555 for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
556 if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
557 return false;
558 /* ??? Check data dependency for vectorizer. */
560 /* What about phi nodes ? */
561 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
562 if (!if_convertible_phi_p (loop, bb, phi))
563 return false;
565 if (bb_with_exit_edge_p (loop, bb))
566 exit_bb_seen = true;
569 /* OK. Did not find any potential issues so go ahead in if-convert
570 this loop. Now there is no looking back. */
571 if (dump_file)
572 fprintf (dump_file,"Applying if-conversion\n");
574 free_dominance_info (CDI_POST_DOMINATORS);
575 return true;
578 /* Add condition COND into predicate list of basic block BB. */
580 static void
581 add_to_predicate_list (basic_block bb, tree new_cond)
583 tree cond = bb->aux;
585 if (cond)
586 cond = fold (build (TRUTH_OR_EXPR, boolean_type_node,
587 unshare_expr (cond), new_cond));
588 else
589 cond = new_cond;
591 bb->aux = cond;
594 /* Add condition COND into BB's predicate list. PREV_COND is
595 existing condition. */
597 static tree
598 add_to_dst_predicate_list (struct loop * loop, basic_block bb,
599 tree prev_cond, tree cond,
600 block_stmt_iterator *bsi)
602 tree new_cond = NULL_TREE;
604 if (!flow_bb_inside_loop_p (loop, bb))
605 return NULL_TREE;
607 if (prev_cond == boolean_true_node || !prev_cond)
608 new_cond = unshare_expr (cond);
609 else
611 tree tmp;
612 tree tmp_stmt = NULL_TREE;
613 tree tmp_stmts1 = NULL_TREE;
614 tree tmp_stmts2 = NULL_TREE;
615 prev_cond = force_gimple_operand (unshare_expr (prev_cond),
616 &tmp_stmts1, true, NULL);
617 if (tmp_stmts1)
618 bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
620 cond = force_gimple_operand (unshare_expr (cond),
621 &tmp_stmts2, true, NULL);
622 if (tmp_stmts2)
623 bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
625 /* new_cond == prev_cond AND cond */
626 tmp = build (TRUTH_AND_EXPR, boolean_type_node,
627 unshare_expr (prev_cond), cond);
628 tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
629 bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
630 new_cond = TREE_OPERAND (tmp_stmt, 0);
632 add_to_predicate_list (bb, new_cond);
633 return new_cond;
636 /* During if-conversion aux field from basic block is used to hold predicate
637 list. Clean each basic block's predicate list for the given LOOP. */
639 static void
640 clean_predicate_lists (struct loop *loop)
642 basic_block *bb;
643 unsigned int i;
644 bb = get_loop_body (loop);
645 for (i = 0; i < loop->num_nodes; i++)
646 bb[i]->aux = NULL;
648 free (bb);
651 /* Basic block BB has two predecessors. Using predecessor's aux field, set
652 appropriate condition COND for the PHI node replacement. Return true block
653 whose phi arguments are selected when cond is true. */
655 static basic_block
656 find_phi_replacement_condition (struct loop *loop,
657 basic_block bb, tree *cond,
658 block_stmt_iterator *bsi)
660 basic_block first_bb = NULL;
661 basic_block second_bb = NULL;
662 tree tmp_cond;
664 gcc_assert (EDGE_COUNT (bb->preds) == 2);
665 first_bb = (EDGE_PRED (bb, 0))->src;
666 second_bb = (EDGE_PRED (bb, 1))->src;
668 /* Use condition based on following criteria:
670 S1: x = !c ? a : b;
672 S2: x = c ? b : a;
674 S2 is preferred over S1. Make 'b' first_bb and use its condition.
676 2) Do not make loop header first_bb.
679 S1: x = !(c == d)? a : b;
681 S21: t1 = c == d;
682 S22: x = t1 ? b : a;
684 S3: x = (c == d) ? b : a;
686 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
687 its condition. */
689 /* Select condition that is not TRUTH_NOT_EXPR. */
690 tmp_cond = first_bb->aux;
691 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
693 basic_block tmp_bb;
694 tmp_bb = first_bb;
695 first_bb = second_bb;
696 second_bb = tmp_bb;
699 /* Check if FIRST_BB is loop header or not. */
700 if (first_bb == loop->header)
702 tmp_cond = second_bb->aux;
703 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
705 /* Select non loop header condition but do not switch basic blocks. */
706 *cond = invert_truthvalue (unshare_expr (tmp_cond));
708 else
710 /* Select non loop header condition. */
711 first_bb = second_bb;
712 *cond = first_bb->aux;
715 else
716 /* FIRST_BB is not loop header */
717 *cond = first_bb->aux;
719 /* Create temp. for the condition. Vectorizer prefers to have gimple
720 value as condition. Various targets use different means to communicate
721 condition in vector compare operation. Using gimple value allows compiler
722 to emit vector compare and select RTL without exposing compare's result. */
723 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
725 tree new_stmt;
727 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
728 bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
729 bsi_next (bsi);
730 *cond = TREE_OPERAND (new_stmt, 0);
733 gcc_assert (*cond);
735 return first_bb;
739 /* Replace PHI node with conditional modify expr using COND.
740 This routine does not handle PHI nodes with more than two arguments.
741 For example,
742 S1: A = PHI <x1(1), x2(5)
743 is converted into,
744 S2: A = cond ? x1 : x2;
745 S2 is inserted at the top of basic block's statement list.
746 When COND is true, phi arg from TRUE_BB is selected.
749 static void
750 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
751 block_stmt_iterator *bsi)
753 tree new_stmt;
754 basic_block bb;
755 tree rhs;
756 tree arg_0, arg_1;
758 gcc_assert (TREE_CODE (phi) == PHI_NODE);
760 /* If this is not filtered earlier, then now it is too late. */
761 gcc_assert (PHI_NUM_ARGS (phi) == 2);
763 /* Find basic block and initialize iterator. */
764 bb = bb_for_stmt (phi);
766 new_stmt = NULL_TREE;
767 arg_0 = NULL_TREE;
768 arg_1 = NULL_TREE;
770 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
771 if (EDGE_PRED (bb, 1)->src == true_bb)
773 arg_0 = PHI_ARG_DEF (phi, 1);
774 arg_1 = PHI_ARG_DEF (phi, 0);
776 else
778 arg_0 = PHI_ARG_DEF (phi, 0);
779 arg_1 = PHI_ARG_DEF (phi, 1);
782 /* Build new RHS using selected condition and arguments. */
783 rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
784 unshare_expr (cond), unshare_expr (arg_0),
785 unshare_expr (arg_1));
787 /* Create new MODIFY expression using RHS. */
788 new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
789 unshare_expr (PHI_RESULT (phi)), rhs);
791 /* Make new statement definition of the original phi result. */
792 SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
794 /* Insert using iterator. */
795 bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
796 bsi_next (bsi);
798 update_stmt (new_stmt);
800 if (dump_file && (dump_flags & TDF_DETAILS))
802 fprintf (dump_file, "new phi replacement stmt\n");
803 print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
807 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
808 modify expr. */
810 static void
811 process_phi_nodes (struct loop *loop)
813 basic_block bb;
814 unsigned int orig_loop_num_nodes = loop->num_nodes;
815 unsigned int i;
817 /* Replace phi nodes with cond. modify expr. */
818 for (i = 1; i < orig_loop_num_nodes; i++)
820 tree phi, cond;
821 block_stmt_iterator bsi;
822 basic_block true_bb = NULL;
823 bb = ifc_bbs[i];
825 if (bb == loop->header)
826 continue;
828 phi = phi_nodes (bb);
829 bsi = bsi_after_labels (bb);
831 /* BB has two predecessors. Using predecessor's aux field, set
832 appropriate condition for the PHI node replacement. */
833 if (phi)
834 true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
836 while (phi)
838 tree next = PHI_CHAIN (phi);
839 replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
840 release_phi_node (phi);
841 phi = next;
843 bb_ann (bb)->phi_nodes = NULL;
845 return;
848 /* Combine all basic block from the given LOOP into one or two super
849 basic block. Replace PHI nodes with conditional modify expression. */
851 static void
852 combine_blocks (struct loop *loop)
854 basic_block bb, exit_bb, merge_target_bb;
855 unsigned int orig_loop_num_nodes = loop->num_nodes;
856 unsigned int i;
857 unsigned int n_exits;
859 get_loop_exit_edges (loop, &n_exits);
860 /* Process phi nodes to prepare blocks for merge. */
861 process_phi_nodes (loop);
863 exit_bb = NULL;
865 /* Merge basic blocks */
866 merge_target_bb = loop->header;
867 for (i = 1; i < orig_loop_num_nodes; i++)
869 edge e;
870 block_stmt_iterator bsi;
871 tree_stmt_iterator last;
873 bb = ifc_bbs[i];
875 if (!exit_bb && bb_with_exit_edge_p (loop, bb))
876 exit_bb = bb;
878 if (bb == exit_bb)
880 edge_iterator ei;
882 /* Connect this node with loop header. */
883 make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
884 set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
886 if (exit_bb != loop->latch)
888 /* Redirect non-exit edge to loop->latch. */
889 FOR_EACH_EDGE (e, ei, bb->succs)
891 if (!loop_exit_edge_p (loop, e))
893 redirect_edge_and_branch (e, loop->latch);
894 set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
898 continue;
901 if (bb == loop->latch && empty_block_p (bb))
902 continue;
904 /* It is time to remove this basic block. First remove edges. */
905 while (EDGE_COUNT (bb->preds) > 0)
906 remove_edge (EDGE_PRED (bb, 0));
908 /* This is loop latch and loop does not have exit then do not
909 delete this basic block. Just remove its PREDS and reconnect
910 loop->header and loop->latch blocks. */
911 if (bb == loop->latch && n_exits == 0)
913 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
914 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
915 continue;
918 while (EDGE_COUNT (bb->succs) > 0)
919 remove_edge (EDGE_SUCC (bb, 0));
921 /* Remove labels and make stmts member of loop->header. */
922 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
924 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
925 bsi_remove (&bsi);
926 else
928 set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
929 bsi_next (&bsi);
933 /* Update stmt list. */
934 last = tsi_last (merge_target_bb->stmt_list);
935 tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
936 bb->stmt_list = NULL;
938 /* Update dominator info. */
939 if (dom_computed[CDI_DOMINATORS])
940 delete_from_dominance_info (CDI_DOMINATORS, bb);
941 if (dom_computed[CDI_POST_DOMINATORS])
942 delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
944 /* Remove basic block. */
945 if (bb == loop->latch)
946 loop->latch = merge_target_bb;
947 remove_bb_from_loops (bb);
948 expunge_block (bb);
951 /* Now if possible, merge loop header and block with exit edge.
952 This reduces number of basic blocks to 2. Auto vectorizer addresses
953 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
954 if (exit_bb
955 && loop->header != loop->latch
956 && exit_bb != loop->latch
957 && empty_block_p (loop->latch))
959 if (can_merge_blocks_p (loop->header, exit_bb))
961 remove_bb_from_loops (exit_bb);
962 merge_blocks (loop->header, exit_bb);
967 /* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
968 to the new variable. */
970 static tree
971 ifc_temp_var (tree type, tree exp)
973 const char *name = "_ifc_";
974 tree var, stmt, new_name;
976 if (is_gimple_reg (exp))
977 return exp;
979 /* Create new temporary variable. */
980 var = create_tmp_var (type, name);
981 add_referenced_tmp_var (var);
983 /* Build new statement to assign EXP to new variable. */
984 stmt = build (MODIFY_EXPR, type, var, exp);
986 /* Get SSA name for the new variable and set make new statement
987 its definition statement. */
988 new_name = make_ssa_name (var, stmt);
989 TREE_OPERAND (stmt, 0) = new_name;
990 SSA_NAME_DEF_STMT (new_name) = stmt;
992 return stmt;
996 /* Return TRUE iff, all pred blocks of BB are visited.
997 Bitmap VISITED keeps history of visited blocks. */
999 static bool
1000 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1002 edge e;
1003 edge_iterator ei;
1004 FOR_EACH_EDGE (e, ei, bb->preds)
1005 if (!bitmap_bit_p (*visited, e->src->index))
1006 return false;
1008 return true;
1011 /* Get body of a LOOP in suitable order for if-conversion.
1012 It is caller's responsibility to deallocate basic block
1013 list. If-conversion suitable order is, BFS order with one
1014 additional constraint. Select block in BFS block, if all
1015 pred are already selected. */
1017 static basic_block *
1018 get_loop_body_in_if_conv_order (const struct loop *loop)
1020 basic_block *blocks, *blocks_in_bfs_order;
1021 basic_block bb;
1022 bitmap visited;
1023 unsigned int index = 0;
1024 unsigned int visited_count = 0;
1026 gcc_assert (loop->num_nodes);
1027 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1029 blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
1030 visited = BITMAP_ALLOC (NULL);
1032 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1034 index = 0;
1035 while (index < loop->num_nodes)
1037 bb = blocks_in_bfs_order [index];
1039 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1041 free (blocks_in_bfs_order);
1042 BITMAP_FREE (visited);
1043 free (blocks);
1044 return NULL;
1046 if (!bitmap_bit_p (visited, bb->index))
1048 if (pred_blocks_visited_p (bb, &visited)
1049 || bb == loop->header)
1051 /* This block is now visited. */
1052 bitmap_set_bit (visited, bb->index);
1053 blocks[visited_count++] = bb;
1056 index++;
1057 if (index == loop->num_nodes
1058 && visited_count != loop->num_nodes)
1060 /* Not done yet. */
1061 index = 0;
1064 free (blocks_in_bfs_order);
1065 BITMAP_FREE (visited);
1066 return blocks;
1069 /* Return true if one of the basic block BB edge is exit of LOOP. */
1071 static bool
1072 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1074 edge e;
1075 edge_iterator ei;
1076 bool exit_edge_found = false;
1078 FOR_EACH_EDGE (e, ei, bb->succs)
1079 if (loop_exit_edge_p (loop, e))
1081 exit_edge_found = true;
1082 break;
1085 return exit_edge_found;
1088 /* Tree if-conversion pass management. */
1090 static void
1091 main_tree_if_conversion (void)
1093 unsigned i, loop_num;
1094 struct loop *loop;
1096 if (!current_loops)
1097 return;
1099 loop_num = current_loops->num;
1100 for (i = 0; i < loop_num; i++)
1102 loop = current_loops->parray[i];
1103 if (!loop)
1104 continue;
1106 tree_if_conversion (loop, true);
1111 static bool
1112 gate_tree_if_conversion (void)
1114 return flag_tree_vectorize != 0;
1117 struct tree_opt_pass pass_if_conversion =
1119 "ifcvt", /* name */
1120 gate_tree_if_conversion, /* gate */
1121 main_tree_if_conversion, /* execute */
1122 NULL, /* sub */
1123 NULL, /* next */
1124 0, /* static_pass_number */
1125 0, /* tv_id */
1126 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1127 0, /* properties_provided */
1128 0, /* properties_destroyed */
1129 0, /* todo_flags_start */
1130 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
1131 /* todo_flags_finish */
1132 0 /* letter */