OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-if-conv.c
1 /* If-conversion for vectorizer.
2    Copyright (C) 2004 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-convertable 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_convertable_phi_p (struct loop *, basic_block, tree);
112 static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree);
113 static bool if_convertable_stmt_p (struct loop *, basic_block, tree);
114 static bool if_convertable_bb_p (struct loop *, basic_block, bool);
115 static bool if_convertable_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, tree, 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 (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 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-convertable or not.  */
153   if (!if_convertable_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 (bb->succ && !bb->succ->succ_next)
191         {
192           basic_block bb_n = bb->succ->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 then_clause, else_clause, c, new_cond;
275   new_cond = NULL_TREE;
276
277   gcc_assert (TREE_CODE (stmt) == COND_EXPR);
278
279   c = TREE_OPERAND (stmt, 0);
280   then_clause = TREE_OPERAND (stmt, 1);
281   else_clause = TREE_OPERAND (stmt, 2);
282
283   /* Create temp. for condition.  */
284   if (!is_gimple_reg (c))
285     {
286       tree new_stmt;
287       new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c));
288       bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
289       c = TREE_OPERAND (new_stmt, 0);
290     }
291
292   /* Add new condition into destination's predicate list.  */
293   if (then_clause)
294     /* if 'c' is true then then_clause is reached.  */
295     new_cond = add_to_dst_predicate_list (loop, then_clause, cond, c, bsi);
296
297   if (else_clause)
298     {
299       /* if 'c' is false then else_clause is reached.  */
300       tree c2 = build1 (TRUTH_NOT_EXPR,
301                         boolean_type_node,
302                         unshare_expr (c));
303       add_to_dst_predicate_list (loop, else_clause, cond, c2, bsi);
304     }
305
306   /* Now this conditional statement is redundant. Remove it.
307      But, do not remove exit condition! Update exit condition
308      using new condition.  */
309   if (!bb_with_exit_edge_p (bb_for_stmt (stmt)))
310     {
311       bsi_remove (bsi);
312       cond = NULL_TREE;
313     }
314   else if (new_cond != NULL_TREE)
315     {
316       TREE_OPERAND (stmt, 0) = new_cond;
317       modify_stmt (stmt);
318     }
319   return;
320 }
321
322 /* Return true, iff PHI is if-convertable. PHI is part of loop LOOP
323    and it belongs to basic block BB.
324    PHI is not if-convertable
325    - if it has more than 2 arguments.
326    - Virtual PHI is immediately used in another PHI node.  */
327
328 static bool
329 if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi)
330 {
331   if (dump_file && (dump_flags & TDF_DETAILS))
332     {
333       fprintf (dump_file, "-------------------------\n");
334       print_generic_stmt (dump_file, phi, TDF_SLIM);
335     }
336
337   if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
338     {
339       if (dump_file && (dump_flags & TDF_DETAILS))
340         fprintf (dump_file, "More than two phi node args.\n");
341       return false;
342     }
343
344   if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
345     {
346       int j;
347       dataflow_t df = get_immediate_uses (phi);
348       int num_uses = num_immediate_uses (df);
349       for (j = 0; j < num_uses; j++)
350         {
351           tree use = immediate_use (df, j);
352           if (TREE_CODE (use) == PHI_NODE)
353             {
354               if (dump_file && (dump_flags & TDF_DETAILS))
355                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
356               return false;
357             }
358         }
359     }
360
361   return true;
362 }
363
364 /* Return true, if M_EXPR is if-convertable.
365    MODIFY_EXPR is not if-convertable if,
366    - It is not movable.
367    - It could trap.
368    - LHS is not var decl.
369   MODIFY_EXPR is part of block BB, which is inside loop LOOP.
370 */
371
372 static bool
373 if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
374 {
375   if (dump_file && (dump_flags & TDF_DETAILS))
376     {
377       fprintf (dump_file, "-------------------------\n");
378       print_generic_stmt (dump_file, m_expr, TDF_SLIM);
379     }
380
381   /* Be conservative and do not handle immovable expressions.  */
382   if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
383     {
384       if (dump_file && (dump_flags & TDF_DETAILS))
385         fprintf (dump_file, "stmt is movable. Don't take risk\n");
386       return false;
387     }
388
389   /* See if it needs speculative loading or not.  */
390   if (bb != loop->header
391       && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
392     {
393       if (dump_file && (dump_flags & TDF_DETAILS))
394         fprintf (dump_file, "tree could trap...\n");
395       return false;
396     }
397
398   if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
399     {
400       if (dump_file && (dump_flags & TDF_DETAILS))
401         fprintf (dump_file, "CALL_EXPR \n");
402       return false;
403     }
404
405   if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
406       && bb != loop->header
407       && !bb_with_exit_edge_p (bb))
408     {
409       if (dump_file && (dump_flags & TDF_DETAILS))
410         {
411           fprintf (dump_file, "LHS is not var\n");
412           print_generic_stmt (dump_file, m_expr, TDF_SLIM);
413         }
414       return false;
415     }
416
417
418   return true;
419 }
420
421 /* Return true, iff STMT is if-convertable.
422    Statement is if-convertable if,
423    - It is if-convertable MODIFY_EXPR
424    - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
425    STMT is inside block BB, which is inside loop LOOP.  */
426
427 static bool
428 if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt)
429 {
430   switch (TREE_CODE (stmt))
431     {
432     case LABEL_EXPR:
433       break;
434
435     case MODIFY_EXPR:
436
437       if (!if_convertable_modify_expr_p (loop, bb, stmt))
438         return false;
439       break;
440
441     case GOTO_EXPR:
442     case COND_EXPR:
443       break;
444
445     default:
446       /* Don't know what to do with 'em so don't do anything.  */
447       if (dump_file && (dump_flags & TDF_DETAILS))
448         {
449           fprintf (dump_file, "don't know what to do\n");
450           print_generic_stmt (dump_file, stmt, TDF_SLIM);
451         }
452       return false;
453       break;
454     }
455
456   return true;
457 }
458
459 /* Return true, iff BB is if-convertable.
460    Note: This routine does _not_ check basic block statements and phis.
461    Basic block is not if-convertable if,
462    - Basic block is non-empty and it is after exit block (in BFS order).
463    - Basic block is after exit block but before latch.
464    - Basic block edge(s) is not normal.
465    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
466    BB is inside loop LOOP.  */
467
468 static bool
469 if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
470 {
471   edge e;
472
473   if (dump_file && (dump_flags & TDF_DETAILS))
474     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
475
476   if (exit_bb_seen)
477     {
478       if (bb != loop->latch)
479         {
480           if (dump_file && (dump_flags & TDF_DETAILS))
481             fprintf (dump_file, "basic block after exit bb but before latch\n");
482           return false;
483         }
484       else if (!empty_block_p (bb))
485         {
486           if (dump_file && (dump_flags & TDF_DETAILS))
487             fprintf (dump_file, "non empty basic block after exit bb\n");
488           return false;
489         }
490     }
491
492   /* Be less adventurous and handle only normal edges.  */
493   for (e = bb->succ; e; e = e->succ_next)
494     if (e->flags &
495         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
496       {
497         if (dump_file && (dump_flags & TDF_DETAILS))
498           fprintf (dump_file,"Difficult to handle edges\n");
499         return false;
500       }
501
502   return true;
503 }
504
505 /* Return true, iff LOOP is if-convertable.
506    LOOP is if-convertable if,
507    - It is innermost.
508    - It has two or more basic blocks.
509    - It has only one exit.
510    - Loop header is not the exit edge.
511    - If its basic blocks and phi nodes are if convertable. See above for
512      more info.
513    FOR_VECTORIZER enables vectorizer specific checks. For example, support
514    for vector conditions, data dependency checks etc.. (Not implemented yet).  */
515
516 static bool
517 if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
518 {
519   tree phi;
520   basic_block bb;
521   block_stmt_iterator itr;
522   unsigned int i;
523   edge e;
524   bool exit_bb_seen = false;
525
526   /* Handle only inner most loop.  */
527   if (!loop || loop->inner)
528     {
529       if (dump_file && (dump_flags & TDF_DETAILS))
530         fprintf (dump_file, "not inner most loop\n");
531       return false;
532     }
533
534   flow_loop_scan (loop, LOOP_ALL);
535
536   /* If only one block, no need for if-conversion.  */
537   if (loop->num_nodes <= 2)
538     {
539       if (dump_file && (dump_flags & TDF_DETAILS))
540         fprintf (dump_file, "less than 2 basic blocks\n");
541       return false;
542     }
543
544   /* More than one loop exit is too much to handle.  */
545   if (loop->num_exits > 1)
546     {
547       if (dump_file && (dump_flags & TDF_DETAILS))
548         fprintf (dump_file, "multiple exits\n");
549       return false;
550     }
551
552   /* ??? Check target's vector conditional operation support for vectorizer.  */
553
554   /* If one of the loop header's edge is exit edge then do not apply
555      if-conversion.  */
556   for (e = loop->header->succ; e; e = e->succ_next)
557     if ( e->flags & EDGE_LOOP_EXIT)
558       return false;
559
560   compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
561
562   calculate_dominance_info (CDI_DOMINATORS);
563   calculate_dominance_info (CDI_POST_DOMINATORS);
564
565   /* Allow statements that can be handled during if-conversion.  */
566   ifc_bbs = get_loop_body_in_if_conv_order (loop);
567   if (!ifc_bbs)
568     {
569       if (dump_file && (dump_flags & TDF_DETAILS))
570         fprintf (dump_file,"Irreducible loop\n");
571       free_dominance_info (CDI_POST_DOMINATORS);
572       return false;
573     }
574
575   for (i = 0; i < loop->num_nodes; i++)
576     {
577       bb = ifc_bbs[i];
578
579       if (!if_convertable_bb_p (loop, bb, exit_bb_seen))
580         return false;
581
582       /* Check statements.  */
583       for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
584         if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr)))
585           return false;
586       /* ??? Check data dependency for vectorizer.  */
587
588       /* What about phi nodes ? */
589       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
590         if (!if_convertable_phi_p (loop, bb, phi))
591           return false;
592
593       if (bb_with_exit_edge_p (bb))
594         exit_bb_seen = true;
595     }
596
597   /* OK. Did not find any potential issues so go ahead in if-convert
598      this loop. Now there is no looking back.  */
599   if (dump_file)
600     fprintf (dump_file,"Applying if-conversion\n");
601
602   free_dominance_info (CDI_POST_DOMINATORS);
603   return true;
604 }
605
606 /* Add condition COND into predicate list of basic block BB.  */
607
608 static void
609 add_to_predicate_list (basic_block bb, tree new_cond)
610 {
611   tree cond = bb->aux;
612
613   if (cond)
614     cond = fold (build (TRUTH_OR_EXPR, boolean_type_node,
615                         unshare_expr (cond), new_cond));
616   else
617     cond = new_cond;
618
619   bb->aux = cond;
620 }
621
622 /* Add condition COND into DST's predicate list.  PREV_COND is
623    existing condition.  */
624
625 static tree
626 add_to_dst_predicate_list (struct loop * loop, tree dst,
627                            tree prev_cond, tree cond,
628                            block_stmt_iterator *bsi)
629 {
630   basic_block bb;
631   tree new_cond = NULL_TREE;
632
633   gcc_assert (TREE_CODE (dst) == GOTO_EXPR);
634   bb = label_to_block (TREE_OPERAND (dst, 0));
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_stmt;
643       /* new_cond == prev_cond AND cond */
644       tree tmp = build (TRUTH_AND_EXPR, boolean_type_node,
645                         unshare_expr (prev_cond), cond);
646       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
647       bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
648       new_cond = TREE_OPERAND (tmp_stmt, 0);
649     }
650   add_to_predicate_list (bb, new_cond);
651   return new_cond;
652 }
653
654 /* During if-conversion aux field from basic block is used to hold predicate
655    list. Clean each basic block's predicate list for the given LOOP.  */
656
657 static void
658 clean_predicate_lists (struct loop *loop)
659 {
660   unsigned int i;
661
662   for (i = 0; i < loop->num_nodes; i++)
663     ifc_bbs[i]->aux = NULL;
664 }
665
666 /* Basic block BB has two predecessors. Using predecessor's aux field, set
667    appropriate condition COND for the PHI node replacement. Return true block
668    whose phi arguments are selected when cond is true.  */
669
670 static basic_block
671 find_phi_replacement_condition (basic_block bb, tree *cond,
672                                 block_stmt_iterator *bsi)
673 {
674   edge e;
675   basic_block p1 = NULL;
676   basic_block p2 = NULL;
677   basic_block true_bb = NULL; 
678   tree tmp_cond;
679
680   for (e = bb->pred; e; e = e->pred_next)
681     {
682       if (p1 == NULL)
683           p1 = e->src;
684       else 
685         {
686           gcc_assert (!p2);
687           p2 = e->src;
688         }
689     }
690
691   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
692   tmp_cond = p1->aux;
693   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
694     {
695       *cond  = p2->aux;
696       true_bb = p2;
697     }
698   else
699     {
700       *cond  = p1->aux;
701       true_bb = p1;
702     }
703
704   /* Create temp. for the condition. Vectorizer prefers to have gimple
705      value as condition. Various targets use different means to communicate
706      condition in vector compare operation. Using gimple value allows compiler
707      to emit vector compare and select RTL without exposing compare's result.  */
708   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
709     {
710       tree new_stmt;
711
712       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
713       bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
714       bsi_next (bsi);
715       *cond = TREE_OPERAND (new_stmt, 0);
716     }
717
718   gcc_assert (*cond);
719
720   return true_bb;
721 }
722
723
724 /* Replace PHI node with conditional modify expr using COND.
725    This routine does not handle PHI nodes with more than two arguments.
726    For example,
727      S1: A = PHI <x1(1), x2(5)
728    is converted into,
729      S2: A = cond ? x1 : x2;
730    S2 is inserted at the top of basic block's statement list.
731    When COND is true, phi arg from TRUE_BB is selected.
732 */
733
734 static void
735 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
736                                    block_stmt_iterator *bsi)
737 {
738   tree new_stmt;
739   basic_block bb;
740   tree rhs;
741   tree arg_0, arg_1;
742
743   gcc_assert (TREE_CODE (phi) == PHI_NODE);
744   
745   /* If this is not filtered earlier, then now it is too late.  */
746   gcc_assert (PHI_NUM_ARGS (phi) == 2);
747
748   /* Find basic block and initialize iterator.  */
749   bb = bb_for_stmt (phi);
750
751   new_stmt = NULL_TREE;
752   arg_0 = NULL_TREE;
753   arg_1 = NULL_TREE;
754
755   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
756   if (PHI_ARG_EDGE(phi, 1)->src == true_bb)
757     {
758       arg_0 = PHI_ARG_DEF (phi, 1);
759       arg_1 = PHI_ARG_DEF (phi, 0);
760     }
761   else
762     {
763       arg_0 = PHI_ARG_DEF (phi, 0);
764       arg_1 = PHI_ARG_DEF (phi, 1);
765     }
766
767   /* Build new RHS using selected condition and arguments.  */
768   rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
769                unshare_expr (cond), unshare_expr (arg_0),
770                unshare_expr (arg_1));
771
772   /* Create new MODIFY expression using RHS.  */
773   new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
774                     unshare_expr (PHI_RESULT (phi)), rhs);
775
776   /* Make new statement definition of the original phi result.  */
777   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
778
779   /* Set basic block and insert using iterator.  */
780   set_bb_for_stmt (new_stmt, bb);
781
782   bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
783   bsi_next (bsi);
784
785   modify_stmt (new_stmt);
786
787   if (dump_file && (dump_flags & TDF_DETAILS))
788     {
789       fprintf (dump_file, "new phi replacement stmt\n");
790       print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
791     }
792 }
793
794 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
795    modify expr.  */
796
797 static void
798 process_phi_nodes (struct loop *loop)
799 {
800   basic_block bb;
801   unsigned int orig_loop_num_nodes = loop->num_nodes;
802   unsigned int i;
803
804   /* Replace phi nodes with cond. modify expr.  */
805   for (i = 1; i < orig_loop_num_nodes; i++)
806     {
807       tree phi, cond;
808       block_stmt_iterator bsi;
809       basic_block true_bb = NULL;
810       bb = ifc_bbs[i];
811
812       if (bb == loop->header || bb == loop->latch)
813         continue;
814
815       phi = phi_nodes (bb);
816       bsi = bsi_start (bb);
817
818       /* BB has two predecessors. Using predecessor's aux field, set
819          appropriate condition for the PHI node replacement.  */
820       if (phi)
821         true_bb = find_phi_replacement_condition (bb, &cond, &bsi);
822
823       while (phi)
824         {
825           tree next = TREE_CHAIN (phi);
826           replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
827           release_phi_node (phi);
828           phi = next;
829         }
830       bb_ann (bb)->phi_nodes = NULL;
831     }
832   return;
833 }
834
835 /* Combine all basic block from the given LOOP into one or two super
836    basic block.  Replace PHI nodes with conditional modify expression.  */
837
838 static void
839 combine_blocks (struct loop *loop)
840 {
841   basic_block bb, exit_bb, merge_target_bb;
842   unsigned int orig_loop_num_nodes = loop->num_nodes;
843   unsigned int i;
844
845   /* Process phi nodes to prepare blocks for merge.  */
846   process_phi_nodes (loop);
847
848   exit_bb = NULL;
849
850   /* Merge basic blocks */
851   merge_target_bb = loop->header;
852   for (i = 1; i < orig_loop_num_nodes; i++)
853     {
854       edge e;
855       block_stmt_iterator bsi;
856       tree_stmt_iterator last;
857
858       bb = ifc_bbs[i];
859
860       if (bb == loop->latch)
861         continue;
862
863       if (!exit_bb && bb_with_exit_edge_p (bb))
864           exit_bb = bb;
865
866       if (bb == exit_bb)
867         {
868           edge new_e;
869
870           /* Connect this node with loop header.  */
871           new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
872           set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
873
874           if (exit_bb != loop->latch)
875             {
876               /* Redirect non-exit edge to loop->latch.  */
877               for (e = bb->succ; e; e = e->succ_next)
878                 if (!(e->flags & EDGE_LOOP_EXIT))
879                   {
880                     redirect_edge_and_branch (e, loop->latch);
881                     set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
882                   }
883             }
884           continue;
885         }
886
887       /* It is time to remove this basic block.  First remove edges.  */
888       while (bb->succ != NULL)
889         ssa_remove_edge (bb->succ);
890       while (bb->pred != NULL)
891         ssa_remove_edge (bb->pred);
892
893       /* Remove labels and make stmts member of loop->header.  */
894       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
895         {
896           if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
897             bsi_remove (&bsi);
898           else
899             {
900               set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
901               bsi_next (&bsi);
902             }
903         }
904
905       /* Update stmt list.  */
906       last = tsi_last (merge_target_bb->stmt_list);
907       tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
908       bb->stmt_list = NULL;
909
910       /* Update dominator info.  */
911       if (dom_computed[CDI_DOMINATORS])
912         delete_from_dominance_info (CDI_DOMINATORS, bb);
913       if (dom_computed[CDI_POST_DOMINATORS])
914         delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
915
916       /* Remove basic block.  */
917       remove_bb_from_loops (bb);
918       expunge_block (bb);
919     }
920 }
921
922 /* Make new  temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
923    to the new variable.  */
924
925 static tree
926 ifc_temp_var (tree type, tree exp)
927 {
928   const char *name = "_ifc_";
929   tree var, stmt, new_name;
930
931   if (is_gimple_reg (exp))
932     return exp;
933
934   /* Create new temporary variable.  */
935   var = create_tmp_var (type, name);
936   add_referenced_tmp_var (var);
937
938   /* Build new statement to assign EXP to new variable.  */
939   stmt = build (MODIFY_EXPR, type, var, exp);
940
941   /* Get SSA name for the new variable and set make new statement
942      its definition statment.  */
943   new_name = make_ssa_name (var, stmt);
944   TREE_OPERAND (stmt, 0) = new_name;
945   SSA_NAME_DEF_STMT (new_name) = stmt;
946
947   return stmt;
948 }
949
950
951 /* Return TRUE iff, all pred blocks of BB are visited.
952    Bitmap VISITED keeps history of visited blocks.  */
953
954 static bool
955 pred_blocks_visited_p (basic_block bb, bitmap *visited)
956 {
957   edge e;
958   for (e = bb->pred; e; e = e->pred_next)
959     if (!bitmap_bit_p (*visited, e->src->index))
960       return false;
961
962   return true;
963 }
964
965 /* Get body of a LOOP in suitable order for if-conversion.
966    It is caller's responsibility to deallocate basic block
967    list.  If-conversion suitable order is, BFS order with one
968    additional constraint. Select block in BFS block, if all
969    pred are already selected.  */
970
971 static basic_block *
972 get_loop_body_in_if_conv_order (const struct loop *loop)
973 {
974   basic_block *blocks, *blocks_in_bfs_order;
975   basic_block bb;
976   bitmap visited;
977   unsigned int index = 0;
978   unsigned int visited_count = 0;
979
980   gcc_assert (loop->num_nodes);
981   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
982
983   blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
984   visited = BITMAP_XMALLOC ();
985
986   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
987
988   index = 0;
989   while (index < loop->num_nodes)
990     {
991       bb = blocks_in_bfs_order [index];
992
993       if (bb->flags & BB_IRREDUCIBLE_LOOP)
994         {
995           free (blocks_in_bfs_order);
996           BITMAP_FREE (visited);
997           free (blocks);
998           return NULL;
999         }
1000       if (!bitmap_bit_p (visited, bb->index))
1001         {
1002           if (pred_blocks_visited_p (bb, &visited)
1003               || bb == loop->header)
1004             {
1005               /* This block is now visited.  */
1006               bitmap_set_bit (visited, bb->index);
1007               blocks[visited_count++] = bb;
1008             }
1009         }
1010       index++;
1011       if (index == loop->num_nodes
1012           && visited_count != loop->num_nodes)
1013         {
1014           /* Not done yet.  */
1015           index = 0;
1016         }
1017     }
1018   free (blocks_in_bfs_order);
1019   BITMAP_XFREE (visited);
1020   return blocks;
1021 }
1022
1023 /* Return true if one of the basic block BB edge is loop exit.  */
1024
1025 static bool
1026 bb_with_exit_edge_p (basic_block bb)
1027 {
1028   edge e;
1029   bool exit_edge_found = false;
1030
1031   for (e = bb->succ; e && !exit_edge_found ; e = e->succ_next)
1032     if (e->flags & EDGE_LOOP_EXIT)
1033       exit_edge_found = true;
1034
1035   return exit_edge_found;
1036 }
1037
1038 /* Tree if-conversion pass management.  */
1039
1040 static void
1041 main_tree_if_conversion (void)
1042 {
1043   unsigned i, loop_num;
1044   struct loop *loop;
1045
1046   if (!current_loops)
1047     return;
1048
1049   loop_num = current_loops->num;
1050   for (i = 0; i < loop_num; i++)
1051     {
1052       loop =  current_loops->parray[i];
1053       if (!loop)
1054       continue;
1055
1056       tree_if_conversion (loop, true);
1057     }
1058
1059 }
1060
1061 static bool
1062 gate_tree_if_conversion (void)
1063 {
1064   return flag_tree_vectorize != 0;
1065 }
1066
1067 struct tree_opt_pass pass_if_conversion =
1068 {
1069   "ifcvt",                           /* name */
1070   gate_tree_if_conversion,           /* gate */
1071   main_tree_if_conversion,           /* execute */
1072   NULL,                              /* sub */
1073   NULL,                              /* next */
1074   0,                                 /* static_pass_number */
1075   0,                                 /* tv_id */
1076   PROP_cfg | PROP_ssa | PROP_alias,  /* properties_required */
1077   0,                                 /* properties_provided */
1078   0,                                 /* properties_destroyed */
1079   TODO_dump_func,                    /* todo_flags_start */
1080   TODO_dump_func
1081     | TODO_verify_ssa
1082     | TODO_verify_stmts
1083     | TODO_verify_flow,              /* todo_flags_finish */
1084   0                                  /* letter */
1085 };