OSDN Git Service

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