OSDN Git Service

PR tree-optimization/31966
[pf3gnuchains/gcc-fork.git] / gcc / tree-if-conv.c
1 /* If-conversion for vectorizer.
2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3    Contributed by Devang Patel <dpatel@apple.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
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 "c-common.h"
89 #include "flags.h"
90 #include "timevar.h"
91 #include "varray.h"
92 #include "rtl.h"
93 #include "basic-block.h"
94 #include "diagnostic.h"
95 #include "tree-flow.h"
96 #include "tree-dump.h"
97 #include "cfgloop.h"
98 #include "tree-chrec.h"
99 #include "tree-data-ref.h"
100 #include "tree-scalar-evolution.h"
101 #include "tree-pass.h"
102 #include "target.h"
103
104 /* local function prototypes */
105 static unsigned int main_tree_if_conversion (void);
106 static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
107                                   block_stmt_iterator *);
108 static void tree_if_convert_cond_expr (struct loop *, tree, tree,
109                                        block_stmt_iterator *);
110 static bool if_convertible_phi_p (struct loop *, basic_block, tree);
111 static bool if_convertible_gimple_modify_stmt_p (struct loop *, basic_block,
112                                                  tree);
113 static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
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                                        block_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                                                    block_stmt_iterator *);
124 static void replace_phi_with_cond_gimple_modify_stmt (tree, tree, basic_block,
125                                                block_stmt_iterator *);
126 static void process_phi_nodes (struct loop *);
127 static void combine_blocks (struct loop *);
128 static tree ifc_temp_var (tree, tree);
129 static bool pred_blocks_visited_p (basic_block, bitmap *);
130 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
131 static bool bb_with_exit_edge_p (struct loop *, basic_block);
132
133 /* List of basic blocks in if-conversion-suitable order.  */
134 static basic_block *ifc_bbs;
135
136 /* Main entry point.
137    Apply if-conversion to the LOOP. Return true if successful otherwise return
138    false. If false is returned then loop remains unchanged.
139    FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
140    for vectorizer or not. If it is used for vectorizer, additional checks are
141    used. (Vectorization checks are not yet implemented).  */
142
143 static bool
144 tree_if_conversion (struct loop *loop, bool for_vectorizer)
145 {
146   basic_block bb;
147   block_stmt_iterator itr;
148   unsigned int i;
149
150   ifc_bbs = NULL;
151
152   /* if-conversion is not appropriate for all loops. First, check if loop  is
153      if-convertible or not.  */
154   if (!if_convertible_loop_p (loop, for_vectorizer))
155     {
156       if (dump_file && (dump_flags & TDF_DETAILS))
157         fprintf (dump_file,"-------------------------\n");
158       if (ifc_bbs)
159         {
160           free (ifc_bbs);
161           ifc_bbs = NULL;
162         }
163       free_dominance_info (CDI_POST_DOMINATORS);
164       return false;
165     }
166
167   /* Do actual work now.  */
168   for (i = 0; i < loop->num_nodes; i++)
169     {
170       tree cond;
171
172       bb = ifc_bbs [i];
173
174       /* Update condition using predicate list.  */
175       cond = bb->aux;
176
177       /* Process all statements in this basic block.
178          Remove conditional expression, if any, and annotate
179          destination basic block(s) appropriately.  */
180       for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
181         {
182           tree t = bsi_stmt (itr);
183           cond = tree_if_convert_stmt (loop, t, cond, &itr);
184           if (!bsi_end_p (itr))
185             bsi_next (&itr);
186         }
187
188       /* If current bb has only one successor, then consider it as an
189          unconditional goto.  */
190       if (single_succ_p (bb))
191         {
192           basic_block bb_n = single_succ (bb);
193           if (cond != NULL_TREE)
194             add_to_predicate_list (bb_n, cond);
195         }
196     }
197
198   /* Now, all statements are if-converted and basic blocks are
199      annotated appropriately. Combine all basic block into one huge
200      basic block.  */
201   combine_blocks (loop);
202
203   /* clean up */
204   clean_predicate_lists (loop);
205   free (ifc_bbs);
206   ifc_bbs = NULL;
207
208   return true;
209 }
210
211 /* if-convert stmt T which is part of LOOP.
212    If T is a GIMPLE_MODIFY_STMT than it is converted into conditional modify
213    expression using COND.  For conditional expressions, add condition in the
214    destination basic block's predicate list and remove conditional
215    expression itself. BSI is the iterator used to traverse statements of
216    loop. It is used here when it is required to delete current statement.  */
217
218 static tree
219 tree_if_convert_stmt (struct loop *  loop, tree t, tree cond,
220                       block_stmt_iterator *bsi)
221 {
222   if (dump_file && (dump_flags & TDF_DETAILS))
223     {
224       fprintf (dump_file, "------if-convert stmt\n");
225       print_generic_stmt (dump_file, t, TDF_SLIM);
226       print_generic_stmt (dump_file, cond, TDF_SLIM);
227     }
228
229   switch (TREE_CODE (t))
230     {
231       /* Labels are harmless here.  */
232     case LABEL_EXPR:
233       break;
234
235     case GIMPLE_MODIFY_STMT:
236       /* This GIMPLE_MODIFY_STMT is killing previous value of LHS. Appropriate
237          value will be selected by PHI node based on condition. It is possible
238          that before this transformation, PHI nodes was selecting default
239          value and now it will use this new value. This is OK because it does 
240          not change validity the program.  */
241       break;
242
243     case COND_EXPR:
244       /* Update destination blocks' predicate list and remove this
245          condition expression.  */
246       tree_if_convert_cond_expr (loop, t, cond, bsi);
247       cond = NULL_TREE;
248       break;
249
250     default:
251       gcc_unreachable ();
252     }
253   return cond;
254 }
255
256 /* STMT is COND_EXPR. Update two destination's predicate list.
257    Remove COND_EXPR, if it is not the loop exit condition. Otherwise
258    update loop exit condition appropriately.  BSI is the iterator
259    used to traverse statement list. STMT is part of loop LOOP.  */
260
261 static void
262 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
263                            block_stmt_iterator *bsi)
264 {
265   tree c, c2;
266   edge true_edge, false_edge;
267
268   gcc_assert (TREE_CODE (stmt) == COND_EXPR);
269
270   c = COND_EXPR_COND (stmt);
271
272   extract_true_false_edges_from_block (bb_for_stmt (stmt),
273                                        &true_edge, &false_edge);
274
275   /* Add new condition into destination's predicate list.  */
276
277   /* If 'c' is true then TRUE_EDGE is taken.  */
278   add_to_dst_predicate_list (loop, true_edge, cond,
279                              unshare_expr (c), bsi);
280
281   /* If 'c' is false then FALSE_EDGE is taken.  */
282   c2 = invert_truthvalue (unshare_expr (c));
283   add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
284
285   /* Now this conditional statement is redundant. Remove it.
286      But, do not remove exit condition! Update exit condition
287      using new condition.  */
288   if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
289     {
290       bsi_remove (bsi, true);
291       cond = NULL_TREE;
292     }
293   return;
294 }
295
296 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
297    and it belongs to basic block BB.
298    PHI is not if-convertible
299    - if it has more than 2 arguments.
300    - Virtual PHI is immediately used in another PHI node.  */
301
302 static bool
303 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
304 {
305   if (dump_file && (dump_flags & TDF_DETAILS))
306     {
307       fprintf (dump_file, "-------------------------\n");
308       print_generic_stmt (dump_file, phi, TDF_SLIM);
309     }
310
311   if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
312     {
313       if (dump_file && (dump_flags & TDF_DETAILS))
314         fprintf (dump_file, "More than two phi node args.\n");
315       return false;
316     }
317
318   if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
319     {
320       imm_use_iterator imm_iter;
321       use_operand_p use_p;
322       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
323         {
324           if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
325             {
326               if (dump_file && (dump_flags & TDF_DETAILS))
327                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
328               return false;
329             }
330         }
331     }
332
333   return true;
334 }
335
336 /* Return true, if M_EXPR is if-convertible.
337    GIMPLE_MODIFY_STMT is not if-convertible if,
338    - It is not movable.
339    - It could trap.
340    - LHS is not var decl.
341   GIMPLE_MODIFY_STMT is part of block BB, which is inside loop LOOP.
342 */
343
344 static bool
345 if_convertible_gimple_modify_stmt_p (struct loop *loop, basic_block bb,
346                                      tree m_expr)
347 {
348   tree lhs, rhs;
349
350   if (TREE_CODE (m_expr) != GIMPLE_MODIFY_STMT)
351     return false;
352
353   if (dump_file && (dump_flags & TDF_DETAILS))
354     {
355       fprintf (dump_file, "-------------------------\n");
356       print_generic_stmt (dump_file, m_expr, TDF_SLIM);
357     }
358
359   lhs = GIMPLE_STMT_OPERAND (m_expr, 0);
360   rhs = GIMPLE_STMT_OPERAND (m_expr, 1);
361
362   /* Some of these constrains might be too conservative.  */
363   if (stmt_ends_bb_p (m_expr) || stmt_ann (m_expr)->has_volatile_ops
364       || (TREE_CODE (lhs) == SSA_NAME
365           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
366       || TREE_SIDE_EFFECTS (rhs))
367     {
368       if (dump_file && (dump_flags & TDF_DETAILS))
369         fprintf (dump_file, "stmt not suitable for ifcvt\n");
370       return false;
371     }
372
373   /* See if it needs speculative loading or not.  */
374   if (bb != loop->header
375       && tree_could_trap_p (GIMPLE_STMT_OPERAND (m_expr, 1)))
376     {
377       if (dump_file && (dump_flags & TDF_DETAILS))
378         fprintf (dump_file, "tree could trap...\n");
379       return false;
380     }
381
382   if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 1)) == CALL_EXPR)
383     {
384       if (dump_file && (dump_flags & TDF_DETAILS))
385         fprintf (dump_file, "CALL_EXPR \n");
386       return false;
387     }
388
389   if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 0)) != SSA_NAME
390       && bb != loop->header
391       && !bb_with_exit_edge_p (loop, bb))
392     {
393       if (dump_file && (dump_flags & TDF_DETAILS))
394         {
395           fprintf (dump_file, "LHS is not var\n");
396           print_generic_stmt (dump_file, m_expr, TDF_SLIM);
397         }
398       return false;
399     }
400
401
402   return true;
403 }
404
405 /* Return true, iff STMT is if-convertible.
406    Statement is if-convertible if,
407    - It is if-convertible GIMPLE_MODIFY_STMT
408    - IT is LABEL_EXPR or COND_EXPR.
409    STMT is inside block BB, which is inside loop LOOP.  */
410
411 static bool
412 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
413 {
414   switch (TREE_CODE (stmt))
415     {
416     case LABEL_EXPR:
417       break;
418
419     case GIMPLE_MODIFY_STMT:
420
421       if (!if_convertible_gimple_modify_stmt_p (loop, bb, stmt))
422         return false;
423       break;
424
425     case COND_EXPR:
426       break;
427
428     default:
429       /* Don't know what to do with 'em so don't do anything.  */
430       if (dump_file && (dump_flags & TDF_DETAILS))
431         {
432           fprintf (dump_file, "don't know what to do\n");
433           print_generic_stmt (dump_file, stmt, TDF_SLIM);
434         }
435       return false;
436       break;
437     }
438
439   return true;
440 }
441
442 /* Return true, iff BB is if-convertible.
443    Note: This routine does _not_ check basic block statements and phis.
444    Basic block is not if-convertible if,
445    - Basic block is non-empty and it is after exit block (in BFS order).
446    - Basic block is after exit block but before latch.
447    - Basic block edge(s) is not normal.
448    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
449    BB is inside loop LOOP.  */
450
451 static bool
452 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
453 {
454   edge e;
455   edge_iterator ei;
456
457   if (dump_file && (dump_flags & TDF_DETAILS))
458     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
459
460   if (exit_bb)
461     {
462       if (bb != loop->latch)
463         {
464           if (dump_file && (dump_flags & TDF_DETAILS))
465             fprintf (dump_file, "basic block after exit bb but before latch\n");
466           return false;
467         }
468       else if (!empty_block_p (bb))
469         {
470           if (dump_file && (dump_flags & TDF_DETAILS))
471             fprintf (dump_file, "non empty basic block after exit bb\n");
472           return false;
473         }
474       else if (bb == loop->latch 
475                && bb != exit_bb
476                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
477           {
478             if (dump_file && (dump_flags & TDF_DETAILS))
479               fprintf (dump_file, "latch is not dominated by exit_block\n");
480             return false;
481           }
482     }
483
484   /* Be less adventurous and handle only normal edges.  */
485   FOR_EACH_EDGE (e, ei, bb->succs)
486     if (e->flags &
487         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
488       {
489         if (dump_file && (dump_flags & TDF_DETAILS))
490           fprintf (dump_file,"Difficult to handle edges\n");
491         return false;
492       }
493
494   return true;
495 }
496
497 /* Return true, iff LOOP is if-convertible.
498    LOOP is if-convertible if,
499    - It is innermost.
500    - It has two or more basic blocks.
501    - It has only one exit.
502    - Loop header is not the exit edge.
503    - If its basic blocks and phi nodes are if convertible. See above for
504      more info.
505    FOR_VECTORIZER enables vectorizer specific checks. For example, support
506    for vector conditions, data dependency checks etc.. (Not implemented yet).  */
507
508 static bool
509 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
510 {
511   tree phi;
512   basic_block bb;
513   block_stmt_iterator itr;
514   unsigned int i;
515   edge e;
516   edge_iterator ei;
517   basic_block exit_bb = NULL;
518
519   /* Handle only inner most loop.  */
520   if (!loop || loop->inner)
521     {
522       if (dump_file && (dump_flags & TDF_DETAILS))
523         fprintf (dump_file, "not inner most loop\n");
524       return false;
525     }
526
527   /* If only one block, no need for if-conversion.  */
528   if (loop->num_nodes <= 2)
529     {
530       if (dump_file && (dump_flags & TDF_DETAILS))
531         fprintf (dump_file, "less than 2 basic blocks\n");
532       return false;
533     }
534
535   /* More than one loop exit is too much to handle.  */
536   if (!single_exit (loop))
537     {
538       if (dump_file && (dump_flags & TDF_DETAILS))
539         fprintf (dump_file, "multiple exits\n");
540       return false;
541     }
542
543   /* ??? Check target's vector conditional operation support for vectorizer.  */
544
545   /* If one of the loop header's edge is exit edge then do not apply
546      if-conversion.  */
547   FOR_EACH_EDGE (e, ei, loop->header->succs)
548     {
549       if (loop_exit_edge_p (loop, e))
550         return false;
551     }
552
553   calculate_dominance_info (CDI_DOMINATORS);
554   calculate_dominance_info (CDI_POST_DOMINATORS);
555
556   /* Allow statements that can be handled during if-conversion.  */
557   ifc_bbs = get_loop_body_in_if_conv_order (loop);
558   if (!ifc_bbs)
559     {
560       if (dump_file && (dump_flags & TDF_DETAILS))
561         fprintf (dump_file,"Irreducible loop\n");
562       free_dominance_info (CDI_POST_DOMINATORS);
563       return false;
564     }
565
566   for (i = 0; i < loop->num_nodes; i++)
567     {
568       bb = ifc_bbs[i];
569
570       if (!if_convertible_bb_p (loop, bb, exit_bb))
571         return false;
572
573       /* Check statements.  */
574       for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
575         if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
576           return false;
577       /* ??? Check data dependency for vectorizer.  */
578
579       /* What about phi nodes ? */
580       phi = phi_nodes (bb);
581
582       /* Clear aux field of incoming edges to a bb with a phi node.  */
583       if (phi)
584         FOR_EACH_EDGE (e, ei, bb->preds)
585           e->aux = NULL;
586
587       /* Check statements.  */
588       for (; phi; phi = PHI_CHAIN (phi))
589         if (!if_convertible_phi_p (loop, bb, phi))
590           return false;
591
592       if (bb_with_exit_edge_p (loop, bb))
593         exit_bb = bb;
594     }
595
596   /* OK. Did not find any potential issues so go ahead in if-convert
597      this loop. Now there is no looking back.  */
598   if (dump_file)
599     fprintf (dump_file,"Applying if-conversion\n");
600
601   free_dominance_info (CDI_POST_DOMINATORS);
602   return true;
603 }
604
605 /* Add condition COND into predicate list of basic block BB.  */
606
607 static void
608 add_to_predicate_list (basic_block bb, tree new_cond)
609 {
610   tree cond = bb->aux;
611
612   if (cond)
613     cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
614                         unshare_expr (cond), new_cond);
615   else
616     cond = new_cond;
617
618   bb->aux = cond;
619 }
620
621 /* Add condition COND into BB's predicate list.  PREV_COND is
622    existing condition.  */
623
624 static tree
625 add_to_dst_predicate_list (struct loop * loop, edge e,
626                            tree prev_cond, tree cond,
627                            block_stmt_iterator *bsi)
628 {
629   tree new_cond = NULL_TREE;
630
631   if (!flow_bb_inside_loop_p (loop, e->dest))
632     return NULL_TREE;
633
634   if (prev_cond == boolean_true_node || !prev_cond)
635     new_cond = unshare_expr (cond);
636   else
637     {
638       tree tmp;
639       tree tmp_stmt = NULL_TREE;
640       tree tmp_stmts1 = NULL_TREE;
641       tree tmp_stmts2 = NULL_TREE;
642       prev_cond = force_gimple_operand (unshare_expr (prev_cond),
643                                         &tmp_stmts1, true, NULL);
644       if (tmp_stmts1)
645         bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
646
647       cond = force_gimple_operand (unshare_expr (cond),
648                                    &tmp_stmts2, true, NULL);
649       if (tmp_stmts2)
650         bsi_insert_before (bsi, tmp_stmts2, BSI_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       bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
662       new_cond = GIMPLE_STMT_OPERAND (tmp_stmt, 0);
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 succesor 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                                 block_stmt_iterator *bsi)
699 {
700   edge first_edge, second_edge;
701   tree tmp_cond, new_stmts;
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 = (first_edge->src)->aux;
733   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
734     {
735       edge tmp_edge;
736
737       tmp_edge = first_edge;
738       first_edge = second_edge;
739       second_edge = tmp_edge;
740     }
741
742   /* Check if FIRST_BB is loop header or not and make sure that
743      FIRST_BB does not dominate SECOND_BB.  */
744   if (first_edge->src == loop->header
745       || dominated_by_p (CDI_DOMINATORS,
746                          second_edge->src, first_edge->src))
747     {
748       *cond = (second_edge->src)->aux;
749
750       /* If there is a condition on an incoming edge,
751          AND it with the incoming bb predicate.  */
752       if (second_edge->aux)
753         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
754                         *cond, first_edge->aux);
755
756       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
757         /* We can be smart here and choose inverted
758            condition without switching bbs.  */
759           *cond = invert_truthvalue (*cond);
760       else
761         /* Select non loop header bb.  */
762         first_edge = second_edge;
763     }
764   else
765     {
766       /* FIRST_BB is not loop header */
767       *cond = (first_edge->src)->aux;
768
769       /* If there is a condition on an incoming edge,
770          AND it with the incoming bb predicate.  */
771       if (first_edge->aux)
772         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
773                         *cond, first_edge->aux);
774     }
775
776   /* Create temp. for the condition. Vectorizer prefers to have gimple
777      value as condition. Various targets use different means to communicate
778      condition in vector compare operation. Using gimple value allows compiler
779      to emit vector compare and select RTL without exposing compare's result.  */
780   *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE);
781   if (new_stmts)
782     bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
783   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
784     {
785       tree new_stmt;
786
787       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
788       bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
789       *cond = GIMPLE_STMT_OPERAND (new_stmt, 0);
790     }
791
792   gcc_assert (*cond);
793
794   return first_edge->src;
795 }
796
797
798 /* Replace PHI node with conditional modify expr using COND.
799    This routine does not handle PHI nodes with more than two arguments.
800    For example,
801      S1: A = PHI <x1(1), x2(5)
802    is converted into,
803      S2: A = cond ? x1 : x2;
804    S2 is inserted at the top of basic block's statement list.
805    When COND is true, phi arg from TRUE_BB is selected.
806 */
807
808 static void
809 replace_phi_with_cond_gimple_modify_stmt (tree phi, tree cond,
810                                           basic_block true_bb,
811                                           block_stmt_iterator *bsi)
812 {
813   tree new_stmt;
814   basic_block bb;
815   tree rhs;
816   tree arg_0, arg_1;
817
818   gcc_assert (TREE_CODE (phi) == PHI_NODE);
819   
820   /* If this is not filtered earlier, then now it is too late.  */
821   gcc_assert (PHI_NUM_ARGS (phi) == 2);
822
823   /* Find basic block and initialize iterator.  */
824   bb = bb_for_stmt (phi);
825
826   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
827   if (EDGE_PRED (bb, 1)->src == true_bb)
828     {
829       arg_0 = PHI_ARG_DEF (phi, 1);
830       arg_1 = PHI_ARG_DEF (phi, 0);
831     }
832   else
833     {
834       arg_0 = PHI_ARG_DEF (phi, 0);
835       arg_1 = PHI_ARG_DEF (phi, 1);
836     }
837
838   /* Build new RHS using selected condition and arguments.  */
839   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
840                 unshare_expr (cond), unshare_expr (arg_0),
841                 unshare_expr (arg_1));
842
843   /* Create new MODIFY expression using RHS.  */
844   new_stmt = build_gimple_modify_stmt (unshare_expr (PHI_RESULT (phi)), rhs);
845
846   /* Make new statement definition of the original phi result.  */
847   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
848
849   /* Insert using iterator.  */
850   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
851   update_stmt (new_stmt);
852
853   if (dump_file && (dump_flags & TDF_DETAILS))
854     {
855       fprintf (dump_file, "new phi replacement stmt\n");
856       print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
857     }
858 }
859
860 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
861    modify expr.  */
862
863 static void
864 process_phi_nodes (struct loop *loop)
865 {
866   basic_block bb;
867   unsigned int orig_loop_num_nodes = loop->num_nodes;
868   unsigned int i;
869
870   /* Replace phi nodes with cond. modify expr.  */
871   for (i = 1; i < orig_loop_num_nodes; i++)
872     {
873       tree phi, cond;
874       block_stmt_iterator bsi;
875       basic_block true_bb = NULL;
876       bb = ifc_bbs[i];
877
878       if (bb == loop->header)
879         continue;
880
881       phi = phi_nodes (bb);
882       bsi = bsi_after_labels (bb);
883
884       /* BB has two predecessors. Using predecessor's aux field, set
885          appropriate condition for the PHI node replacement.  */
886       if (phi)
887         true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
888
889       while (phi)
890         {
891           tree next = PHI_CHAIN (phi);
892           replace_phi_with_cond_gimple_modify_stmt (phi, cond, true_bb, &bsi);
893           release_phi_node (phi);
894           phi = next;
895         }
896       set_phi_nodes (bb, NULL_TREE);
897     }
898   return;
899 }
900
901 /* Combine all basic block from the given LOOP into one or two super
902    basic block.  Replace PHI nodes with conditional modify expression.  */
903
904 static void
905 combine_blocks (struct loop *loop)
906 {
907   basic_block bb, exit_bb, merge_target_bb;
908   unsigned int orig_loop_num_nodes = loop->num_nodes;
909   unsigned int i;
910   edge e;
911   edge_iterator ei;
912
913   /* Process phi nodes to prepare blocks for merge.  */
914   process_phi_nodes (loop);
915
916   /* Merge basic blocks.  First remove all the edges in the loop, except
917      for those from the exit block.  */
918   exit_bb = NULL;
919   for (i = 0; i < orig_loop_num_nodes; i++)
920     {
921       bb = ifc_bbs[i];
922       if (bb_with_exit_edge_p (loop, bb))
923         {
924           exit_bb = bb;
925           break;
926         }
927     }
928   gcc_assert (exit_bb != loop->latch);
929
930   for (i = 1; i < orig_loop_num_nodes; i++)
931     {
932       bb = ifc_bbs[i];
933
934       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
935         {
936           if (e->src == exit_bb)
937             ei_next (&ei);
938           else
939             remove_edge (e);
940         }
941     }
942
943   if (exit_bb != NULL)
944     {
945       if (exit_bb != loop->header)
946         {
947           /* Connect this node with loop header.  */
948           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
949           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
950         }
951
952       /* Redirect non-exit edges to loop->latch.  */
953       FOR_EACH_EDGE (e, ei, exit_bb->succs)
954         {
955           if (!loop_exit_edge_p (loop, e))
956             redirect_edge_and_branch (e, loop->latch);
957         }
958       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
959     }
960   else
961     {
962       /* If the loop does not have exit then reconnect header and latch.  */
963       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
964       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
965     }
966
967   merge_target_bb = loop->header;
968   for (i = 1; i < orig_loop_num_nodes; i++)
969     {
970       block_stmt_iterator bsi;
971       tree_stmt_iterator last;
972
973       bb = ifc_bbs[i];
974
975       if (bb == exit_bb || bb == loop->latch)
976         continue;
977
978       /* Remove labels and make stmts member of loop->header.  */
979       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
980         {
981           if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
982             bsi_remove (&bsi, true);
983           else
984             {
985               set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
986               bsi_next (&bsi);
987             }
988         }
989
990       /* Update stmt list.  */
991       last = tsi_last (bb_stmt_list (merge_target_bb));
992       tsi_link_after (&last, bb_stmt_list (bb), TSI_NEW_STMT);
993       set_bb_stmt_list (bb, NULL);
994
995       delete_basic_block (bb);
996     }
997
998   /* Now if possible, merge loop header and block with exit edge.
999      This reduces number of basic blocks to 2. Auto vectorizer addresses
1000      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1001   if (exit_bb
1002       && exit_bb != loop->header
1003       && can_merge_blocks_p (loop->header, exit_bb))
1004     merge_blocks (loop->header, exit_bb);
1005 }
1006
1007 /* Make new  temp variable of type TYPE. Add GIMPLE_MODIFY_STMT to assign EXP
1008    to the new variable.  */
1009
1010 static tree
1011 ifc_temp_var (tree type, tree exp)
1012 {
1013   const char *name = "_ifc_";
1014   tree var, stmt, new_name;
1015
1016   if (is_gimple_reg (exp))
1017     return exp;
1018
1019   /* Create new temporary variable.  */
1020   var = create_tmp_var (type, name);
1021   add_referenced_var (var);
1022
1023   /* Build new statement to assign EXP to new variable.  */
1024   stmt = build_gimple_modify_stmt (var, exp);
1025
1026   /* Get SSA name for the new variable and set make new statement
1027      its definition statement.  */
1028   new_name = make_ssa_name (var, stmt);
1029   GIMPLE_STMT_OPERAND (stmt, 0) = new_name;
1030   SSA_NAME_DEF_STMT (new_name) = stmt;
1031
1032   return stmt;
1033 }
1034
1035
1036 /* Return TRUE iff, all pred blocks of BB are visited.
1037    Bitmap VISITED keeps history of visited blocks.  */
1038
1039 static bool
1040 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1041 {
1042   edge e;
1043   edge_iterator ei;
1044   FOR_EACH_EDGE (e, ei, bb->preds)
1045     if (!bitmap_bit_p (*visited, e->src->index))
1046       return false;
1047
1048   return true;
1049 }
1050
1051 /* Get body of a LOOP in suitable order for if-conversion.
1052    It is caller's responsibility to deallocate basic block
1053    list.  If-conversion suitable order is, BFS order with one
1054    additional constraint. Select block in BFS block, if all
1055    pred are already selected.  */
1056
1057 static basic_block *
1058 get_loop_body_in_if_conv_order (const struct loop *loop)
1059 {
1060   basic_block *blocks, *blocks_in_bfs_order;
1061   basic_block bb;
1062   bitmap visited;
1063   unsigned int index = 0;
1064   unsigned int visited_count = 0;
1065
1066   gcc_assert (loop->num_nodes);
1067   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1068
1069   blocks = XCNEWVEC (basic_block, loop->num_nodes);
1070   visited = BITMAP_ALLOC (NULL);
1071
1072   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1073
1074   index = 0;
1075   while (index < loop->num_nodes)
1076     {
1077       bb = blocks_in_bfs_order [index];
1078
1079       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1080         {
1081           free (blocks_in_bfs_order);
1082           BITMAP_FREE (visited);
1083           free (blocks);
1084           return NULL;
1085         }
1086       if (!bitmap_bit_p (visited, bb->index))
1087         {
1088           if (pred_blocks_visited_p (bb, &visited)
1089               || bb == loop->header)
1090             {
1091               /* This block is now visited.  */
1092               bitmap_set_bit (visited, bb->index);
1093               blocks[visited_count++] = bb;
1094             }
1095         }
1096       index++;
1097       if (index == loop->num_nodes
1098           && visited_count != loop->num_nodes)
1099         {
1100           /* Not done yet.  */
1101           index = 0;
1102         }
1103     }
1104   free (blocks_in_bfs_order);
1105   BITMAP_FREE (visited);
1106   return blocks;
1107 }
1108
1109 /* Return true if one of the basic block BB edge is exit of LOOP.  */
1110
1111 static bool
1112 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1113 {
1114   edge e;
1115   edge_iterator ei;
1116   bool exit_edge_found = false;
1117
1118   FOR_EACH_EDGE (e, ei, bb->succs)
1119     if (loop_exit_edge_p (loop, e))
1120       {
1121         exit_edge_found = true;
1122         break;
1123       }
1124
1125   return exit_edge_found;
1126 }
1127
1128 /* Tree if-conversion pass management.  */
1129
1130 static unsigned int
1131 main_tree_if_conversion (void)
1132 {
1133   loop_iterator li;
1134   struct loop *loop;
1135
1136   if (number_of_loops () <= 1)
1137     return 0;
1138
1139   FOR_EACH_LOOP (li, loop, 0)
1140     {
1141       tree_if_conversion (loop, true);
1142     }
1143   return 0;
1144 }
1145
1146 static bool
1147 gate_tree_if_conversion (void)
1148 {
1149   return flag_tree_vectorize != 0;
1150 }
1151
1152 struct tree_opt_pass pass_if_conversion =
1153 {
1154   "ifcvt",                              /* name */
1155   gate_tree_if_conversion,              /* gate */
1156   main_tree_if_conversion,              /* execute */
1157   NULL,                                 /* sub */
1158   NULL,                                 /* next */
1159   0,                                    /* static_pass_number */
1160   0,                                    /* tv_id */
1161   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1162   0,                                    /* properties_provided */
1163   0,                                    /* properties_destroyed */
1164   0,                                    /* todo_flags_start */
1165   TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,    
1166                                         /* todo_flags_finish */
1167   0                                     /* letter */
1168 };