* xcoffout.h (xcoffout_source_line): Update prototype.
[official-gcc.git] / gcc / tree-if-conv.c
blobc1b05328fa61e33840469248a4c99827025a5eec
1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Devang Patel <dpatel@apple.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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 "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"
104 /* local function prototypes */
105 static unsigned int main_tree_if_conversion (void);
106 static tree tree_if_convert_stmt (struct loop *loop, gimple, tree,
107 gimple_stmt_iterator *);
108 static void tree_if_convert_cond_stmt (struct loop *, gimple, tree,
109 gimple_stmt_iterator *);
110 static bool if_convertible_phi_p (struct loop *, basic_block, gimple);
111 static bool if_convertible_gimple_assign_stmt_p (struct loop *, basic_block,
112 gimple);
113 static bool if_convertible_stmt_p (struct loop *, basic_block, gimple);
114 static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
115 static bool if_convertible_loop_p (struct loop *, bool);
116 static void add_to_predicate_list (basic_block, tree);
117 static tree add_to_dst_predicate_list (struct loop * loop, edge,
118 tree, tree,
119 gimple_stmt_iterator *);
120 static void clean_predicate_lists (struct loop *loop);
121 static basic_block find_phi_replacement_condition (struct loop *loop,
122 basic_block, tree *,
123 gimple_stmt_iterator *);
124 static void replace_phi_with_cond_gimple_assign_stmt (gimple, tree,
125 basic_block,
126 gimple_stmt_iterator *);
127 static void process_phi_nodes (struct loop *);
128 static void combine_blocks (struct loop *);
129 static gimple ifc_temp_var (tree, tree);
130 static bool pred_blocks_visited_p (basic_block, bitmap *);
131 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
132 static bool bb_with_exit_edge_p (struct loop *, basic_block);
134 /* List of basic blocks in if-conversion-suitable order. */
135 static basic_block *ifc_bbs;
137 /* Main entry point.
138 Apply if-conversion to the LOOP. Return true if successful otherwise return
139 false. If false is returned then loop remains unchanged.
140 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
141 for vectorizer or not. If it is used for vectorizer, additional checks are
142 used. (Vectorization checks are not yet implemented). */
144 static bool
145 tree_if_conversion (struct loop *loop, bool for_vectorizer)
147 basic_block bb;
148 gimple_stmt_iterator itr;
149 unsigned int i;
151 ifc_bbs = NULL;
153 /* if-conversion is not appropriate for all loops. First, check if loop is
154 if-convertible or not. */
155 if (!if_convertible_loop_p (loop, for_vectorizer))
157 if (dump_file && (dump_flags & TDF_DETAILS))
158 fprintf (dump_file,"-------------------------\n");
159 if (ifc_bbs)
161 free (ifc_bbs);
162 ifc_bbs = NULL;
164 free_dominance_info (CDI_POST_DOMINATORS);
165 return false;
168 /* Do actual work now. */
169 for (i = 0; i < loop->num_nodes; i++)
171 tree cond;
173 bb = ifc_bbs [i];
175 /* Update condition using predicate list. */
176 cond = (tree) bb->aux;
178 /* Process all statements in this basic block.
179 Remove conditional expression, if any, and annotate
180 destination basic block(s) appropriately. */
181 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
183 gimple t = gsi_stmt (itr);
184 cond = tree_if_convert_stmt (loop, t, cond, &itr);
185 if (!gsi_end_p (itr))
186 gsi_next (&itr);
189 /* If current bb has only one successor, then consider it as an
190 unconditional goto. */
191 if (single_succ_p (bb))
193 basic_block bb_n = single_succ (bb);
195 /* Successor bb inherits predicate of its predecessor. If there
196 is no predicate in predecessor bb, then consider successor bb
197 as always executed. */
198 if (cond == NULL_TREE)
199 cond = boolean_true_node;
201 add_to_predicate_list (bb_n, cond);
205 /* Now, all statements are if-converted and basic blocks are
206 annotated appropriately. Combine all basic block into one huge
207 basic block. */
208 combine_blocks (loop);
210 /* clean up */
211 clean_predicate_lists (loop);
212 free (ifc_bbs);
213 ifc_bbs = NULL;
215 return true;
218 /* if-convert stmt T which is part of LOOP.
219 If T is a GIMPLE_ASSIGN then it is converted into conditional modify
220 expression using COND. For conditional expressions, add condition in the
221 destination basic block's predicate list and remove conditional
222 expression itself. BSI is the iterator used to traverse statements of
223 loop. It is used here when it is required to delete current statement. */
225 static tree
226 tree_if_convert_stmt (struct loop * loop, gimple t, tree cond,
227 gimple_stmt_iterator *gsi)
229 if (dump_file && (dump_flags & TDF_DETAILS))
231 fprintf (dump_file, "------if-convert stmt\n");
232 print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
233 print_generic_stmt (dump_file, cond, TDF_SLIM);
236 switch (gimple_code (t))
238 /* Labels are harmless here. */
239 case GIMPLE_LABEL:
240 break;
242 case GIMPLE_ASSIGN:
243 /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate
244 value will be selected by PHI node based on condition. It is possible
245 that before this transformation, PHI nodes was selecting default
246 value and now it will use this new value. This is OK because it does
247 not change validity the program. */
248 break;
250 case GIMPLE_COND:
251 /* Update destination blocks' predicate list and remove this
252 condition expression. */
253 tree_if_convert_cond_stmt (loop, t, cond, gsi);
254 cond = NULL_TREE;
255 break;
257 default:
258 gcc_unreachable ();
260 return cond;
263 /* STMT is a GIMPLE_COND. Update two destination's predicate list.
264 Remove COND_EXPR, if it is not the loop exit condition. Otherwise
265 update loop exit condition appropriately. GSI is the iterator
266 used to traverse statement list. STMT is part of loop LOOP. */
268 static void
269 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
270 gimple_stmt_iterator *gsi)
272 tree c, c2;
273 edge true_edge, false_edge;
275 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
277 c = fold_build2 (gimple_cond_code (stmt), boolean_type_node,
278 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
280 extract_true_false_edges_from_block (gimple_bb (stmt),
281 &true_edge, &false_edge);
283 /* Add new condition into destination's predicate list. */
285 /* If C is true then TRUE_EDGE is taken. */
286 add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
288 /* If 'c' is false then FALSE_EDGE is taken. */
289 c2 = invert_truthvalue (unshare_expr (c));
290 add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
292 /* Now this conditional statement is redundant. Remove it.
293 But, do not remove exit condition! Update exit condition
294 using new condition. */
295 if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
297 gsi_remove (gsi, true);
298 cond = NULL_TREE;
300 return;
303 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
304 and it belongs to basic block BB.
305 PHI is not if-convertible
306 - if it has more than 2 arguments.
307 - Virtual PHI is immediately used in another PHI node.
308 - Virtual PHI on BB other than header. */
310 static bool
311 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
313 if (dump_file && (dump_flags & TDF_DETAILS))
315 fprintf (dump_file, "-------------------------\n");
316 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
319 if (bb != loop->header && gimple_phi_num_args (phi) != 2)
321 if (dump_file && (dump_flags & TDF_DETAILS))
322 fprintf (dump_file, "More than two phi node args.\n");
323 return false;
326 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
328 imm_use_iterator imm_iter;
329 use_operand_p use_p;
331 if (bb != loop->header)
333 if (dump_file && (dump_flags & TDF_DETAILS))
334 fprintf (dump_file, "Virtual phi not on loop header.\n");
335 return false;
337 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
339 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
341 if (dump_file && (dump_flags & TDF_DETAILS))
342 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
343 return false;
348 return true;
351 /* Return true, if STMT is if-convertible.
352 GIMPLE_ASSIGN statement is not if-convertible if,
353 - It is not movable.
354 - It could trap.
355 - LHS is not var decl.
356 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
358 static bool
359 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
360 gimple stmt)
362 tree lhs;
364 if (!is_gimple_assign (stmt))
365 return false;
367 if (dump_file && (dump_flags & TDF_DETAILS))
369 fprintf (dump_file, "-------------------------\n");
370 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
373 lhs = gimple_assign_lhs (stmt);
375 /* Some of these constrains might be too conservative. */
376 if (stmt_ends_bb_p (stmt)
377 || gimple_has_volatile_ops (stmt)
378 || (TREE_CODE (lhs) == SSA_NAME
379 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
380 || gimple_has_side_effects (stmt))
382 if (dump_file && (dump_flags & TDF_DETAILS))
383 fprintf (dump_file, "stmt not suitable for ifcvt\n");
384 return false;
387 /* See if it needs speculative loading or not. */
388 if (bb != loop->header
389 && gimple_assign_rhs_could_trap_p (stmt))
391 if (dump_file && (dump_flags & TDF_DETAILS))
392 fprintf (dump_file, "tree could trap...\n");
393 return false;
396 if (TREE_CODE (lhs) != SSA_NAME
397 && bb != loop->header
398 && !bb_with_exit_edge_p (loop, bb))
400 if (dump_file && (dump_flags & TDF_DETAILS))
402 fprintf (dump_file, "LHS is not var\n");
403 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
405 return false;
408 return true;
411 /* Return true, iff STMT is if-convertible.
412 Statement is if-convertible if,
413 - It is if-convertible GIMPLE_ASSGIN
414 - It is GIMPLE_LABEL or GIMPLE_COND.
415 STMT is inside block BB, which is inside loop LOOP. */
417 static bool
418 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
420 switch (gimple_code (stmt))
422 case GIMPLE_LABEL:
423 break;
425 case GIMPLE_ASSIGN:
427 if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt))
428 return false;
429 break;
431 case GIMPLE_COND:
432 break;
434 default:
435 /* Don't know what to do with 'em so don't do anything. */
436 if (dump_file && (dump_flags & TDF_DETAILS))
438 fprintf (dump_file, "don't know what to do\n");
439 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
441 return false;
442 break;
445 return true;
448 /* Return true, iff BB is if-convertible.
449 Note: This routine does _not_ check basic block statements and phis.
450 Basic block is not if-convertible if,
451 - Basic block is non-empty and it is after exit block (in BFS order).
452 - Basic block is after exit block but before latch.
453 - Basic block edge(s) is not normal.
454 EXIT_BB_SEEN is true if basic block with exit edge is already seen.
455 BB is inside loop LOOP. */
457 static bool
458 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
460 edge e;
461 edge_iterator ei;
463 if (dump_file && (dump_flags & TDF_DETAILS))
464 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
466 if (exit_bb)
468 if (bb != loop->latch)
470 if (dump_file && (dump_flags & TDF_DETAILS))
471 fprintf (dump_file, "basic block after exit bb but before latch\n");
472 return false;
474 else if (!empty_block_p (bb))
476 if (dump_file && (dump_flags & TDF_DETAILS))
477 fprintf (dump_file, "non empty basic block after exit bb\n");
478 return false;
480 else if (bb == loop->latch
481 && bb != exit_bb
482 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
484 if (dump_file && (dump_flags & TDF_DETAILS))
485 fprintf (dump_file, "latch is not dominated by exit_block\n");
486 return false;
490 /* Be less adventurous and handle only normal edges. */
491 FOR_EACH_EDGE (e, ei, bb->succs)
492 if (e->flags &
493 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
495 if (dump_file && (dump_flags & TDF_DETAILS))
496 fprintf (dump_file,"Difficult to handle edges\n");
497 return false;
500 return true;
503 /* Return true, iff LOOP is if-convertible.
504 LOOP is if-convertible if,
505 - It is innermost.
506 - It has two or more basic blocks.
507 - It has only one exit.
508 - Loop header is not the exit edge.
509 - If its basic blocks and phi nodes are if convertible. See above for
510 more info.
511 FOR_VECTORIZER enables vectorizer specific checks. For example, support
512 for vector conditions, data dependency checks etc.. (Not implemented yet). */
514 static bool
515 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
517 basic_block bb;
518 gimple_stmt_iterator itr;
519 unsigned int i;
520 edge e;
521 edge_iterator ei;
522 basic_block exit_bb = NULL;
524 /* Handle only inner most loop. */
525 if (!loop || loop->inner)
527 if (dump_file && (dump_flags & TDF_DETAILS))
528 fprintf (dump_file, "not inner most loop\n");
529 return false;
532 /* If only one block, no need for if-conversion. */
533 if (loop->num_nodes <= 2)
535 if (dump_file && (dump_flags & TDF_DETAILS))
536 fprintf (dump_file, "less than 2 basic blocks\n");
537 return false;
540 /* More than one loop exit is too much to handle. */
541 if (!single_exit (loop))
543 if (dump_file && (dump_flags & TDF_DETAILS))
544 fprintf (dump_file, "multiple exits\n");
545 return false;
548 /* ??? Check target's vector conditional operation support for vectorizer. */
550 /* If one of the loop header's edge is exit edge then do not apply
551 if-conversion. */
552 FOR_EACH_EDGE (e, ei, loop->header->succs)
554 if (loop_exit_edge_p (loop, e))
555 return false;
558 calculate_dominance_info (CDI_DOMINATORS);
559 calculate_dominance_info (CDI_POST_DOMINATORS);
561 /* Allow statements that can be handled during if-conversion. */
562 ifc_bbs = get_loop_body_in_if_conv_order (loop);
563 if (!ifc_bbs)
565 if (dump_file && (dump_flags & TDF_DETAILS))
566 fprintf (dump_file,"Irreducible loop\n");
567 free_dominance_info (CDI_POST_DOMINATORS);
568 return false;
571 for (i = 0; i < loop->num_nodes; i++)
573 bb = ifc_bbs[i];
575 if (!if_convertible_bb_p (loop, bb, exit_bb))
576 return false;
578 /* Check statements. */
579 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
580 if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
581 return false;
582 /* ??? Check data dependency for vectorizer. */
584 /* What about phi nodes ? */
585 itr = gsi_start_phis (bb);
587 /* Clear aux field of incoming edges to a bb with a phi node. */
588 if (!gsi_end_p (itr))
589 FOR_EACH_EDGE (e, ei, bb->preds)
590 e->aux = NULL;
592 /* Check statements. */
593 for (; !gsi_end_p (itr); gsi_next (&itr))
594 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
595 return false;
597 if (bb_with_exit_edge_p (loop, bb))
598 exit_bb = bb;
601 /* OK. Did not find any potential issues so go ahead in if-convert
602 this loop. Now there is no looking back. */
603 if (dump_file)
604 fprintf (dump_file,"Applying if-conversion\n");
606 free_dominance_info (CDI_POST_DOMINATORS);
607 return true;
610 /* Add condition COND into predicate list of basic block BB. */
612 static void
613 add_to_predicate_list (basic_block bb, tree new_cond)
615 tree cond = (tree) bb->aux;
617 if (cond)
618 cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
619 unshare_expr (cond), new_cond);
620 else
621 cond = new_cond;
623 bb->aux = cond;
626 /* Add condition COND into BB's predicate list. PREV_COND is
627 existing condition. */
629 static tree
630 add_to_dst_predicate_list (struct loop * loop, edge e,
631 tree prev_cond, tree cond,
632 gimple_stmt_iterator *gsi)
634 tree new_cond = NULL_TREE;
636 if (!flow_bb_inside_loop_p (loop, e->dest))
637 return NULL_TREE;
639 if (prev_cond == boolean_true_node || !prev_cond)
640 new_cond = unshare_expr (cond);
641 else
643 tree tmp;
644 gimple tmp_stmt = NULL;
646 prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
647 true, NULL, true, GSI_SAME_STMT);
649 cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
650 true, NULL, true, GSI_SAME_STMT);
652 /* Add the condition to aux field of the edge. In case edge
653 destination is a PHI node, this condition will be ANDed with
654 block predicate to construct complete condition. */
655 e->aux = cond;
657 /* new_cond == prev_cond AND cond */
658 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
659 unshare_expr (prev_cond), cond);
660 tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
661 gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
662 new_cond = gimple_assign_lhs (tmp_stmt);
664 add_to_predicate_list (e->dest, new_cond);
665 return new_cond;
668 /* During if-conversion aux field from basic block structure is used to hold
669 predicate list. Clean each basic block's predicate list for the given LOOP.
670 Also clean aux field of successor edges, used to hold true and false
671 condition from conditional expression. */
673 static void
674 clean_predicate_lists (struct loop *loop)
676 basic_block *bb;
677 unsigned int i;
678 edge e;
679 edge_iterator ei;
681 bb = get_loop_body (loop);
682 for (i = 0; i < loop->num_nodes; i++)
684 bb[i]->aux = NULL;
685 FOR_EACH_EDGE (e, ei, bb[i]->succs)
686 e->aux = NULL;
688 free (bb);
691 /* Basic block BB has two predecessors. Using predecessor's aux field, set
692 appropriate condition COND for the PHI node replacement. Return true block
693 whose phi arguments are selected when cond is true. */
695 static basic_block
696 find_phi_replacement_condition (struct loop *loop,
697 basic_block bb, tree *cond,
698 gimple_stmt_iterator *gsi)
700 edge first_edge, second_edge;
701 tree tmp_cond;
703 gcc_assert (EDGE_COUNT (bb->preds) == 2);
704 first_edge = EDGE_PRED (bb, 0);
705 second_edge = EDGE_PRED (bb, 1);
707 /* Use condition based on following criteria:
709 S1: x = !c ? a : b;
711 S2: x = c ? b : a;
713 S2 is preferred over S1. Make 'b' first_bb and use its condition.
715 2) Do not make loop header first_bb.
718 S1: x = !(c == d)? a : b;
720 S21: t1 = c == d;
721 S22: x = t1 ? b : a;
723 S3: x = (c == d) ? b : a;
725 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
726 its condition.
728 4) If pred B is dominated by pred A then use pred B's condition.
729 See PR23115. */
731 /* Select condition that is not TRUTH_NOT_EXPR. */
732 tmp_cond = (tree) (first_edge->src)->aux;
733 gcc_assert (tmp_cond);
735 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
737 edge tmp_edge;
739 tmp_edge = first_edge;
740 first_edge = second_edge;
741 second_edge = tmp_edge;
744 /* Check if FIRST_BB is loop header or not and make sure that
745 FIRST_BB does not dominate SECOND_BB. */
746 if (first_edge->src == loop->header
747 || dominated_by_p (CDI_DOMINATORS,
748 second_edge->src, first_edge->src))
750 *cond = (tree) (second_edge->src)->aux;
752 /* If there is a condition on an incoming edge,
753 AND it with the incoming bb predicate. */
754 if (second_edge->aux)
755 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
756 *cond, (tree) second_edge->aux);
758 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
759 /* We can be smart here and choose inverted
760 condition without switching bbs. */
761 *cond = invert_truthvalue (*cond);
762 else
763 /* Select non loop header bb. */
764 first_edge = second_edge;
766 else
768 /* FIRST_BB is not loop header */
769 *cond = (tree) (first_edge->src)->aux;
771 /* If there is a condition on an incoming edge,
772 AND it with the incoming bb predicate. */
773 if (first_edge->aux)
774 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
775 *cond, (tree) first_edge->aux);
778 /* Create temp. for the condition. Vectorizer prefers to have gimple
779 value as condition. Various targets use different means to communicate
780 condition in vector compare operation. Using gimple value allows
781 compiler to emit vector compare and select RTL without exposing
782 compare's result. */
783 *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
784 false, NULL_TREE,
785 true, GSI_SAME_STMT);
786 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
788 gimple new_stmt;
790 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
791 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
792 *cond = gimple_assign_lhs (new_stmt);
795 gcc_assert (*cond);
797 return first_edge->src;
801 /* Replace PHI node with conditional modify expr using COND.
802 This routine does not handle PHI nodes with more than two arguments.
803 For example,
804 S1: A = PHI <x1(1), x2(5)
805 is converted into,
806 S2: A = cond ? x1 : x2;
807 S2 is inserted at the top of basic block's statement list.
808 When COND is true, phi arg from TRUE_BB is selected.
811 static void
812 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
813 basic_block true_bb,
814 gimple_stmt_iterator *gsi)
816 gimple new_stmt;
817 basic_block bb;
818 tree rhs;
819 tree arg_0, arg_1;
821 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
823 /* If this is not filtered earlier, then now it is too late. */
824 gcc_assert (gimple_phi_num_args (phi) == 2);
826 /* Find basic block and initialize iterator. */
827 bb = gimple_bb (phi);
829 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
830 if (EDGE_PRED (bb, 1)->src == true_bb)
832 arg_0 = gimple_phi_arg_def (phi, 1);
833 arg_1 = gimple_phi_arg_def (phi, 0);
835 else
837 arg_0 = gimple_phi_arg_def (phi, 0);
838 arg_1 = gimple_phi_arg_def (phi, 1);
841 /* Build new RHS using selected condition and arguments. */
842 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
843 unshare_expr (cond), unshare_expr (arg_0),
844 unshare_expr (arg_1));
846 /* Create new GIMPLE_ASSIGN statement using RHS. */
847 new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
849 /* Make new statement definition of the original phi result. */
850 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
852 /* Insert using iterator. */
853 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
854 update_stmt (new_stmt);
856 if (dump_file && (dump_flags & TDF_DETAILS))
858 fprintf (dump_file, "new phi replacement stmt\n");
859 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
863 /* Process phi nodes for the given LOOP. Replace phi nodes with cond
864 modify expr. */
866 static void
867 process_phi_nodes (struct loop *loop)
869 basic_block bb;
870 unsigned int orig_loop_num_nodes = loop->num_nodes;
871 unsigned int i;
873 /* Replace phi nodes with cond. modify expr. */
874 for (i = 1; i < orig_loop_num_nodes; i++)
876 gimple phi;
877 tree cond = NULL_TREE;
878 gimple_stmt_iterator gsi, phi_gsi;
879 basic_block true_bb = NULL;
880 bb = ifc_bbs[i];
882 if (bb == loop->header)
883 continue;
885 phi_gsi = gsi_start_phis (bb);
886 gsi = gsi_after_labels (bb);
888 /* BB has two predecessors. Using predecessor's aux field, set
889 appropriate condition for the PHI node replacement. */
890 if (!gsi_end_p (phi_gsi))
891 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
893 while (!gsi_end_p (phi_gsi))
895 phi = gsi_stmt (phi_gsi);
896 replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
897 release_phi_node (phi);
898 gsi_next (&phi_gsi);
900 set_phi_nodes (bb, NULL);
902 return;
905 /* Combine all basic block from the given LOOP into one or two super
906 basic block. Replace PHI nodes with conditional modify expression. */
908 static void
909 combine_blocks (struct loop *loop)
911 basic_block bb, exit_bb, merge_target_bb;
912 unsigned int orig_loop_num_nodes = loop->num_nodes;
913 unsigned int i;
914 edge e;
915 edge_iterator ei;
917 /* Process phi nodes to prepare blocks for merge. */
918 process_phi_nodes (loop);
920 /* Merge basic blocks. First remove all the edges in the loop, except
921 for those from the exit block. */
922 exit_bb = NULL;
923 for (i = 0; i < orig_loop_num_nodes; i++)
925 bb = ifc_bbs[i];
926 if (bb_with_exit_edge_p (loop, bb))
928 exit_bb = bb;
929 break;
932 gcc_assert (exit_bb != loop->latch);
934 for (i = 1; i < orig_loop_num_nodes; i++)
936 bb = ifc_bbs[i];
938 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
940 if (e->src == exit_bb)
941 ei_next (&ei);
942 else
943 remove_edge (e);
947 if (exit_bb != NULL)
949 if (exit_bb != loop->header)
951 /* Connect this node with loop header. */
952 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
953 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
956 /* Redirect non-exit edges to loop->latch. */
957 FOR_EACH_EDGE (e, ei, exit_bb->succs)
959 if (!loop_exit_edge_p (loop, e))
960 redirect_edge_and_branch (e, loop->latch);
962 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
964 else
966 /* If the loop does not have exit then reconnect header and latch. */
967 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
968 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
971 merge_target_bb = loop->header;
972 for (i = 1; i < orig_loop_num_nodes; i++)
974 gimple_stmt_iterator gsi;
975 gimple_stmt_iterator last;
977 bb = ifc_bbs[i];
979 if (bb == exit_bb || bb == loop->latch)
980 continue;
982 /* Remove labels and make stmts member of loop->header. */
983 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
985 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
986 gsi_remove (&gsi, true);
987 else
989 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
990 gsi_next (&gsi);
994 /* Update stmt list. */
995 last = gsi_last_bb (merge_target_bb);
996 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
997 set_bb_seq (bb, NULL);
999 delete_basic_block (bb);
1002 /* Now if possible, merge loop header and block with exit edge.
1003 This reduces number of basic blocks to 2. Auto vectorizer addresses
1004 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
1005 if (exit_bb
1006 && exit_bb != loop->header
1007 && can_merge_blocks_p (loop->header, exit_bb))
1008 merge_blocks (loop->header, exit_bb);
1011 /* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
1012 to the new variable. */
1014 static gimple
1015 ifc_temp_var (tree type, tree exp)
1017 const char *name = "_ifc_";
1018 tree var, new_name;
1019 gimple stmt;
1021 /* Create new temporary variable. */
1022 var = create_tmp_var (type, name);
1023 add_referenced_var (var);
1025 /* Build new statement to assign EXP to new variable. */
1026 stmt = gimple_build_assign (var, exp);
1028 /* Get SSA name for the new variable and set make new statement
1029 its definition statement. */
1030 new_name = make_ssa_name (var, stmt);
1031 gimple_assign_set_lhs (stmt, new_name);
1032 SSA_NAME_DEF_STMT (new_name) = stmt;
1033 update_stmt (stmt);
1035 return stmt;
1039 /* Return TRUE iff, all pred blocks of BB are visited.
1040 Bitmap VISITED keeps history of visited blocks. */
1042 static bool
1043 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1045 edge e;
1046 edge_iterator ei;
1047 FOR_EACH_EDGE (e, ei, bb->preds)
1048 if (!bitmap_bit_p (*visited, e->src->index))
1049 return false;
1051 return true;
1054 /* Get body of a LOOP in suitable order for if-conversion.
1055 It is caller's responsibility to deallocate basic block
1056 list. If-conversion suitable order is, BFS order with one
1057 additional constraint. Select block in BFS block, if all
1058 pred are already selected. */
1060 static basic_block *
1061 get_loop_body_in_if_conv_order (const struct loop *loop)
1063 basic_block *blocks, *blocks_in_bfs_order;
1064 basic_block bb;
1065 bitmap visited;
1066 unsigned int index = 0;
1067 unsigned int visited_count = 0;
1069 gcc_assert (loop->num_nodes);
1070 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1072 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1073 visited = BITMAP_ALLOC (NULL);
1075 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1077 index = 0;
1078 while (index < loop->num_nodes)
1080 bb = blocks_in_bfs_order [index];
1082 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1084 free (blocks_in_bfs_order);
1085 BITMAP_FREE (visited);
1086 free (blocks);
1087 return NULL;
1089 if (!bitmap_bit_p (visited, bb->index))
1091 if (pred_blocks_visited_p (bb, &visited)
1092 || bb == loop->header)
1094 /* This block is now visited. */
1095 bitmap_set_bit (visited, bb->index);
1096 blocks[visited_count++] = bb;
1099 index++;
1100 if (index == loop->num_nodes
1101 && visited_count != loop->num_nodes)
1103 /* Not done yet. */
1104 index = 0;
1107 free (blocks_in_bfs_order);
1108 BITMAP_FREE (visited);
1109 return blocks;
1112 /* Return true if one of the basic block BB edge is exit of LOOP. */
1114 static bool
1115 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1117 edge e;
1118 edge_iterator ei;
1119 bool exit_edge_found = false;
1121 FOR_EACH_EDGE (e, ei, bb->succs)
1122 if (loop_exit_edge_p (loop, e))
1124 exit_edge_found = true;
1125 break;
1128 return exit_edge_found;
1131 /* Tree if-conversion pass management. */
1133 static unsigned int
1134 main_tree_if_conversion (void)
1136 loop_iterator li;
1137 struct loop *loop;
1139 if (number_of_loops () <= 1)
1140 return 0;
1142 FOR_EACH_LOOP (li, loop, 0)
1144 tree_if_conversion (loop, true);
1146 return 0;
1149 static bool
1150 gate_tree_if_conversion (void)
1152 return flag_tree_vectorize != 0;
1155 struct gimple_opt_pass pass_if_conversion =
1158 GIMPLE_PASS,
1159 "ifcvt", /* name */
1160 gate_tree_if_conversion, /* gate */
1161 main_tree_if_conversion, /* execute */
1162 NULL, /* sub */
1163 NULL, /* next */
1164 0, /* static_pass_number */
1165 TV_NONE, /* tv_id */
1166 PROP_cfg | PROP_ssa, /* properties_required */
1167 0, /* properties_provided */
1168 0, /* properties_destroyed */
1169 0, /* todo_flags_start */
1170 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow
1171 /* todo_flags_finish */