Daily bump.
[official-gcc.git] / gcc / tree-if-conv.c
blobec349297fd109adc7cd9984b8ece7b3bc93d64fa
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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements tree level if-conversion transformation of loops.
22 Initial goal is to help vectorizer vectorize loops with conditions.
24 A short description of if-conversion:
26 o Decide if a loop is if-convertible or not.
27 o Walk all loop basic blocks in breadth first order (BFS order).
28 o Remove conditional statements (at the end of basic block)
29 and propagate condition into destination basic blocks'
30 predicate list.
31 o Replace modify expression with conditional modify expression
32 using current basic block's condition.
33 o Merge all basic blocks
34 o Replace phi nodes with conditional modify expr
35 o Merge all basic blocks into header
37 Sample transformation:
39 INPUT
40 -----
42 # i_23 = PHI <0(0), i_18(10)>;
43 <L0>:;
44 j_15 = A[i_23];
45 if (j_15 > 41) goto <L1>; else goto <L17>;
47 <L17>:;
48 goto <bb 3> (<L3>);
50 <L1>:;
52 # iftmp.2_4 = PHI <0(8), 42(2)>;
53 <L3>:;
54 A[i_23] = iftmp.2_4;
55 i_18 = i_23 + 1;
56 if (i_18 <= 15) goto <L19>; else goto <L18>;
58 <L19>:;
59 goto <bb 1> (<L0>);
61 <L18>:;
63 OUTPUT
64 ------
66 # i_23 = PHI <0(0), i_18(10)>;
67 <L0>:;
68 j_15 = A[i_23];
70 <L3>:;
71 iftmp.2_4 = j_15 > 41 ? 42 : 0;
72 A[i_23] = iftmp.2_4;
73 i_18 = i_23 + 1;
74 if (i_18 <= 15) goto <L19>; else goto <L18>;
76 <L19>:;
77 goto <bb 1> (<L0>);
79 <L18>:;
82 #include "config.h"
83 #include "system.h"
84 #include "coretypes.h"
85 #include "tm.h"
86 #include "tree.h"
87 #include "c-common.h"
88 #include "flags.h"
89 #include "timevar.h"
90 #include "varray.h"
91 #include "rtl.h"
92 #include "basic-block.h"
93 #include "diagnostic.h"
94 #include "tree-flow.h"
95 #include "tree-dump.h"
96 #include "cfgloop.h"
97 #include "tree-chrec.h"
98 #include "tree-data-ref.h"
99 #include "tree-scalar-evolution.h"
100 #include "tree-pass.h"
101 #include "target.h"
103 /* local function prototypes */
104 static unsigned int main_tree_if_conversion (void);
105 static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
106 block_stmt_iterator *);
107 static void tree_if_convert_cond_expr (struct loop *, tree, tree,
108 block_stmt_iterator *);
109 static bool if_convertible_phi_p (struct loop *, basic_block, tree);
110 static bool if_convertible_gimple_modify_stmt_p (struct loop *, basic_block,
111 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, edge,
117 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_gimple_modify_stmt (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 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 /* Do actual work now. */
167 for (i = 0; i < loop->num_nodes; i++)
169 tree cond;
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);
193 /* Successor bb inherits predicate of its predecessor. If there
194 is no predicate in predecessor bb, then consider successor bb
195 as always executed. */
196 if (cond == NULL_TREE)
197 cond = boolean_true_node;
199 add_to_predicate_list (bb_n, cond);
203 /* Now, all statements are if-converted and basic blocks are
204 annotated appropriately. Combine all basic block into one huge
205 basic block. */
206 combine_blocks (loop);
208 /* clean up */
209 clean_predicate_lists (loop);
210 free (ifc_bbs);
211 ifc_bbs = NULL;
213 return true;
216 /* if-convert stmt T which is part of LOOP.
217 If T is a GIMPLE_MODIFY_STMT than it is converted into conditional modify
218 expression using COND. For conditional expressions, add condition in the
219 destination basic block's predicate list and remove conditional
220 expression itself. BSI is the iterator used to traverse statements of
221 loop. It is used here when it is required to delete current statement. */
223 static tree
224 tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
225 block_stmt_iterator *bsi)
227 if (dump_file && (dump_flags & TDF_DETAILS))
229 fprintf (dump_file, "------if-convert stmt\n");
230 print_generic_stmt (dump_file, t, TDF_SLIM);
231 print_generic_stmt (dump_file, cond, TDF_SLIM);
234 switch (TREE_CODE (t))
236 /* Labels are harmless here. */
237 case LABEL_EXPR:
238 break;
240 case GIMPLE_MODIFY_STMT:
241 /* This GIMPLE_MODIFY_STMT is killing previous value of LHS. Appropriate
242 value will be selected by PHI node based on condition. It is possible
243 that before this transformation, PHI nodes was selecting default
244 value and now it will use this new value. This is OK because it does
245 not change validity the program. */
246 break;
248 case COND_EXPR:
249 /* Update destination blocks' predicate list and remove this
250 condition expression. */
251 tree_if_convert_cond_expr (loop, t, cond, bsi);
252 cond = NULL_TREE;
253 break;
255 default:
256 gcc_unreachable ();
258 return cond;
261 /* STMT is COND_EXPR. Update two destination's predicate list.
262 Remove COND_EXPR, if it is not the loop exit condition. Otherwise
263 update loop exit condition appropriately. BSI is the iterator
264 used to traverse statement list. STMT is part of loop LOOP. */
266 static void
267 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
268 block_stmt_iterator *bsi)
270 tree c, c2;
271 edge true_edge, false_edge;
273 gcc_assert (TREE_CODE (stmt) == COND_EXPR);
275 c = COND_EXPR_COND (stmt);
277 extract_true_false_edges_from_block (bb_for_stmt (stmt),
278 &true_edge, &false_edge);
280 /* Add new condition into destination's predicate list. */
282 /* If 'c' is true then TRUE_EDGE is taken. */
283 add_to_dst_predicate_list (loop, true_edge, cond,
284 unshare_expr (c), bsi);
286 /* If 'c' is false then FALSE_EDGE is taken. */
287 c2 = invert_truthvalue (unshare_expr (c));
288 add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
290 /* Now this conditional statement is redundant. Remove it.
291 But, do not remove exit condition! Update exit condition
292 using new condition. */
293 if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
295 bsi_remove (bsi, true);
296 cond = NULL_TREE;
298 return;
301 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
302 and it belongs to basic block BB.
303 PHI is not if-convertible
304 - if it has more than 2 arguments.
305 - Virtual PHI is immediately used in another PHI node.
306 - Virtual PHI on BB other than header. */
308 static bool
309 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
311 if (dump_file && (dump_flags & TDF_DETAILS))
313 fprintf (dump_file, "-------------------------\n");
314 print_generic_stmt (dump_file, phi, TDF_SLIM);
317 if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
319 if (dump_file && (dump_flags & TDF_DETAILS))
320 fprintf (dump_file, "More than two phi node args.\n");
321 return false;
324 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
326 imm_use_iterator imm_iter;
327 use_operand_p use_p;
329 if (bb != loop->header)
331 if (dump_file && (dump_flags & TDF_DETAILS))
332 fprintf (dump_file, "Virtual phi not on loop header.\n");
333 return false;
335 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
337 if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
339 if (dump_file && (dump_flags & TDF_DETAILS))
340 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
341 return false;
346 return true;
349 /* Return true, if M_EXPR is if-convertible.
350 GIMPLE_MODIFY_STMT is not if-convertible if,
351 - It is not movable.
352 - It could trap.
353 - LHS is not var decl.
354 GIMPLE_MODIFY_STMT is part of block BB, which is inside loop LOOP.
357 static bool
358 if_convertible_gimple_modify_stmt_p (struct loop *loop, basic_block bb,
359 tree m_expr)
361 tree lhs, rhs;
363 if (TREE_CODE (m_expr) != GIMPLE_MODIFY_STMT)
364 return false;
366 if (dump_file && (dump_flags & TDF_DETAILS))
368 fprintf (dump_file, "-------------------------\n");
369 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
372 lhs = GIMPLE_STMT_OPERAND (m_expr, 0);
373 rhs = GIMPLE_STMT_OPERAND (m_expr, 1);
375 /* Some of these constrains might be too conservative. */
376 if (stmt_ends_bb_p (m_expr) || stmt_ann (m_expr)->has_volatile_ops
377 || (TREE_CODE (lhs) == SSA_NAME
378 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
379 || TREE_SIDE_EFFECTS (rhs))
381 if (dump_file && (dump_flags & TDF_DETAILS))
382 fprintf (dump_file, "stmt not suitable for ifcvt\n");
383 return false;
386 /* See if it needs speculative loading or not. */
387 if (bb != loop->header
388 && tree_could_trap_p (GIMPLE_STMT_OPERAND (m_expr, 1)))
390 if (dump_file && (dump_flags & TDF_DETAILS))
391 fprintf (dump_file, "tree could trap...\n");
392 return false;
395 if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 1)) == CALL_EXPR)
397 if (dump_file && (dump_flags & TDF_DETAILS))
398 fprintf (dump_file, "CALL_EXPR \n");
399 return false;
402 if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 0)) != SSA_NAME
403 && bb != loop->header
404 && !bb_with_exit_edge_p (loop, bb))
406 if (dump_file && (dump_flags & TDF_DETAILS))
408 fprintf (dump_file, "LHS is not var\n");
409 print_generic_stmt (dump_file, m_expr, TDF_SLIM);
411 return false;
415 return true;
418 /* Return true, iff STMT is if-convertible.
419 Statement is if-convertible if,
420 - It is if-convertible GIMPLE_MODIFY_STMT
421 - IT is LABEL_EXPR or COND_EXPR.
422 STMT is inside block BB, which is inside loop LOOP. */
424 static bool
425 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
427 switch (TREE_CODE (stmt))
429 case LABEL_EXPR:
430 break;
432 case GIMPLE_MODIFY_STMT:
434 if (!if_convertible_gimple_modify_stmt_p (loop, bb, stmt))
435 return false;
436 break;
438 case COND_EXPR:
439 break;
441 default:
442 /* Don't know what to do with 'em so don't do anything. */
443 if (dump_file && (dump_flags & TDF_DETAILS))
445 fprintf (dump_file, "don't know what to do\n");
446 print_generic_stmt (dump_file, stmt, TDF_SLIM);
448 return false;
449 break;
452 return true;
455 /* Return true, iff BB is if-convertible.
456 Note: This routine does _not_ check basic block statements and phis.
457 Basic block is not if-convertible if,
458 - Basic block is non-empty and it is after exit block (in BFS order).
459 - Basic block is after exit block but before latch.
460 - Basic block edge(s) is not normal.
461 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
462 BB is inside loop LOOP. */
464 static bool
465 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
467 edge e;
468 edge_iterator ei;
470 if (dump_file && (dump_flags & TDF_DETAILS))
471 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
473 if (exit_bb)
475 if (bb != loop->latch)
477 if (dump_file && (dump_flags & TDF_DETAILS))
478 fprintf (dump_file, "basic block after exit bb but before latch\n");
479 return false;
481 else if (!empty_block_p (bb))
483 if (dump_file && (dump_flags & TDF_DETAILS))
484 fprintf (dump_file, "non empty basic block after exit bb\n");
485 return false;
487 else if (bb == loop->latch
488 && bb != exit_bb
489 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
491 if (dump_file && (dump_flags & TDF_DETAILS))
492 fprintf (dump_file, "latch is not dominated by exit_block\n");
493 return false;
497 /* Be less adventurous and handle only normal edges. */
498 FOR_EACH_EDGE (e, ei, bb->succs)
499 if (e->flags &
500 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
502 if (dump_file && (dump_flags & TDF_DETAILS))
503 fprintf (dump_file,"Difficult to handle edges\n");
504 return false;
507 return true;
510 /* Return true, iff LOOP is if-convertible.
511 LOOP is if-convertible if,
512 - It is innermost.
513 - It has two or more basic blocks.
514 - It has only one exit.
515 - Loop header is not the exit edge.
516 - If its basic blocks and phi nodes are if convertible. See above for
517 more info.
518 FOR_VECTORIZER enables vectorizer specific checks. For example, support
519 for vector conditions, data dependency checks etc.. (Not implemented yet). */
521 static bool
522 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
524 tree phi;
525 basic_block bb;
526 block_stmt_iterator itr;
527 unsigned int i;
528 edge e;
529 edge_iterator ei;
530 basic_block exit_bb = NULL;
532 /* Handle only inner most loop. */
533 if (!loop || loop->inner)
535 if (dump_file && (dump_flags & TDF_DETAILS))
536 fprintf (dump_file, "not inner most loop\n");
537 return false;
540 /* If only one block, no need for if-conversion. */
541 if (loop->num_nodes <= 2)
543 if (dump_file && (dump_flags & TDF_DETAILS))
544 fprintf (dump_file, "less than 2 basic blocks\n");
545 return false;
548 /* More than one loop exit is too much to handle. */
549 if (!single_exit (loop))
551 if (dump_file && (dump_flags & TDF_DETAILS))
552 fprintf (dump_file, "multiple exits\n");
553 return false;
556 /* ??? Check target's vector conditional operation support for vectorizer. */
558 /* If one of the loop header's edge is exit edge then do not apply
559 if-conversion. */
560 FOR_EACH_EDGE (e, ei, loop->header->succs)
562 if (loop_exit_edge_p (loop, e))
563 return false;
566 calculate_dominance_info (CDI_DOMINATORS);
567 calculate_dominance_info (CDI_POST_DOMINATORS);
569 /* Allow statements that can be handled during if-conversion. */
570 ifc_bbs = get_loop_body_in_if_conv_order (loop);
571 if (!ifc_bbs)
573 if (dump_file && (dump_flags & TDF_DETAILS))
574 fprintf (dump_file,"Irreducible loop\n");
575 free_dominance_info (CDI_POST_DOMINATORS);
576 return false;
579 for (i = 0; i < loop->num_nodes; i++)
581 bb = ifc_bbs[i];
583 if (!if_convertible_bb_p (loop, bb, exit_bb))
584 return false;
586 /* Check statements. */
587 for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
588 if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
589 return false;
590 /* ??? Check data dependency for vectorizer. */
592 /* What about phi nodes ? */
593 phi = phi_nodes (bb);
595 /* Clear aux field of incoming edges to a bb with a phi node. */
596 if (phi)
597 FOR_EACH_EDGE (e, ei, bb->preds)
598 e->aux = NULL;
600 /* Check statements. */
601 for (; phi; phi = PHI_CHAIN (phi))
602 if (!if_convertible_phi_p (loop, bb, phi))
603 return false;
605 if (bb_with_exit_edge_p (loop, bb))
606 exit_bb = bb;
609 /* OK. Did not find any potential issues so go ahead in if-convert
610 this loop. Now there is no looking back. */
611 if (dump_file)
612 fprintf (dump_file,"Applying if-conversion\n");
614 free_dominance_info (CDI_POST_DOMINATORS);
615 return true;
618 /* Add condition COND into predicate list of basic block BB. */
620 static void
621 add_to_predicate_list (basic_block bb, tree new_cond)
623 tree cond = bb->aux;
625 if (cond)
626 cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
627 unshare_expr (cond), new_cond);
628 else
629 cond = new_cond;
631 bb->aux = cond;
634 /* Add condition COND into BB's predicate list. PREV_COND is
635 existing condition. */
637 static tree
638 add_to_dst_predicate_list (struct loop * loop, edge e,
639 tree prev_cond, tree cond,
640 block_stmt_iterator *bsi)
642 tree new_cond = NULL_TREE;
644 if (!flow_bb_inside_loop_p (loop, e->dest))
645 return NULL_TREE;
647 if (prev_cond == boolean_true_node || !prev_cond)
648 new_cond = unshare_expr (cond);
649 else
651 tree tmp;
652 tree tmp_stmt = NULL_TREE;
654 prev_cond = force_gimple_operand_bsi (bsi, unshare_expr (prev_cond),
655 true, NULL, true, BSI_SAME_STMT);
657 cond = force_gimple_operand_bsi (bsi, unshare_expr (cond),
658 true, NULL, true, BSI_SAME_STMT);
660 /* Add the condition to aux field of the edge. In case edge
661 destination is a PHI node, this condition will be ANDed with
662 block predicate to construct complete condition. */
663 e->aux = cond;
665 /* new_cond == prev_cond AND cond */
666 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
667 unshare_expr (prev_cond), cond);
668 tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
669 bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
670 new_cond = GIMPLE_STMT_OPERAND (tmp_stmt, 0);
672 add_to_predicate_list (e->dest, new_cond);
673 return new_cond;
676 /* During if-conversion aux field from basic block structure is used to hold
677 predicate list. Clean each basic block's predicate list for the given LOOP.
678 Also clean aux field of successor edges, used to hold true and false
679 condition from conditional expression. */
681 static void
682 clean_predicate_lists (struct loop *loop)
684 basic_block *bb;
685 unsigned int i;
686 edge e;
687 edge_iterator ei;
689 bb = get_loop_body (loop);
690 for (i = 0; i < loop->num_nodes; i++)
692 bb[i]->aux = NULL;
693 FOR_EACH_EDGE (e, ei, bb[i]->succs)
694 e->aux = NULL;
696 free (bb);
699 /* Basic block BB has two predecessors. Using predecessor's aux field, set
700 appropriate condition COND for the PHI node replacement. Return true block
701 whose phi arguments are selected when cond is true. */
703 static basic_block
704 find_phi_replacement_condition (struct loop *loop,
705 basic_block bb, tree *cond,
706 block_stmt_iterator *bsi)
708 edge first_edge, second_edge;
709 tree tmp_cond;
711 gcc_assert (EDGE_COUNT (bb->preds) == 2);
712 first_edge = EDGE_PRED (bb, 0);
713 second_edge = EDGE_PRED (bb, 1);
715 /* Use condition based on following criteria:
717 S1: x = !c ? a : b;
719 S2: x = c ? b : a;
721 S2 is preferred over S1. Make 'b' first_bb and use its condition.
723 2) Do not make loop header first_bb.
726 S1: x = !(c == d)? a : b;
728 S21: t1 = c == d;
729 S22: x = t1 ? b : a;
731 S3: x = (c == d) ? b : a;
733 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
734 its condition.
736 4) If pred B is dominated by pred A then use pred B's condition.
737 See PR23115. */
739 /* Select condition that is not TRUTH_NOT_EXPR. */
740 tmp_cond = (first_edge->src)->aux;
741 gcc_assert (tmp_cond);
743 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
745 edge tmp_edge;
747 tmp_edge = first_edge;
748 first_edge = second_edge;
749 second_edge = tmp_edge;
752 /* Check if FIRST_BB is loop header or not and make sure that
753 FIRST_BB does not dominate SECOND_BB. */
754 if (first_edge->src == loop->header
755 || dominated_by_p (CDI_DOMINATORS,
756 second_edge->src, first_edge->src))
758 *cond = (second_edge->src)->aux;
760 /* If there is a condition on an incoming edge,
761 AND it with the incoming bb predicate. */
762 if (second_edge->aux)
763 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
764 *cond, second_edge->aux);
766 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
767 /* We can be smart here and choose inverted
768 condition without switching bbs. */
769 *cond = invert_truthvalue (*cond);
770 else
771 /* Select non loop header bb. */
772 first_edge = second_edge;
774 else
776 /* FIRST_BB is not loop header */
777 *cond = (first_edge->src)->aux;
779 /* If there is a condition on an incoming edge,
780 AND it with the incoming bb predicate. */
781 if (first_edge->aux)
782 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
783 *cond, first_edge->aux);
786 /* Create temp. for the condition. Vectorizer prefers to have gimple
787 value as condition. Various targets use different means to communicate
788 condition in vector compare operation. Using gimple value allows
789 compiler to emit vector compare and select RTL without exposing
790 compare's result. */
791 *cond = force_gimple_operand_bsi (bsi, unshare_expr (*cond),
792 false, NULL_TREE,
793 true, BSI_SAME_STMT);
794 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
796 tree new_stmt;
798 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
799 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
800 *cond = GIMPLE_STMT_OPERAND (new_stmt, 0);
803 gcc_assert (*cond);
805 return first_edge->src;
809 /* Replace PHI node with conditional modify expr using COND.
810 This routine does not handle PHI nodes with more than two arguments.
811 For example,
812 S1: A = PHI <x1(1), x2(5)
813 is converted into,
814 S2: A = cond ? x1 : x2;
815 S2 is inserted at the top of basic block's statement list.
816 When COND is true, phi arg from TRUE_BB is selected.
819 static void
820 replace_phi_with_cond_gimple_modify_stmt (tree phi, tree cond,
821 basic_block true_bb,
822 block_stmt_iterator *bsi)
824 tree new_stmt;
825 basic_block bb;
826 tree rhs;
827 tree arg_0, arg_1;
829 gcc_assert (TREE_CODE (phi) == PHI_NODE);
831 /* If this is not filtered earlier, then now it is too late. */
832 gcc_assert (PHI_NUM_ARGS (phi) == 2);
834 /* Find basic block and initialize iterator. */
835 bb = bb_for_stmt (phi);
837 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
838 if (EDGE_PRED (bb, 1)->src == true_bb)
840 arg_0 = PHI_ARG_DEF (phi, 1);
841 arg_1 = PHI_ARG_DEF (phi, 0);
843 else
845 arg_0 = PHI_ARG_DEF (phi, 0);
846 arg_1 = PHI_ARG_DEF (phi, 1);
849 /* Build new RHS using selected condition and arguments. */
850 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
851 unshare_expr (cond), unshare_expr (arg_0),
852 unshare_expr (arg_1));
854 /* Create new MODIFY expression using RHS. */
855 new_stmt = build_gimple_modify_stmt (unshare_expr (PHI_RESULT (phi)), rhs);
857 /* Make new statement definition of the original phi result. */
858 SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
860 /* Insert using iterator. */
861 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
862 update_stmt (new_stmt);
864 if (dump_file && (dump_flags & TDF_DETAILS))
866 fprintf (dump_file, "new phi replacement stmt\n");
867 print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
871 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
872 modify expr. */
874 static void
875 process_phi_nodes (struct loop *loop)
877 basic_block bb;
878 unsigned int orig_loop_num_nodes = loop->num_nodes;
879 unsigned int i;
881 /* Replace phi nodes with cond. modify expr. */
882 for (i = 1; i < orig_loop_num_nodes; i++)
884 tree phi, cond = NULL_TREE;
885 block_stmt_iterator bsi;
886 basic_block true_bb = NULL;
887 bb = ifc_bbs[i];
889 if (bb == loop->header)
890 continue;
892 phi = phi_nodes (bb);
893 bsi = bsi_after_labels (bb);
895 /* BB has two predecessors. Using predecessor's aux field, set
896 appropriate condition for the PHI node replacement. */
897 if (phi)
898 true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
900 while (phi)
902 tree next = PHI_CHAIN (phi);
903 replace_phi_with_cond_gimple_modify_stmt (phi, cond, true_bb, &bsi);
904 release_phi_node (phi);
905 phi = next;
907 set_phi_nodes (bb, NULL_TREE);
909 return;
912 /* Combine all basic block from the given LOOP into one or two super
913 basic block. Replace PHI nodes with conditional modify expression. */
915 static void
916 combine_blocks (struct loop *loop)
918 basic_block bb, exit_bb, merge_target_bb;
919 unsigned int orig_loop_num_nodes = loop->num_nodes;
920 unsigned int i;
921 edge e;
922 edge_iterator ei;
924 /* Process phi nodes to prepare blocks for merge. */
925 process_phi_nodes (loop);
927 /* Merge basic blocks. First remove all the edges in the loop, except
928 for those from the exit block. */
929 exit_bb = NULL;
930 for (i = 0; i < orig_loop_num_nodes; i++)
932 bb = ifc_bbs[i];
933 if (bb_with_exit_edge_p (loop, bb))
935 exit_bb = bb;
936 break;
939 gcc_assert (exit_bb != loop->latch);
941 for (i = 1; i < orig_loop_num_nodes; i++)
943 bb = ifc_bbs[i];
945 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
947 if (e->src == exit_bb)
948 ei_next (&ei);
949 else
950 remove_edge (e);
954 if (exit_bb != NULL)
956 if (exit_bb != loop->header)
958 /* Connect this node with loop header. */
959 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
960 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
963 /* Redirect non-exit edges to loop->latch. */
964 FOR_EACH_EDGE (e, ei, exit_bb->succs)
966 if (!loop_exit_edge_p (loop, e))
967 redirect_edge_and_branch (e, loop->latch);
969 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
971 else
973 /* If the loop does not have exit then reconnect header and latch. */
974 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
975 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
978 merge_target_bb = loop->header;
979 for (i = 1; i < orig_loop_num_nodes; i++)
981 block_stmt_iterator bsi;
982 tree_stmt_iterator last;
984 bb = ifc_bbs[i];
986 if (bb == exit_bb || bb == loop->latch)
987 continue;
989 /* Remove labels and make stmts member of loop->header. */
990 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
992 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
993 bsi_remove (&bsi, true);
994 else
996 set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
997 bsi_next (&bsi);
1001 /* Update stmt list. */
1002 last = tsi_last (bb_stmt_list (merge_target_bb));
1003 tsi_link_after (&last, bb_stmt_list (bb), TSI_NEW_STMT);
1004 set_bb_stmt_list (bb, alloc_stmt_list());
1006 delete_basic_block (bb);
1009 /* Now if possible, merge loop header and block with exit edge.
1010 This reduces number of basic blocks to 2. Auto vectorizer addresses
1011 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
1012 if (exit_bb
1013 && exit_bb != loop->header
1014 && can_merge_blocks_p (loop->header, exit_bb))
1015 merge_blocks (loop->header, exit_bb);
1018 /* Make new temp variable of type TYPE. Add GIMPLE_MODIFY_STMT to assign EXP
1019 to the new variable. */
1021 static tree
1022 ifc_temp_var (tree type, tree exp)
1024 const char *name = "_ifc_";
1025 tree var, stmt, new_name;
1027 if (is_gimple_reg (exp))
1028 return exp;
1030 /* Create new temporary variable. */
1031 var = create_tmp_var (type, name);
1032 add_referenced_var (var);
1034 /* Build new statement to assign EXP to new variable. */
1035 stmt = build_gimple_modify_stmt (var, exp);
1037 /* Get SSA name for the new variable and set make new statement
1038 its definition statement. */
1039 new_name = make_ssa_name (var, stmt);
1040 GIMPLE_STMT_OPERAND (stmt, 0) = new_name;
1041 SSA_NAME_DEF_STMT (new_name) = stmt;
1043 return stmt;
1047 /* Return TRUE iff, all pred blocks of BB are visited.
1048 Bitmap VISITED keeps history of visited blocks. */
1050 static bool
1051 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1053 edge e;
1054 edge_iterator ei;
1055 FOR_EACH_EDGE (e, ei, bb->preds)
1056 if (!bitmap_bit_p (*visited, e->src->index))
1057 return false;
1059 return true;
1062 /* Get body of a LOOP in suitable order for if-conversion.
1063 It is caller's responsibility to deallocate basic block
1064 list. If-conversion suitable order is, BFS order with one
1065 additional constraint. Select block in BFS block, if all
1066 pred are already selected. */
1068 static basic_block *
1069 get_loop_body_in_if_conv_order (const struct loop *loop)
1071 basic_block *blocks, *blocks_in_bfs_order;
1072 basic_block bb;
1073 bitmap visited;
1074 unsigned int index = 0;
1075 unsigned int visited_count = 0;
1077 gcc_assert (loop->num_nodes);
1078 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1080 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1081 visited = BITMAP_ALLOC (NULL);
1083 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1085 index = 0;
1086 while (index < loop->num_nodes)
1088 bb = blocks_in_bfs_order [index];
1090 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1092 free (blocks_in_bfs_order);
1093 BITMAP_FREE (visited);
1094 free (blocks);
1095 return NULL;
1097 if (!bitmap_bit_p (visited, bb->index))
1099 if (pred_blocks_visited_p (bb, &visited)
1100 || bb == loop->header)
1102 /* This block is now visited. */
1103 bitmap_set_bit (visited, bb->index);
1104 blocks[visited_count++] = bb;
1107 index++;
1108 if (index == loop->num_nodes
1109 && visited_count != loop->num_nodes)
1111 /* Not done yet. */
1112 index = 0;
1115 free (blocks_in_bfs_order);
1116 BITMAP_FREE (visited);
1117 return blocks;
1120 /* Return true if one of the basic block BB edge is exit of LOOP. */
1122 static bool
1123 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1125 edge e;
1126 edge_iterator ei;
1127 bool exit_edge_found = false;
1129 FOR_EACH_EDGE (e, ei, bb->succs)
1130 if (loop_exit_edge_p (loop, e))
1132 exit_edge_found = true;
1133 break;
1136 return exit_edge_found;
1139 /* Tree if-conversion pass management. */
1141 static unsigned int
1142 main_tree_if_conversion (void)
1144 loop_iterator li;
1145 struct loop *loop;
1147 if (number_of_loops () <= 1)
1148 return 0;
1150 FOR_EACH_LOOP (li, loop, 0)
1152 tree_if_conversion (loop, true);
1154 return 0;
1157 static bool
1158 gate_tree_if_conversion (void)
1160 return flag_tree_vectorize != 0;
1163 struct tree_opt_pass pass_if_conversion =
1165 "ifcvt", /* name */
1166 gate_tree_if_conversion, /* gate */
1167 main_tree_if_conversion, /* execute */
1168 NULL, /* sub */
1169 NULL, /* next */
1170 0, /* static_pass_number */
1171 0, /* tv_id */
1172 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1173 0, /* properties_provided */
1174 0, /* properties_destroyed */
1175 0, /* todo_flags_start */
1176 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
1177 /* todo_flags_finish */
1178 0 /* letter */