OSDN Git Service

* ipa-reference.c: Do not include c-common.h, include splay-tree.h.
[pf3gnuchains/gcc-fork.git] / gcc / tree-if-conv.c
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>
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>.  */
21
22 /* This pass implements tree level if-conversion transformation of loops.
23    Initial goal is to help vectorizer vectorize loops with conditions.
24
25    A short description of if-conversion:
26
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
37
38      Sample transformation:
39
40      INPUT
41      -----
42
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>;
47
48      <L17>:;
49      goto <bb 3> (<L3>);
50
51      <L1>:;
52
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>;
58
59      <L19>:;
60      goto <bb 1> (<L0>);
61
62      <L18>:;
63
64      OUTPUT
65      ------
66
67      # i_23 = PHI <0(0), i_18(10)>;
68      <L0>:;
69      j_15 = A[i_23];
70
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>;
76
77      <L19>:;
78      goto <bb 1> (<L0>);
79
80      <L18>:;
81 */
82
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"
102
103
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);
133
134 /* List of basic blocks in if-conversion-suitable order.  */
135 static basic_block *ifc_bbs;
136
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).  */
143
144 static bool
145 tree_if_conversion (struct loop *loop, bool for_vectorizer)
146 {
147   basic_block bb;
148   gimple_stmt_iterator itr;
149   unsigned int i;
150
151   ifc_bbs = NULL;
152
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))
156     {
157       if (dump_file && (dump_flags & TDF_DETAILS))
158         fprintf (dump_file,"-------------------------\n");
159       if (ifc_bbs)
160         {
161           free (ifc_bbs);
162           ifc_bbs = NULL;
163         }
164       free_dominance_info (CDI_POST_DOMINATORS);
165       return false;
166     }
167
168   /* Do actual work now.  */
169   for (i = 0; i < loop->num_nodes; i++)
170     {
171       tree cond;
172
173       bb = ifc_bbs [i];
174
175       /* Update condition using predicate list.  */
176       cond = (tree) bb->aux;
177
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 */)
182         {
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);
187         }
188
189       /* If current bb has only one successor, then consider it as an
190          unconditional goto.  */
191       if (single_succ_p (bb))
192         {
193           basic_block bb_n = single_succ (bb);
194
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;
200
201           add_to_predicate_list (bb_n, cond);
202         }
203     }
204
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);
209
210   /* clean up */
211   clean_predicate_lists (loop);
212   free (ifc_bbs);
213   ifc_bbs = NULL;
214
215   return true;
216 }
217
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.  */
224
225 static tree
226 tree_if_convert_stmt (struct loop *  loop, gimple t, tree cond,
227                       gimple_stmt_iterator *gsi)
228 {
229   if (dump_file && (dump_flags & TDF_DETAILS))
230     {
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);
234     }
235
236   switch (gimple_code (t))
237     {
238       /* Labels are harmless here.  */
239     case GIMPLE_LABEL:
240       break;
241
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;
249
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;
256
257     default:
258       gcc_unreachable ();
259     }
260   return cond;
261 }
262
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.  */
267
268 static void
269 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
270                            gimple_stmt_iterator *gsi)
271 {
272   tree c, c2;
273   edge true_edge, false_edge;
274
275   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
276
277   c = fold_build2 (gimple_cond_code (stmt), boolean_type_node,
278                    gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
279
280   extract_true_false_edges_from_block (gimple_bb (stmt),
281                                        &true_edge, &false_edge);
282
283   /* Add new condition into destination's predicate list.  */
284
285   /* If C is true then TRUE_EDGE is taken.  */
286   add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
287
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);
291
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)))
296     {
297       gsi_remove (gsi, true);
298       cond = NULL_TREE;
299     }
300   return;
301 }
302
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.  */
309
310 static bool
311 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
312 {
313   if (dump_file && (dump_flags & TDF_DETAILS))
314     {
315       fprintf (dump_file, "-------------------------\n");
316       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
317     }
318
319   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
320     {
321       if (dump_file && (dump_flags & TDF_DETAILS))
322         fprintf (dump_file, "More than two phi node args.\n");
323       return false;
324     }
325
326   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
327     {
328       imm_use_iterator imm_iter;
329       use_operand_p use_p;
330
331       if (bb != loop->header)
332         {
333           if (dump_file && (dump_flags & TDF_DETAILS))
334             fprintf (dump_file, "Virtual phi not on loop header.\n");
335           return false;
336         }
337       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
338         {
339           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
340             {
341               if (dump_file && (dump_flags & TDF_DETAILS))
342                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
343               return false;
344             }
345         }
346     }
347
348   return true;
349 }
350
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.  */
357
358 static bool
359 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
360                                      gimple stmt)
361 {
362   tree lhs;
363
364   if (!is_gimple_assign (stmt))
365     return false;
366
367   if (dump_file && (dump_flags & TDF_DETAILS))
368     {
369       fprintf (dump_file, "-------------------------\n");
370       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
371     }
372
373   lhs = gimple_assign_lhs (stmt);
374
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))
381     {
382       if (dump_file && (dump_flags & TDF_DETAILS))
383         fprintf (dump_file, "stmt not suitable for ifcvt\n");
384       return false;
385     }
386
387   /* See if it needs speculative loading or not.  */
388   if (bb != loop->header
389       && gimple_assign_rhs_could_trap_p (stmt))
390     {
391       if (dump_file && (dump_flags & TDF_DETAILS))
392         fprintf (dump_file, "tree could trap...\n");
393       return false;
394     }
395
396   if (TREE_CODE (lhs) != SSA_NAME
397       && bb != loop->header
398       && !bb_with_exit_edge_p (loop, bb))
399     {
400       if (dump_file && (dump_flags & TDF_DETAILS))
401         {
402           fprintf (dump_file, "LHS is not var\n");
403           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
404         }
405       return false;
406     }
407
408   return true;
409 }
410
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.  */
416
417 static bool
418 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
419 {
420   switch (gimple_code (stmt))
421     {
422     case GIMPLE_LABEL:
423       break;
424
425     case GIMPLE_ASSIGN:
426
427       if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt))
428         return false;
429       break;
430
431     case GIMPLE_COND:
432       break;
433
434     default:
435       /* Don't know what to do with 'em so don't do anything.  */
436       if (dump_file && (dump_flags & TDF_DETAILS))
437         {
438           fprintf (dump_file, "don't know what to do\n");
439           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
440         }
441       return false;
442       break;
443     }
444
445   return true;
446 }
447
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.  */
456
457 static bool
458 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
459 {
460   edge e;
461   edge_iterator ei;
462
463   if (dump_file && (dump_flags & TDF_DETAILS))
464     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
465
466   if (exit_bb)
467     {
468       if (bb != loop->latch)
469         {
470           if (dump_file && (dump_flags & TDF_DETAILS))
471             fprintf (dump_file, "basic block after exit bb but before latch\n");
472           return false;
473         }
474       else if (!empty_block_p (bb))
475         {
476           if (dump_file && (dump_flags & TDF_DETAILS))
477             fprintf (dump_file, "non empty basic block after exit bb\n");
478           return false;
479         }
480       else if (bb == loop->latch 
481                && bb != exit_bb
482                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
483           {
484             if (dump_file && (dump_flags & TDF_DETAILS))
485               fprintf (dump_file, "latch is not dominated by exit_block\n");
486             return false;
487           }
488     }
489
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))
494       {
495         if (dump_file && (dump_flags & TDF_DETAILS))
496           fprintf (dump_file,"Difficult to handle edges\n");
497         return false;
498       }
499
500   return true;
501 }
502
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).  */
513
514 static bool
515 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
516 {
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;
523
524   /* Handle only inner most loop.  */
525   if (!loop || loop->inner)
526     {
527       if (dump_file && (dump_flags & TDF_DETAILS))
528         fprintf (dump_file, "not inner most loop\n");
529       return false;
530     }
531
532   /* If only one block, no need for if-conversion.  */
533   if (loop->num_nodes <= 2)
534     {
535       if (dump_file && (dump_flags & TDF_DETAILS))
536         fprintf (dump_file, "less than 2 basic blocks\n");
537       return false;
538     }
539
540   /* More than one loop exit is too much to handle.  */
541   if (!single_exit (loop))
542     {
543       if (dump_file && (dump_flags & TDF_DETAILS))
544         fprintf (dump_file, "multiple exits\n");
545       return false;
546     }
547
548   /* ??? Check target's vector conditional operation support for vectorizer.  */
549
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)
553     {
554       if (loop_exit_edge_p (loop, e))
555         return false;
556     }
557
558   calculate_dominance_info (CDI_DOMINATORS);
559   calculate_dominance_info (CDI_POST_DOMINATORS);
560
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)
564     {
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;
569     }
570
571   for (i = 0; i < loop->num_nodes; i++)
572     {
573       bb = ifc_bbs[i];
574
575       if (!if_convertible_bb_p (loop, bb, exit_bb))
576         return false;
577
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.  */
583
584       /* What about phi nodes ? */
585       itr = gsi_start_phis (bb);
586
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;
591
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;
596
597       if (bb_with_exit_edge_p (loop, bb))
598         exit_bb = bb;
599     }
600
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");
605
606   free_dominance_info (CDI_POST_DOMINATORS);
607   return true;
608 }
609
610 /* Add condition COND into predicate list of basic block BB.  */
611
612 static void
613 add_to_predicate_list (basic_block bb, tree new_cond)
614 {
615   tree cond = (tree) bb->aux;
616
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;
622
623   bb->aux = cond;
624 }
625
626 /* Add condition COND into BB's predicate list.  PREV_COND is
627    existing condition.  */
628
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)
633 {
634   tree new_cond = NULL_TREE;
635
636   if (!flow_bb_inside_loop_p (loop, e->dest))
637     return NULL_TREE;
638
639   if (prev_cond == boolean_true_node || !prev_cond)
640     new_cond = unshare_expr (cond);
641   else
642     {
643       tree tmp;
644       gimple tmp_stmt = NULL;
645
646       prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
647                                             true, NULL, true, GSI_SAME_STMT);
648
649       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
650                                        true, NULL, true, GSI_SAME_STMT);
651
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;
656
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);
663     }
664   add_to_predicate_list (e->dest, new_cond);
665   return new_cond;
666 }
667
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.  */
672
673 static void
674 clean_predicate_lists (struct loop *loop)
675 {
676   basic_block *bb;
677   unsigned int i;
678   edge e;
679   edge_iterator ei;
680
681   bb = get_loop_body (loop);
682   for (i = 0; i < loop->num_nodes; i++)
683     {
684       bb[i]->aux = NULL;
685       FOR_EACH_EDGE (e, ei, bb[i]->succs)
686         e->aux = NULL;
687     }
688   free (bb);
689 }
690
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.  */
694
695 static basic_block
696 find_phi_replacement_condition (struct loop *loop, 
697                                 basic_block bb, tree *cond,
698                                 gimple_stmt_iterator *gsi)
699 {
700   edge first_edge, second_edge;
701   tree tmp_cond;
702
703   gcc_assert (EDGE_COUNT (bb->preds) == 2);
704   first_edge = EDGE_PRED (bb, 0);
705   second_edge = EDGE_PRED (bb, 1);
706
707   /* Use condition based on following criteria:
708      1)
709        S1: x = !c ? a : b;
710
711        S2: x = c ? b : a;
712
713        S2 is preferred over S1. Make 'b' first_bb and use its condition.
714        
715      2) Do not make loop header first_bb.
716
717      3)
718        S1: x = !(c == d)? a : b;
719
720        S21: t1 = c == d;
721        S22: x = t1 ? b : a;
722
723        S3: x = (c == d) ? b : a;
724
725        S3 is preferred over S1 and S2*, Make 'b' first_bb and use 
726        its condition.
727
728      4) If  pred B is dominated by pred A then use pred B's condition.
729         See PR23115.  */
730
731   /* Select condition that is not TRUTH_NOT_EXPR.  */
732   tmp_cond = (tree) (first_edge->src)->aux;
733   gcc_assert (tmp_cond);
734
735   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
736     {
737       edge tmp_edge;
738
739       tmp_edge = first_edge;
740       first_edge = second_edge;
741       second_edge = tmp_edge;
742     }
743
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))
749     {
750       *cond = (tree) (second_edge->src)->aux;
751
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);
757
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;
765     }
766   else
767     {
768       /* FIRST_BB is not loop header */
769       *cond = (tree) (first_edge->src)->aux;
770
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);
776     }
777
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))
787     {
788       gimple new_stmt;
789
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);
793     }
794
795   gcc_assert (*cond);
796
797   return first_edge->src;
798 }
799
800
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.
809 */
810
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)
815 {
816   gimple new_stmt;
817   basic_block bb;
818   tree rhs;
819   tree arg_0, arg_1;
820
821   gcc_assert (gimple_code (phi) == GIMPLE_PHI);
822   
823   /* If this is not filtered earlier, then now it is too late.  */
824   gcc_assert (gimple_phi_num_args (phi) == 2);
825
826   /* Find basic block and initialize iterator.  */
827   bb = gimple_bb (phi);
828
829   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
830   if (EDGE_PRED (bb, 1)->src == true_bb)
831     {
832       arg_0 = gimple_phi_arg_def (phi, 1);
833       arg_1 = gimple_phi_arg_def (phi, 0);
834     }
835   else
836     {
837       arg_0 = gimple_phi_arg_def (phi, 0);
838       arg_1 = gimple_phi_arg_def (phi, 1);
839     }
840
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));
845
846   /* Create new GIMPLE_ASSIGN statement using RHS.  */
847   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
848
849   /* Make new statement definition of the original phi result.  */
850   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
851
852   /* Insert using iterator.  */
853   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
854   update_stmt (new_stmt);
855
856   if (dump_file && (dump_flags & TDF_DETAILS))
857     {
858       fprintf (dump_file, "new phi replacement stmt\n");
859       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
860     }
861 }
862
863 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
864    modify expr.  */
865
866 static void
867 process_phi_nodes (struct loop *loop)
868 {
869   basic_block bb;
870   unsigned int orig_loop_num_nodes = loop->num_nodes;
871   unsigned int i;
872
873   /* Replace phi nodes with cond. modify expr.  */
874   for (i = 1; i < orig_loop_num_nodes; i++)
875     {
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];
881
882       if (bb == loop->header)
883         continue;
884
885       phi_gsi = gsi_start_phis (bb);
886       gsi = gsi_after_labels (bb);
887
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);
892
893       while (!gsi_end_p (phi_gsi))
894         {
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);
899         }
900       set_phi_nodes (bb, NULL);
901     }
902   return;
903 }
904
905 /* Combine all basic block from the given LOOP into one or two super
906    basic block.  Replace PHI nodes with conditional modify expression.  */
907
908 static void
909 combine_blocks (struct loop *loop)
910 {
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;
916
917   /* Process phi nodes to prepare blocks for merge.  */
918   process_phi_nodes (loop);
919
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++)
924     {
925       bb = ifc_bbs[i];
926       if (bb_with_exit_edge_p (loop, bb))
927         {
928           exit_bb = bb;
929           break;
930         }
931     }
932   gcc_assert (exit_bb != loop->latch);
933
934   for (i = 1; i < orig_loop_num_nodes; i++)
935     {
936       bb = ifc_bbs[i];
937
938       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
939         {
940           if (e->src == exit_bb)
941             ei_next (&ei);
942           else
943             remove_edge (e);
944         }
945     }
946
947   if (exit_bb != NULL)
948     {
949       if (exit_bb != loop->header)
950         {
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);
954         }
955
956       /* Redirect non-exit edges to loop->latch.  */
957       FOR_EACH_EDGE (e, ei, exit_bb->succs)
958         {
959           if (!loop_exit_edge_p (loop, e))
960             redirect_edge_and_branch (e, loop->latch);
961         }
962       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
963     }
964   else
965     {
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);
969     }
970
971   merge_target_bb = loop->header;
972   for (i = 1; i < orig_loop_num_nodes; i++)
973     {
974       gimple_stmt_iterator gsi;
975       gimple_stmt_iterator last;
976
977       bb = ifc_bbs[i];
978
979       if (bb == exit_bb || bb == loop->latch)
980         continue;
981
982       /* Remove labels and make stmts member of loop->header.  */
983       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
984         {
985           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
986             gsi_remove (&gsi, true);
987           else
988             {
989               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
990               gsi_next (&gsi);
991             }
992         }
993
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);
998
999       delete_basic_block (bb);
1000     }
1001
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);
1009 }
1010
1011 /* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
1012    to the new variable.  */
1013
1014 static gimple
1015 ifc_temp_var (tree type, tree exp)
1016 {
1017   const char *name = "_ifc_";
1018   tree var, new_name;
1019   gimple stmt;
1020
1021   /* Create new temporary variable.  */
1022   var = create_tmp_var (type, name);
1023   add_referenced_var (var);
1024
1025   /* Build new statement to assign EXP to new variable.  */
1026   stmt = gimple_build_assign (var, exp);
1027
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);
1034
1035   return stmt;
1036 }
1037
1038
1039 /* Return TRUE iff, all pred blocks of BB are visited.
1040    Bitmap VISITED keeps history of visited blocks.  */
1041
1042 static bool
1043 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1044 {
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;
1050
1051   return true;
1052 }
1053
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.  */
1059
1060 static basic_block *
1061 get_loop_body_in_if_conv_order (const struct loop *loop)
1062 {
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;
1068
1069   gcc_assert (loop->num_nodes);
1070   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1071
1072   blocks = XCNEWVEC (basic_block, loop->num_nodes);
1073   visited = BITMAP_ALLOC (NULL);
1074
1075   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1076
1077   index = 0;
1078   while (index < loop->num_nodes)
1079     {
1080       bb = blocks_in_bfs_order [index];
1081
1082       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1083         {
1084           free (blocks_in_bfs_order);
1085           BITMAP_FREE (visited);
1086           free (blocks);
1087           return NULL;
1088         }
1089       if (!bitmap_bit_p (visited, bb->index))
1090         {
1091           if (pred_blocks_visited_p (bb, &visited)
1092               || bb == loop->header)
1093             {
1094               /* This block is now visited.  */
1095               bitmap_set_bit (visited, bb->index);
1096               blocks[visited_count++] = bb;
1097             }
1098         }
1099       index++;
1100       if (index == loop->num_nodes
1101           && visited_count != loop->num_nodes)
1102         {
1103           /* Not done yet.  */
1104           index = 0;
1105         }
1106     }
1107   free (blocks_in_bfs_order);
1108   BITMAP_FREE (visited);
1109   return blocks;
1110 }
1111
1112 /* Return true if one of the basic block BB edge is exit of LOOP.  */
1113
1114 static bool
1115 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1116 {
1117   edge e;
1118   edge_iterator ei;
1119   bool exit_edge_found = false;
1120
1121   FOR_EACH_EDGE (e, ei, bb->succs)
1122     if (loop_exit_edge_p (loop, e))
1123       {
1124         exit_edge_found = true;
1125         break;
1126       }
1127
1128   return exit_edge_found;
1129 }
1130
1131 /* Tree if-conversion pass management.  */
1132
1133 static unsigned int
1134 main_tree_if_conversion (void)
1135 {
1136   loop_iterator li;
1137   struct loop *loop;
1138
1139   if (number_of_loops () <= 1)
1140     return 0;
1141
1142   FOR_EACH_LOOP (li, loop, 0)
1143     {
1144       tree_if_conversion (loop, true);
1145     }
1146   return 0;
1147 }
1148
1149 static bool
1150 gate_tree_if_conversion (void)
1151 {
1152   return flag_tree_vectorize != 0;
1153 }
1154
1155 struct gimple_opt_pass pass_if_conversion =
1156 {
1157  {
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 | PROP_alias,     /* 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 */
1172  }
1173 };