Parallelize in_ifaddrhead operation
[dragonfly.git] / contrib / gcc-4.1 / gcc / tree-if-conv.c
blob6643d5b65ad9bf8b572d6d418b05dac8a5e12632
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, 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 "tree.h"
88 #include "c-common.h"
89 #include "flags.h"
90 #include "timevar.h"
91 #include "varray.h"
92 #include "rtl.h"
93 #include "basic-block.h"
94 #include "diagnostic.h"
95 #include "tree-flow.h"
96 #include "tree-dump.h"
97 #include "cfgloop.h"
98 #include "tree-chrec.h"
99 #include "tree-data-ref.h"
100 #include "tree-scalar-evolution.h"
101 #include "tree-pass.h"
102 #include "target.h"
104 /* local function prototypes */
105 static void 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_modify_expr_p (struct loop *, basic_block, tree);
112 static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
113 static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
114 static bool if_convertible_loop_p (struct loop *, bool);
115 static void add_to_predicate_list (basic_block, tree);
116 static tree add_to_dst_predicate_list (struct loop * loop, basic_block, tree, tree,
117 block_stmt_iterator *);
118 static void clean_predicate_lists (struct loop *loop);
119 static basic_block find_phi_replacement_condition (struct loop *loop,
120 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;
134 /* Main entry point.
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). */
141 static bool
142 tree_if_conversion (struct loop *loop, bool for_vectorizer)
144 basic_block bb;
145 block_stmt_iterator itr;
146 tree cond;
147 unsigned int i;
149 ifc_bbs = NULL;
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");
157 if (ifc_bbs)
159 free (ifc_bbs);
160 ifc_bbs = NULL;
162 free_dominance_info (CDI_POST_DOMINATORS);
163 return false;
166 cond = NULL_TREE;
168 /* Do actual work now. */
169 for (i = 0; i < loop->num_nodes; i++)
171 bb = ifc_bbs [i];
173 /* Update condition using predicate list. */
174 cond = bb->aux;
176 /* Process all statements in this basic block.
177 Remove conditional expression, if any, and annotate
178 destination basic block(s) appropriately. */
179 for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
181 tree t = bsi_stmt (itr);
182 cond = tree_if_convert_stmt (loop, t, cond, &itr);
183 if (!bsi_end_p (itr))
184 bsi_next (&itr);
187 /* If current bb has only one successor, then consider it as an
188 unconditional goto. */
189 if (single_succ_p (bb))
191 basic_block bb_n = single_succ (bb);
192 if (cond != NULL_TREE)
193 add_to_predicate_list (bb_n, cond);
194 cond = NULL_TREE;
198 /* Now, all statements are if-converted and basic blocks are
199 annotated appropriately. Combine all basic block into one huge
200 basic block. */
201 combine_blocks (loop);
203 /* clean up */
204 clean_predicate_lists (loop);
205 free (ifc_bbs);
206 ifc_bbs = NULL;
208 return true;
211 /* if-convert stmt T which is part of LOOP.
212 If T is a MODIFY_EXPR 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. */
218 static tree
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. */
232 case LABEL_EXPR:
233 break;
235 case MODIFY_EXPR:
236 /* This modify_expr is killing previous value of LHS. Appropriate value will
237 be selected by PHI node based on condition. It is possible that before
238 this transformation, PHI nodes was selecting default value and now it will
239 use this new value. This is OK because it does not change validity the
240 program. */
241 break;
243 case COND_EXPR:
244 /* Update destination blocks' predicate list and remove this
245 condition expression. */
246 tree_if_convert_cond_expr (loop, t, cond, bsi);
247 cond = NULL_TREE;
248 break;
250 default:
251 gcc_unreachable ();
253 return cond;
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. */
261 static void
262 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
263 block_stmt_iterator *bsi)
265 tree c, c2;
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->dest, 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->dest, 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);
291 cond = NULL_TREE;
293 return;
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. */
302 static bool
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");
315 return false;
318 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
320 imm_use_iterator imm_iter;
321 use_operand_p use_p;
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");
328 return false;
333 return true;
336 /* Return true, if M_EXPR is if-convertible.
337 MODIFY_EXPR is not if-convertible if,
338 - It is not movable.
339 - It could trap.
340 - LHS is not var decl.
341 MODIFY_EXPR is part of block BB, which is inside loop LOOP.
344 static bool
345 if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
347 if (dump_file && (dump_flags & TDF_DETAILS))
349 fprintf (dump_file, "-------------------------\n");
350 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
353 /* Be conservative and do not handle immovable expressions. */
354 if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
356 if (dump_file && (dump_flags & TDF_DETAILS))
357 fprintf (dump_file, "stmt is movable. Don't take risk\n");
358 return false;
361 /* See if it needs speculative loading or not. */
362 if (bb != loop->header
363 && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
365 if (dump_file && (dump_flags & TDF_DETAILS))
366 fprintf (dump_file, "tree could trap...\n");
367 return false;
370 if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
372 if (dump_file && (dump_flags & TDF_DETAILS))
373 fprintf (dump_file, "CALL_EXPR \n");
374 return false;
377 if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
378 && bb != loop->header
379 && !bb_with_exit_edge_p (loop, bb))
381 if (dump_file && (dump_flags & TDF_DETAILS))
383 fprintf (dump_file, "LHS is not var\n");
384 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
386 return false;
390 return true;
393 /* Return true, iff STMT is if-convertible.
394 Statement is if-convertible if,
395 - It is if-convertible MODIFY_EXPR
396 - IT is LABEL_EXPR or COND_EXPR.
397 STMT is inside block BB, which is inside loop LOOP. */
399 static bool
400 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
402 switch (TREE_CODE (stmt))
404 case LABEL_EXPR:
405 break;
407 case MODIFY_EXPR:
409 if (!if_convertible_modify_expr_p (loop, bb, stmt))
410 return false;
411 break;
413 case COND_EXPR:
414 break;
416 default:
417 /* Don't know what to do with 'em so don't do anything. */
418 if (dump_file && (dump_flags & TDF_DETAILS))
420 fprintf (dump_file, "don't know what to do\n");
421 print_generic_stmt (dump_file, stmt, TDF_SLIM);
423 return false;
424 break;
427 return true;
430 /* Return true, iff BB is if-convertible.
431 Note: This routine does _not_ check basic block statements and phis.
432 Basic block is not if-convertible if,
433 - Basic block is non-empty and it is after exit block (in BFS order).
434 - Basic block is after exit block but before latch.
435 - Basic block edge(s) is not normal.
436 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
437 BB is inside loop LOOP. */
439 static bool
440 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
442 edge e;
443 edge_iterator ei;
445 if (dump_file && (dump_flags & TDF_DETAILS))
446 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
448 if (exit_bb)
450 if (bb != loop->latch)
452 if (dump_file && (dump_flags & TDF_DETAILS))
453 fprintf (dump_file, "basic block after exit bb but before latch\n");
454 return false;
456 else if (!empty_block_p (bb))
458 if (dump_file && (dump_flags & TDF_DETAILS))
459 fprintf (dump_file, "non empty basic block after exit bb\n");
460 return false;
462 else if (bb == loop->latch
463 && bb != exit_bb
464 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
466 if (dump_file && (dump_flags & TDF_DETAILS))
467 fprintf (dump_file, "latch is not dominated by exit_block\n");
468 return false;
472 /* Be less adventurous and handle only normal edges. */
473 FOR_EACH_EDGE (e, ei, bb->succs)
474 if (e->flags &
475 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
477 if (dump_file && (dump_flags & TDF_DETAILS))
478 fprintf (dump_file,"Difficult to handle edges\n");
479 return false;
482 return true;
485 /* Return true, iff LOOP is if-convertible.
486 LOOP is if-convertible if,
487 - It is innermost.
488 - It has two or more basic blocks.
489 - It has only one exit.
490 - Loop header is not the exit edge.
491 - If its basic blocks and phi nodes are if convertible. See above for
492 more info.
493 FOR_VECTORIZER enables vectorizer specific checks. For example, support
494 for vector conditions, data dependency checks etc.. (Not implemented yet). */
496 static bool
497 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
499 tree phi;
500 basic_block bb;
501 block_stmt_iterator itr;
502 unsigned int i;
503 edge e;
504 edge_iterator ei;
505 basic_block exit_bb = NULL;
507 /* Handle only inner most loop. */
508 if (!loop || loop->inner)
510 if (dump_file && (dump_flags & TDF_DETAILS))
511 fprintf (dump_file, "not inner most loop\n");
512 return false;
515 /* If only one block, no need for if-conversion. */
516 if (loop->num_nodes <= 2)
518 if (dump_file && (dump_flags & TDF_DETAILS))
519 fprintf (dump_file, "less than 2 basic blocks\n");
520 return false;
523 /* More than one loop exit is too much to handle. */
524 if (!loop->single_exit)
526 if (dump_file && (dump_flags & TDF_DETAILS))
527 fprintf (dump_file, "multiple exits\n");
528 return false;
531 /* ??? Check target's vector conditional operation support for vectorizer. */
533 /* If one of the loop header's edge is exit edge then do not apply
534 if-conversion. */
535 FOR_EACH_EDGE (e, ei, loop->header->succs)
537 if (loop_exit_edge_p (loop, e))
538 return false;
541 calculate_dominance_info (CDI_DOMINATORS);
542 calculate_dominance_info (CDI_POST_DOMINATORS);
544 /* Allow statements that can be handled during if-conversion. */
545 ifc_bbs = get_loop_body_in_if_conv_order (loop);
546 if (!ifc_bbs)
548 if (dump_file && (dump_flags & TDF_DETAILS))
549 fprintf (dump_file,"Irreducible loop\n");
550 free_dominance_info (CDI_POST_DOMINATORS);
551 return false;
554 for (i = 0; i < loop->num_nodes; i++)
556 bb = ifc_bbs[i];
558 if (!if_convertible_bb_p (loop, bb, exit_bb))
559 return false;
561 /* Check statements. */
562 for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
563 if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
564 return false;
565 /* ??? Check data dependency for vectorizer. */
567 /* What about phi nodes ? */
568 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
569 if (!if_convertible_phi_p (loop, bb, phi))
570 return false;
572 if (bb_with_exit_edge_p (loop, bb))
573 exit_bb = bb;
576 /* OK. Did not find any potential issues so go ahead in if-convert
577 this loop. Now there is no looking back. */
578 if (dump_file)
579 fprintf (dump_file,"Applying if-conversion\n");
581 free_dominance_info (CDI_POST_DOMINATORS);
582 return true;
585 /* Add condition COND into predicate list of basic block BB. */
587 static void
588 add_to_predicate_list (basic_block bb, tree new_cond)
590 tree cond = bb->aux;
592 if (cond)
593 cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
594 unshare_expr (cond), new_cond);
595 else
596 cond = new_cond;
598 bb->aux = cond;
601 /* Add condition COND into BB's predicate list. PREV_COND is
602 existing condition. */
604 static tree
605 add_to_dst_predicate_list (struct loop * loop, basic_block bb,
606 tree prev_cond, tree cond,
607 block_stmt_iterator *bsi)
609 tree new_cond = NULL_TREE;
611 if (!flow_bb_inside_loop_p (loop, bb))
612 return NULL_TREE;
614 if (prev_cond == boolean_true_node || !prev_cond)
615 new_cond = unshare_expr (cond);
616 else
618 tree tmp;
619 tree tmp_stmt = NULL_TREE;
620 tree tmp_stmts1 = NULL_TREE;
621 tree tmp_stmts2 = NULL_TREE;
622 prev_cond = force_gimple_operand (unshare_expr (prev_cond),
623 &tmp_stmts1, true, NULL);
624 if (tmp_stmts1)
625 bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
627 cond = force_gimple_operand (unshare_expr (cond),
628 &tmp_stmts2, true, NULL);
629 if (tmp_stmts2)
630 bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
632 /* new_cond == prev_cond AND cond */
633 tmp = build (TRUTH_AND_EXPR, boolean_type_node,
634 unshare_expr (prev_cond), cond);
635 tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
636 bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
637 new_cond = TREE_OPERAND (tmp_stmt, 0);
639 add_to_predicate_list (bb, new_cond);
640 return new_cond;
643 /* During if-conversion aux field from basic block is used to hold predicate
644 list. Clean each basic block's predicate list for the given LOOP. */
646 static void
647 clean_predicate_lists (struct loop *loop)
649 basic_block *bb;
650 unsigned int i;
651 bb = get_loop_body (loop);
652 for (i = 0; i < loop->num_nodes; i++)
653 bb[i]->aux = NULL;
655 free (bb);
658 /* Basic block BB has two predecessors. Using predecessor's aux field, set
659 appropriate condition COND for the PHI node replacement. Return true block
660 whose phi arguments are selected when cond is true. */
662 static basic_block
663 find_phi_replacement_condition (struct loop *loop,
664 basic_block bb, tree *cond,
665 block_stmt_iterator *bsi)
667 basic_block first_bb = NULL;
668 basic_block second_bb = NULL;
669 tree tmp_cond, new_stmts;
671 gcc_assert (EDGE_COUNT (bb->preds) == 2);
672 first_bb = (EDGE_PRED (bb, 0))->src;
673 second_bb = (EDGE_PRED (bb, 1))->src;
675 /* Use condition based on following criteria:
677 S1: x = !c ? a : b;
679 S2: x = c ? b : a;
681 S2 is preferred over S1. Make 'b' first_bb and use its condition.
683 2) Do not make loop header first_bb.
686 S1: x = !(c == d)? a : b;
688 S21: t1 = c == d;
689 S22: x = t1 ? b : a;
691 S3: x = (c == d) ? b : a;
693 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
694 its condition.
696 4) If pred B is dominated by pred A then use pred B's condition.
697 See PR23115. */
699 /* Select condition that is not TRUTH_NOT_EXPR. */
700 tmp_cond = first_bb->aux;
701 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
703 basic_block tmp_bb;
704 tmp_bb = first_bb;
705 first_bb = second_bb;
706 second_bb = tmp_bb;
709 /* Check if FIRST_BB is loop header or not and make sure that
710 FIRST_BB does not dominate SECOND_BB. */
711 if (first_bb == loop->header
712 || dominated_by_p (CDI_DOMINATORS, second_bb, first_bb))
714 tmp_cond = second_bb->aux;
715 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
717 /* Select non loop header condition but do not switch basic blocks. */
718 *cond = invert_truthvalue (unshare_expr (tmp_cond));
720 else
722 /* Select non loop header condition. */
723 first_bb = second_bb;
724 *cond = first_bb->aux;
727 else
728 /* FIRST_BB is not loop header */
729 *cond = first_bb->aux;
731 /* Create temp. for the condition. Vectorizer prefers to have gimple
732 value as condition. Various targets use different means to communicate
733 condition in vector compare operation. Using gimple value allows compiler
734 to emit vector compare and select RTL without exposing compare's result. */
735 *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE);
736 if (new_stmts)
737 bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
738 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
740 tree new_stmt;
742 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
743 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
744 *cond = TREE_OPERAND (new_stmt, 0);
747 gcc_assert (*cond);
749 return first_bb;
753 /* Replace PHI node with conditional modify expr using COND.
754 This routine does not handle PHI nodes with more than two arguments.
755 For example,
756 S1: A = PHI <x1(1), x2(5)
757 is converted into,
758 S2: A = cond ? x1 : x2;
759 S2 is inserted at the top of basic block's statement list.
760 When COND is true, phi arg from TRUE_BB is selected.
763 static void
764 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
765 block_stmt_iterator *bsi)
767 tree new_stmt;
768 basic_block bb;
769 tree rhs;
770 tree arg_0, arg_1;
772 gcc_assert (TREE_CODE (phi) == PHI_NODE);
774 /* If this is not filtered earlier, then now it is too late. */
775 gcc_assert (PHI_NUM_ARGS (phi) == 2);
777 /* Find basic block and initialize iterator. */
778 bb = bb_for_stmt (phi);
780 new_stmt = NULL_TREE;
781 arg_0 = NULL_TREE;
782 arg_1 = NULL_TREE;
784 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
785 if (EDGE_PRED (bb, 1)->src == true_bb)
787 arg_0 = PHI_ARG_DEF (phi, 1);
788 arg_1 = PHI_ARG_DEF (phi, 0);
790 else
792 arg_0 = PHI_ARG_DEF (phi, 0);
793 arg_1 = PHI_ARG_DEF (phi, 1);
796 /* Build new RHS using selected condition and arguments. */
797 rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
798 unshare_expr (cond), unshare_expr (arg_0),
799 unshare_expr (arg_1));
801 /* Create new MODIFY expression using RHS. */
802 new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
803 unshare_expr (PHI_RESULT (phi)), rhs);
805 /* Make new statement definition of the original phi result. */
806 SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
808 /* Insert using iterator. */
809 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
810 update_stmt (new_stmt);
812 if (dump_file && (dump_flags & TDF_DETAILS))
814 fprintf (dump_file, "new phi replacement stmt\n");
815 print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
819 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
820 modify expr. */
822 static void
823 process_phi_nodes (struct loop *loop)
825 basic_block bb;
826 unsigned int orig_loop_num_nodes = loop->num_nodes;
827 unsigned int i;
829 /* Replace phi nodes with cond. modify expr. */
830 for (i = 1; i < orig_loop_num_nodes; i++)
832 tree phi, cond;
833 block_stmt_iterator bsi;
834 basic_block true_bb = NULL;
835 bb = ifc_bbs[i];
837 if (bb == loop->header)
838 continue;
840 phi = phi_nodes (bb);
841 bsi = bsi_after_labels (bb);
843 /* BB has two predecessors. Using predecessor's aux field, set
844 appropriate condition for the PHI node replacement. */
845 if (phi)
846 true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
848 while (phi)
850 tree next = PHI_CHAIN (phi);
851 replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
852 release_phi_node (phi);
853 phi = next;
855 bb->phi_nodes = NULL;
857 return;
860 /* Combine all basic block from the given LOOP into one or two super
861 basic block. Replace PHI nodes with conditional modify expression. */
863 static void
864 combine_blocks (struct loop *loop)
866 basic_block bb, exit_bb, merge_target_bb;
867 unsigned int orig_loop_num_nodes = loop->num_nodes;
868 unsigned int i;
869 edge e;
870 edge_iterator ei;
872 /* Process phi nodes to prepare blocks for merge. */
873 process_phi_nodes (loop);
875 /* Merge basic blocks. First remove all the edges in the loop, except
876 for those from the exit block. */
877 exit_bb = NULL;
878 for (i = 0; i < orig_loop_num_nodes; i++)
880 bb = ifc_bbs[i];
881 if (bb_with_exit_edge_p (loop, bb))
883 exit_bb = bb;
884 break;
887 gcc_assert (exit_bb != loop->latch);
889 for (i = 1; i < orig_loop_num_nodes; i++)
891 bb = ifc_bbs[i];
893 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
895 if (e->src == exit_bb)
896 ei_next (&ei);
897 else
898 remove_edge (e);
902 if (exit_bb != NULL)
904 if (exit_bb != loop->header)
906 /* Connect this node with loop header. */
907 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
908 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
911 /* Redirect non-exit edges to loop->latch. */
912 FOR_EACH_EDGE (e, ei, exit_bb->succs)
914 if (!loop_exit_edge_p (loop, e))
915 redirect_edge_and_branch (e, loop->latch);
917 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
919 else
921 /* If the loop does not have exit then reconnect header and latch. */
922 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
923 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
926 merge_target_bb = loop->header;
927 for (i = 1; i < orig_loop_num_nodes; i++)
929 block_stmt_iterator bsi;
930 tree_stmt_iterator last;
932 bb = ifc_bbs[i];
934 if (bb == exit_bb || bb == loop->latch)
935 continue;
937 /* Remove labels and make stmts member of loop->header. */
938 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
940 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
941 bsi_remove (&bsi);
942 else
944 set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
945 bsi_next (&bsi);
949 /* Update stmt list. */
950 last = tsi_last (merge_target_bb->stmt_list);
951 tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
952 bb->stmt_list = NULL;
954 /* Update dominator info. */
955 if (dom_computed[CDI_DOMINATORS])
956 delete_from_dominance_info (CDI_DOMINATORS, bb);
957 if (dom_computed[CDI_POST_DOMINATORS])
958 delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
960 /* Remove basic block. */
961 remove_bb_from_loops (bb);
962 expunge_block (bb);
965 /* Now if possible, merge loop header and block with exit edge.
966 This reduces number of basic blocks to 2. Auto vectorizer addresses
967 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
968 if (exit_bb
969 && exit_bb != loop->header
970 && can_merge_blocks_p (loop->header, exit_bb))
972 remove_bb_from_loops (exit_bb);
973 merge_blocks (loop->header, exit_bb);
977 /* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
978 to the new variable. */
980 static tree
981 ifc_temp_var (tree type, tree exp)
983 const char *name = "_ifc_";
984 tree var, stmt, new_name;
986 if (is_gimple_reg (exp))
987 return exp;
989 /* Create new temporary variable. */
990 var = create_tmp_var (type, name);
991 add_referenced_tmp_var (var);
993 /* Build new statement to assign EXP to new variable. */
994 stmt = build (MODIFY_EXPR, type, var, exp);
996 /* Get SSA name for the new variable and set make new statement
997 its definition statement. */
998 new_name = make_ssa_name (var, stmt);
999 TREE_OPERAND (stmt, 0) = new_name;
1000 SSA_NAME_DEF_STMT (new_name) = stmt;
1002 return stmt;
1006 /* Return TRUE iff, all pred blocks of BB are visited.
1007 Bitmap VISITED keeps history of visited blocks. */
1009 static bool
1010 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1012 edge e;
1013 edge_iterator ei;
1014 FOR_EACH_EDGE (e, ei, bb->preds)
1015 if (!bitmap_bit_p (*visited, e->src->index))
1016 return false;
1018 return true;
1021 /* Get body of a LOOP in suitable order for if-conversion.
1022 It is caller's responsibility to deallocate basic block
1023 list. If-conversion suitable order is, BFS order with one
1024 additional constraint. Select block in BFS block, if all
1025 pred are already selected. */
1027 static basic_block *
1028 get_loop_body_in_if_conv_order (const struct loop *loop)
1030 basic_block *blocks, *blocks_in_bfs_order;
1031 basic_block bb;
1032 bitmap visited;
1033 unsigned int index = 0;
1034 unsigned int visited_count = 0;
1036 gcc_assert (loop->num_nodes);
1037 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1039 blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
1040 visited = BITMAP_ALLOC (NULL);
1042 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1044 index = 0;
1045 while (index < loop->num_nodes)
1047 bb = blocks_in_bfs_order [index];
1049 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1051 free (blocks_in_bfs_order);
1052 BITMAP_FREE (visited);
1053 free (blocks);
1054 return NULL;
1056 if (!bitmap_bit_p (visited, bb->index))
1058 if (pred_blocks_visited_p (bb, &visited)
1059 || bb == loop->header)
1061 /* This block is now visited. */
1062 bitmap_set_bit (visited, bb->index);
1063 blocks[visited_count++] = bb;
1066 index++;
1067 if (index == loop->num_nodes
1068 && visited_count != loop->num_nodes)
1070 /* Not done yet. */
1071 index = 0;
1074 free (blocks_in_bfs_order);
1075 BITMAP_FREE (visited);
1076 return blocks;
1079 /* Return true if one of the basic block BB edge is exit of LOOP. */
1081 static bool
1082 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1084 edge e;
1085 edge_iterator ei;
1086 bool exit_edge_found = false;
1088 FOR_EACH_EDGE (e, ei, bb->succs)
1089 if (loop_exit_edge_p (loop, e))
1091 exit_edge_found = true;
1092 break;
1095 return exit_edge_found;
1098 /* Tree if-conversion pass management. */
1100 static void
1101 main_tree_if_conversion (void)
1103 unsigned i, loop_num;
1104 struct loop *loop;
1106 if (!current_loops)
1107 return;
1109 loop_num = current_loops->num;
1110 for (i = 0; i < loop_num; i++)
1112 loop = current_loops->parray[i];
1113 if (!loop)
1114 continue;
1116 tree_if_conversion (loop, true);
1121 static bool
1122 gate_tree_if_conversion (void)
1124 return flag_tree_vectorize != 0;
1127 struct tree_opt_pass pass_if_conversion =
1129 "ifcvt", /* name */
1130 gate_tree_if_conversion, /* gate */
1131 main_tree_if_conversion, /* execute */
1132 NULL, /* sub */
1133 NULL, /* next */
1134 0, /* static_pass_number */
1135 0, /* tv_id */
1136 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1137 0, /* properties_provided */
1138 0, /* properties_destroyed */
1139 0, /* todo_flags_start */
1140 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
1141 /* todo_flags_finish */
1142 0 /* letter */