OSDN Git Service

f05e36995ae362ad05373429ef2c394b2b98d7d3
[pf3gnuchains/gcc-fork.git] / gcc / tree-if-conv.c
1 /* If-conversion for vectorizer.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3    Free Software Foundation, Inc.
4    Contributed by Devang Patel <dpatel@apple.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /* This pass implements a tree level if-conversion of loops.  Its
23    initial goal is to help the vectorizer to vectorize loops with
24    conditions.
25
26    A short description of if-conversion:
27
28      o Decide if a loop is if-convertible or not.
29      o Walk all loop basic blocks in breadth first order (BFS order).
30        o Remove conditional statements (at the end of basic block)
31          and propagate condition into destination basic blocks'
32          predicate list.
33        o Replace modify expression with conditional modify expression
34          using current basic block's condition.
35      o Merge all basic blocks
36        o Replace phi nodes with conditional modify expr
37        o Merge all basic blocks into header
38
39      Sample transformation:
40
41      INPUT
42      -----
43
44      # i_23 = PHI <0(0), i_18(10)>;
45      <L0>:;
46      j_15 = A[i_23];
47      if (j_15 > 41) goto <L1>; else goto <L17>;
48
49      <L17>:;
50      goto <bb 3> (<L3>);
51
52      <L1>:;
53
54      # iftmp.2_4 = PHI <0(8), 42(2)>;
55      <L3>:;
56      A[i_23] = iftmp.2_4;
57      i_18 = i_23 + 1;
58      if (i_18 <= 15) goto <L19>; else goto <L18>;
59
60      <L19>:;
61      goto <bb 1> (<L0>);
62
63      <L18>:;
64
65      OUTPUT
66      ------
67
68      # i_23 = PHI <0(0), i_18(10)>;
69      <L0>:;
70      j_15 = A[i_23];
71
72      <L3>:;
73      iftmp.2_4 = j_15 > 41 ? 42 : 0;
74      A[i_23] = iftmp.2_4;
75      i_18 = i_23 + 1;
76      if (i_18 <= 15) goto <L19>; else goto <L18>;
77
78      <L19>:;
79      goto <bb 1> (<L0>);
80
81      <L18>:;
82 */
83
84 #include "config.h"
85 #include "system.h"
86 #include "coretypes.h"
87 #include "tm.h"
88 #include "tree.h"
89 #include "flags.h"
90 #include "timevar.h"
91 #include "rtl.h"
92 #include "basic-block.h"
93 #include "diagnostic.h"
94 #include "tree-flow.h"
95 #include "tree-dump.h"
96 #include "cfgloop.h"
97 #include "tree-chrec.h"
98 #include "tree-data-ref.h"
99 #include "tree-scalar-evolution.h"
100 #include "tree-pass.h"
101 #include "target.h"
102
103 /* List of basic blocks in if-conversion-suitable order.  */
104 static basic_block *ifc_bbs;
105
106 /* Make a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
107    to the new variable.  */
108
109 static gimple
110 ifc_temp_var (tree type, tree exp)
111 {
112   const char *name = "_ifc_";
113   tree var, new_name;
114   gimple stmt;
115
116   /* Create new temporary variable.  */
117   var = create_tmp_var (type, name);
118   add_referenced_var (var);
119
120   /* Build new statement to assign EXP to new variable.  */
121   stmt = gimple_build_assign (var, exp);
122
123   /* Get SSA name for the new variable and set make new statement
124      its definition statement.  */
125   new_name = make_ssa_name (var, stmt);
126   gimple_assign_set_lhs (stmt, new_name);
127   SSA_NAME_DEF_STMT (new_name) = stmt;
128   update_stmt (stmt);
129
130   return stmt;
131 }
132
133 /* Add condition NEW_COND into predicate list of basic block BB.  */
134
135 static void
136 add_to_predicate_list (basic_block bb, tree new_cond)
137 {
138   tree cond = (tree) bb->aux;
139
140   if (cond)
141     cond = fold_build2_loc (EXPR_LOCATION (cond),
142                             TRUTH_OR_EXPR, boolean_type_node,
143                             unshare_expr (cond), new_cond);
144   else
145     cond = new_cond;
146
147   bb->aux = cond;
148 }
149
150 /* And condition COND to the previous condition PREV_COND and add this
151    to the predicate list of the destination of edge E.  GSI is the
152    place where the gimplification of the resulting condition should
153    output code.  LOOP is the loop to be if-converted.  */
154
155 static tree
156 add_to_dst_predicate_list (struct loop *loop, edge e,
157                            tree prev_cond, tree cond,
158                            gimple_stmt_iterator *gsi)
159 {
160   tree new_cond = NULL_TREE;
161
162   if (!flow_bb_inside_loop_p (loop, e->dest))
163     return NULL_TREE;
164
165   if (prev_cond == boolean_true_node || !prev_cond)
166     new_cond = unshare_expr (cond);
167   else
168     {
169       tree tmp;
170       gimple tmp_stmt = NULL;
171
172       prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
173                                             true, NULL, true, GSI_SAME_STMT);
174
175       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
176                                        true, NULL, true, GSI_SAME_STMT);
177
178       /* Add the condition to aux field of the edge.  In case edge
179          destination is a PHI node, this condition will be ANDed with
180          block predicate to construct complete condition.  */
181       e->aux = cond;
182
183       tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
184                     unshare_expr (prev_cond), cond);
185       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
186       gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
187       new_cond = gimple_assign_lhs (tmp_stmt);
188     }
189
190   add_to_predicate_list (e->dest, new_cond);
191   return new_cond;
192 }
193
194 /* Return true if one of the basic block BB edge is exit of LOOP.  */
195
196 static bool
197 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
198 {
199   edge e;
200   edge_iterator ei;
201   bool exit_edge_found = false;
202
203   FOR_EACH_EDGE (e, ei, bb->succs)
204     if (loop_exit_edge_p (loop, e))
205       {
206         exit_edge_found = true;
207         break;
208       }
209
210   return exit_edge_found;
211 }
212
213 /* STMT is a GIMPLE_COND.  Update two destination's predicate list.
214    Remove COND_EXPR, if it is not the loop exit condition.  Otherwise
215    update loop exit condition appropriately.  GSI is the iterator
216    used to traverse statement list.  STMT is part of loop LOOP.  */
217
218 static void
219 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
220                            gimple_stmt_iterator *gsi)
221 {
222   tree c2;
223   edge true_edge, false_edge;
224   location_t loc = gimple_location (stmt);
225   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
226                             gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
227
228   extract_true_false_edges_from_block (gimple_bb (stmt),
229                                        &true_edge, &false_edge);
230
231   /* Add new condition into destination's predicate list.  */
232
233   /* If C is true, then TRUE_EDGE is taken.  */
234   add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
235
236   /* If C is false, then FALSE_EDGE is taken.  */
237   c2 = invert_truthvalue_loc (loc, unshare_expr (c));
238   add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
239
240   /* Now this conditional statement is redundant.  Remove it.
241      But, do not remove exit condition!  Update exit condition
242      using new condition.  */
243   if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
244     {
245       gsi_remove (gsi, true);
246       cond = NULL_TREE;
247     }
248   return;
249 }
250
251 /* If-convert stmt T which is part of LOOP.
252    If T is a GIMPLE_ASSIGN then it is converted into conditional modify
253    expression using COND.  For conditional expressions, add condition in the
254    destination basic block's predicate list and remove conditional
255    expression itself.  BSI is the iterator used to traverse statements of
256    loop.  It is used here when it is required to delete current statement.  */
257
258 static tree
259 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
260                       gimple_stmt_iterator *gsi)
261 {
262   if (dump_file && (dump_flags & TDF_DETAILS))
263     {
264       fprintf (dump_file, "------if-convert stmt\n");
265       print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
266       print_generic_stmt (dump_file, cond, TDF_SLIM);
267     }
268
269   switch (gimple_code (t))
270     {
271       /* Labels are harmless here.  */
272     case GIMPLE_LABEL:
273       break;
274
275     case GIMPLE_DEBUG:
276       /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
277       if (gimple_debug_bind_p (gsi_stmt (*gsi)))
278         {
279           gimple_debug_bind_reset_value (gsi_stmt (*gsi));
280           update_stmt (gsi_stmt (*gsi));
281         }
282       break;
283
284     case GIMPLE_ASSIGN:
285       /* This GIMPLE_ASSIGN is killing previous value of LHS.  Appropriate
286          value will be selected by PHI node based on condition.  It is possible
287          that before this transformation, PHI nodes was selecting default
288          value and now it will use this new value.  This is OK because it does
289          not change the validity of the program.  */
290       break;
291
292     case GIMPLE_COND:
293       /* Update destination blocks' predicate list and remove this
294          condition expression.  */
295       tree_if_convert_cond_stmt (loop, t, cond, gsi);
296       cond = NULL_TREE;
297       break;
298
299     default:
300       gcc_unreachable ();
301     }
302   return cond;
303 }
304
305 /* Return true, iff PHI is if-convertible.  PHI is part of loop LOOP
306    and it belongs to basic block BB.
307    PHI is not if-convertible
308    - if it has more than 2 arguments,
309    - virtual PHI is immediately used in another PHI node,
310    - virtual PHI on BB other than header.  */
311
312 static bool
313 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
314 {
315   if (dump_file && (dump_flags & TDF_DETAILS))
316     {
317       fprintf (dump_file, "-------------------------\n");
318       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
319     }
320
321   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
322     {
323       if (dump_file && (dump_flags & TDF_DETAILS))
324         fprintf (dump_file, "More than two phi node args.\n");
325       return false;
326     }
327
328   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
329     {
330       imm_use_iterator imm_iter;
331       use_operand_p use_p;
332
333       if (bb != loop->header)
334         {
335           if (dump_file && (dump_flags & TDF_DETAILS))
336             fprintf (dump_file, "Virtual phi not on loop header.\n");
337           return false;
338         }
339       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
340         {
341           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
342             {
343               if (dump_file && (dump_flags & TDF_DETAILS))
344                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
345               return false;
346             }
347         }
348     }
349
350   return true;
351 }
352
353 /* Return true when STMT is if-convertible.
354
355    GIMPLE_ASSIGN statement is not if-convertible if,
356    - it is not movable,
357    - it could trap,
358    - LHS is not var decl.
359    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
360
361 static bool
362 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
363                                      gimple stmt)
364 {
365   tree lhs = gimple_assign_lhs (stmt);
366
367   if (dump_file && (dump_flags & TDF_DETAILS))
368     {
369       fprintf (dump_file, "-------------------------\n");
370       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
371     }
372
373   /* Some of these constrains might be too conservative.  */
374   if (stmt_ends_bb_p (stmt)
375       || gimple_has_volatile_ops (stmt)
376       || (TREE_CODE (lhs) == SSA_NAME
377           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
378       || gimple_has_side_effects (stmt))
379     {
380       if (dump_file && (dump_flags & TDF_DETAILS))
381         fprintf (dump_file, "stmt not suitable for ifcvt\n");
382       return false;
383     }
384
385   /* See if it needs speculative loading or not.  */
386   if (bb != loop->header
387       && gimple_assign_rhs_could_trap_p (stmt))
388     {
389       if (dump_file && (dump_flags & TDF_DETAILS))
390         fprintf (dump_file, "tree could trap...\n");
391       return false;
392     }
393
394   if (TREE_CODE (lhs) != SSA_NAME
395       && bb != loop->header
396       && !bb_with_exit_edge_p (loop, bb))
397     {
398       if (dump_file && (dump_flags & TDF_DETAILS))
399         {
400           fprintf (dump_file, "LHS is not var\n");
401           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
402         }
403       return false;
404     }
405
406   return true;
407 }
408
409 /* Return true, iff STMT is if-convertible.
410    Statement is if-convertible if,
411    - it is if-convertible GIMPLE_ASSGIN,
412    - it is GIMPLE_LABEL or GIMPLE_COND.
413    STMT is inside block BB, which is inside loop LOOP.  */
414
415 static bool
416 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
417 {
418   switch (gimple_code (stmt))
419     {
420     case GIMPLE_LABEL:
421     case GIMPLE_DEBUG:
422     case GIMPLE_COND:
423       return true;
424
425     case GIMPLE_ASSIGN:
426       return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
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_gimple_stmt (dump_file, stmt, 0, 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, all pred blocks of BB are visited.
498    Bitmap VISITED keeps history of visited blocks.  */
499
500 static bool
501 pred_blocks_visited_p (basic_block bb, bitmap *visited)
502 {
503   edge e;
504   edge_iterator ei;
505   FOR_EACH_EDGE (e, ei, bb->preds)
506     if (!bitmap_bit_p (*visited, e->src->index))
507       return false;
508
509   return true;
510 }
511
512 /* Get body of a LOOP in suitable order for if-conversion.  It is
513    caller's responsibility to deallocate basic block list.
514    If-conversion suitable order is, breadth first sort (BFS) order
515    with an additional constraint: select a block only if all its
516    predecessors are already selected.  */
517
518 static basic_block *
519 get_loop_body_in_if_conv_order (const struct loop *loop)
520 {
521   basic_block *blocks, *blocks_in_bfs_order;
522   basic_block bb;
523   bitmap visited;
524   unsigned int index = 0;
525   unsigned int visited_count = 0;
526
527   gcc_assert (loop->num_nodes);
528   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
529
530   blocks = XCNEWVEC (basic_block, loop->num_nodes);
531   visited = BITMAP_ALLOC (NULL);
532
533   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
534
535   index = 0;
536   while (index < loop->num_nodes)
537     {
538       bb = blocks_in_bfs_order [index];
539
540       if (bb->flags & BB_IRREDUCIBLE_LOOP)
541         {
542           free (blocks_in_bfs_order);
543           BITMAP_FREE (visited);
544           free (blocks);
545           return NULL;
546         }
547
548       if (!bitmap_bit_p (visited, bb->index))
549         {
550           if (pred_blocks_visited_p (bb, &visited)
551               || bb == loop->header)
552             {
553               /* This block is now visited.  */
554               bitmap_set_bit (visited, bb->index);
555               blocks[visited_count++] = bb;
556             }
557         }
558
559       index++;
560
561       if (index == loop->num_nodes
562           && visited_count != loop->num_nodes)
563         /* Not done yet.  */
564         index = 0;
565     }
566   free (blocks_in_bfs_order);
567   BITMAP_FREE (visited);
568   return blocks;
569 }
570
571 /* Return true, iff LOOP is if-convertible.
572    LOOP is if-convertible if:
573    - it is innermost,
574    - it has two or more basic blocks,
575    - it has only one exit,
576    - loop header is not the exit edge,
577    - if its basic blocks and phi nodes are if convertible.  */
578
579 static bool
580 if_convertible_loop_p (struct loop *loop)
581 {
582   basic_block bb;
583   gimple_stmt_iterator itr;
584   unsigned int i;
585   edge e;
586   edge_iterator ei;
587   basic_block exit_bb = NULL;
588
589   /* Handle only inner most loop.  */
590   if (!loop || loop->inner)
591     {
592       if (dump_file && (dump_flags & TDF_DETAILS))
593         fprintf (dump_file, "not inner most loop\n");
594       return false;
595     }
596
597   /* If only one block, no need for if-conversion.  */
598   if (loop->num_nodes <= 2)
599     {
600       if (dump_file && (dump_flags & TDF_DETAILS))
601         fprintf (dump_file, "less than 2 basic blocks\n");
602       return false;
603     }
604
605   /* More than one loop exit is too much to handle.  */
606   if (!single_exit (loop))
607     {
608       if (dump_file && (dump_flags & TDF_DETAILS))
609         fprintf (dump_file, "multiple exits\n");
610       return false;
611     }
612
613   /* ??? Check target's vector conditional operation support for vectorizer.  */
614
615   /* If one of the loop header's edge is exit edge then do not apply
616      if-conversion.  */
617   FOR_EACH_EDGE (e, ei, loop->header->succs)
618     {
619       if (loop_exit_edge_p (loop, e))
620         return false;
621     }
622
623   calculate_dominance_info (CDI_DOMINATORS);
624   calculate_dominance_info (CDI_POST_DOMINATORS);
625
626   /* Allow statements that can be handled during if-conversion.  */
627   ifc_bbs = get_loop_body_in_if_conv_order (loop);
628   if (!ifc_bbs)
629     {
630       if (dump_file && (dump_flags & TDF_DETAILS))
631         fprintf (dump_file,"Irreducible loop\n");
632       free_dominance_info (CDI_POST_DOMINATORS);
633       return false;
634     }
635
636   for (i = 0; i < loop->num_nodes; i++)
637     {
638       bb = ifc_bbs[i];
639
640       if (!if_convertible_bb_p (loop, bb, exit_bb))
641         return false;
642
643       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
644         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
645           return false;
646
647       itr = gsi_start_phis (bb);
648
649       if (!gsi_end_p (itr))
650         FOR_EACH_EDGE (e, ei, bb->preds)
651           e->aux = NULL;
652
653       for (; !gsi_end_p (itr); gsi_next (&itr))
654         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
655           return false;
656
657       if (bb_with_exit_edge_p (loop, bb))
658         exit_bb = bb;
659     }
660
661   if (dump_file)
662     fprintf (dump_file,"Applying if-conversion\n");
663
664   free_dominance_info (CDI_POST_DOMINATORS);
665   return true;
666 }
667
668 /* During if-conversion aux field from basic block structure is used to hold
669    predicate list.  Clean each basic block's predicate list for the given LOOP.
670    Also clean aux field of successor edges, used to hold true and false
671    condition from conditional expression.  */
672
673 static void
674 clean_predicate_lists (struct loop *loop)
675 {
676   basic_block *bb;
677   unsigned int i;
678   edge e;
679   edge_iterator ei;
680
681   bb = get_loop_body (loop);
682   for (i = 0; i < loop->num_nodes; i++)
683     {
684       bb[i]->aux = NULL;
685       FOR_EACH_EDGE (e, ei, bb[i]->succs)
686         e->aux = NULL;
687     }
688   free (bb);
689 }
690
691 /* Basic block BB has two predecessors. Using predecessor's aux field, set
692    appropriate condition COND for the PHI node replacement.  Return true block
693    whose phi arguments are selected when cond is true.  */
694
695 static basic_block
696 find_phi_replacement_condition (struct loop *loop,
697                                 basic_block bb, tree *cond,
698                                 gimple_stmt_iterator *gsi)
699 {
700   edge first_edge, second_edge;
701   tree tmp_cond;
702
703   gcc_assert (EDGE_COUNT (bb->preds) == 2);
704   first_edge = EDGE_PRED (bb, 0);
705   second_edge = EDGE_PRED (bb, 1);
706
707   /* Use condition based on following criteria:
708      1)
709        S1: x = !c ? a : b;
710
711        S2: x = c ? b : a;
712
713        S2 is preferred over S1. Make 'b' first_bb and use its condition.
714
715      2) Do not make loop header first_bb.
716
717      3)
718        S1: x = !(c == d)? a : b;
719
720        S21: t1 = c == d;
721        S22: x = t1 ? b : a;
722
723        S3: x = (c == d) ? b : a;
724
725        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
726        its condition.
727
728      4) If  pred B is dominated by pred A then use pred B's condition.
729         See PR23115.  */
730
731   /* Select condition that is not TRUTH_NOT_EXPR.  */
732   tmp_cond = (tree) (first_edge->src)->aux;
733   gcc_assert (tmp_cond);
734
735   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
736     {
737       edge tmp_edge;
738
739       tmp_edge = first_edge;
740       first_edge = second_edge;
741       second_edge = tmp_edge;
742     }
743
744   /* Check if FIRST_BB is loop header or not and make sure that
745      FIRST_BB does not dominate SECOND_BB.  */
746   if (first_edge->src == loop->header
747       || dominated_by_p (CDI_DOMINATORS,
748                          second_edge->src, first_edge->src))
749     {
750       *cond = (tree) (second_edge->src)->aux;
751
752       /* If there is a condition on an incoming edge, add it to the
753          incoming bb predicate.  */
754       if (second_edge->aux)
755         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
756                         *cond, (tree) second_edge->aux);
757
758       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
759         *cond = invert_truthvalue (*cond);
760       else
761         /* Select non loop header bb.  */
762         first_edge = second_edge;
763     }
764   else
765     {
766       *cond = (tree) (first_edge->src)->aux;
767
768       /* If there is a condition on an incoming edge, add it to the
769          incoming bb predicate.  */
770       if (first_edge->aux)
771         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
772                         *cond, (tree) first_edge->aux);
773     }
774
775   /* Gimplify the condition: the vectorizer prefers to have gimple
776      values as conditions.  Various targets use different means to
777      communicate conditions in vector compare operations.  Using a
778      gimple value allows the compiler to emit vector compare and
779      select RTL without exposing compare's result.  */
780   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
781                                     false, NULL_TREE,
782                                     true, GSI_SAME_STMT);
783   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
784     {
785       gimple new_stmt;
786
787       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
788       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
789       *cond = gimple_assign_lhs (new_stmt);
790     }
791
792   gcc_assert (*cond);
793
794   return first_edge->src;
795 }
796
797 /* Replace PHI node with conditional modify expr using COND.  This
798    routine does not handle PHI nodes with more than two arguments.
799
800    For example,
801      S1: A = PHI <x1(1), x2(5)
802    is converted into,
803      S2: A = cond ? x1 : x2;
804
805    The generated code is inserted at GSI that points to the top of
806    basic block's statement list.  When COND is true, phi arg from
807    TRUE_BB is selected.  */
808
809 static void
810 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
811                                           basic_block true_bb,
812                                           gimple_stmt_iterator *gsi)
813 {
814   gimple new_stmt;
815   basic_block bb;
816   tree rhs;
817   tree arg_0, arg_1;
818
819   gcc_assert (gimple_code (phi) == GIMPLE_PHI
820               && gimple_phi_num_args (phi) == 2);
821
822   bb = gimple_bb (phi);
823
824   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
825   if (EDGE_PRED (bb, 1)->src == true_bb)
826     {
827       arg_0 = gimple_phi_arg_def (phi, 1);
828       arg_1 = gimple_phi_arg_def (phi, 0);
829     }
830   else
831     {
832       arg_0 = gimple_phi_arg_def (phi, 0);
833       arg_1 = gimple_phi_arg_def (phi, 1);
834     }
835
836   /* Build new RHS using selected condition and arguments.  */
837   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
838                 unshare_expr (cond), unshare_expr (arg_0),
839                 unshare_expr (arg_1));
840
841   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
842   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
843   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
844   update_stmt (new_stmt);
845
846   if (dump_file && (dump_flags & TDF_DETAILS))
847     {
848       fprintf (dump_file, "new phi replacement stmt\n");
849       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
850     }
851 }
852
853 /* Process phi nodes for the given LOOP.  Replace phi nodes with
854    conditional modify expressions.  */
855
856 static void
857 process_phi_nodes (struct loop *loop)
858 {
859   basic_block bb;
860   unsigned int orig_loop_num_nodes = loop->num_nodes;
861   unsigned int i;
862
863   for (i = 1; i < orig_loop_num_nodes; i++)
864     {
865       gimple phi;
866       tree cond = NULL_TREE;
867       gimple_stmt_iterator gsi, phi_gsi;
868       basic_block true_bb = NULL;
869       bb = ifc_bbs[i];
870
871       if (bb == loop->header)
872         continue;
873
874       phi_gsi = gsi_start_phis (bb);
875       gsi = gsi_after_labels (bb);
876
877       /* BB has two predecessors.  Using predecessor's aux field, set
878          appropriate condition for the PHI node replacement.  */
879       if (!gsi_end_p (phi_gsi))
880         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
881
882       while (!gsi_end_p (phi_gsi))
883         {
884           phi = gsi_stmt (phi_gsi);
885           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
886           release_phi_node (phi);
887           gsi_next (&phi_gsi);
888         }
889       set_phi_nodes (bb, NULL);
890     }
891 }
892
893 /* Combine all the basic blocks from LOOP into one or two super basic
894    blocks.  Replace PHI nodes with conditional modify expressions.  */
895
896 static void
897 combine_blocks (struct loop *loop)
898 {
899   basic_block bb, exit_bb, merge_target_bb;
900   unsigned int orig_loop_num_nodes = loop->num_nodes;
901   unsigned int i;
902   edge e;
903   edge_iterator ei;
904
905   /* Process phi nodes to prepare blocks for merge.  */
906   process_phi_nodes (loop);
907
908   /* Merge basic blocks: first remove all the edges in the loop,
909      except for those from the exit block.  */
910   exit_bb = NULL;
911   for (i = 0; i < orig_loop_num_nodes; i++)
912     {
913       bb = ifc_bbs[i];
914       if (bb_with_exit_edge_p (loop, bb))
915         {
916           exit_bb = bb;
917           break;
918         }
919     }
920   gcc_assert (exit_bb != loop->latch);
921
922   for (i = 1; i < orig_loop_num_nodes; i++)
923     {
924       bb = ifc_bbs[i];
925
926       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
927         {
928           if (e->src == exit_bb)
929             ei_next (&ei);
930           else
931             remove_edge (e);
932         }
933     }
934
935   if (exit_bb != NULL)
936     {
937       if (exit_bb != loop->header)
938         {
939           /* Connect this node to loop header.  */
940           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
941           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
942         }
943
944       /* Redirect non-exit edges to loop->latch.  */
945       FOR_EACH_EDGE (e, ei, exit_bb->succs)
946         {
947           if (!loop_exit_edge_p (loop, e))
948             redirect_edge_and_branch (e, loop->latch);
949         }
950       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
951     }
952   else
953     {
954       /* If the loop does not have an exit, reconnect header and latch.  */
955       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
956       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
957     }
958
959   merge_target_bb = loop->header;
960   for (i = 1; i < orig_loop_num_nodes; i++)
961     {
962       gimple_stmt_iterator gsi;
963       gimple_stmt_iterator last;
964
965       bb = ifc_bbs[i];
966
967       if (bb == exit_bb || bb == loop->latch)
968         continue;
969
970       /* Remove labels and make stmts member of loop->header.  */
971       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
972         {
973           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
974             gsi_remove (&gsi, true);
975           else
976             {
977               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
978               gsi_next (&gsi);
979             }
980         }
981
982       /* Update stmt list.  */
983       last = gsi_last_bb (merge_target_bb);
984       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
985       set_bb_seq (bb, NULL);
986
987       delete_basic_block (bb);
988     }
989
990   /* Now if possible, merge loop header and block with exit edge.
991      This reduces number of basic blocks to 2.  Auto vectorizer addresses
992      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
993   if (exit_bb
994       && exit_bb != loop->header
995       && can_merge_blocks_p (loop->header, exit_bb))
996     merge_blocks (loop->header, exit_bb);
997 }
998
999 /* Main entry point.  Apply if-conversion to the LOOP.  Return true if
1000    successful otherwise return false.  If false is returned then loop
1001    remains unchanged.  */
1002
1003 static bool
1004 tree_if_conversion (struct loop *loop)
1005 {
1006   basic_block bb;
1007   gimple_stmt_iterator itr;
1008   unsigned int i;
1009
1010   ifc_bbs = NULL;
1011
1012   /* If-conversion is not appropriate for all loops.  First, check if
1013      loop is if-convertible or not.  */
1014   if (!if_convertible_loop_p (loop))
1015     {
1016       if (dump_file && (dump_flags & TDF_DETAILS))
1017         fprintf (dump_file,"-------------------------\n");
1018       if (ifc_bbs)
1019         {
1020           free (ifc_bbs);
1021           ifc_bbs = NULL;
1022         }
1023       free_dominance_info (CDI_POST_DOMINATORS);
1024       return false;
1025     }
1026
1027   /* Do actual work now.  */
1028   for (i = 0; i < loop->num_nodes; i++)
1029     {
1030       tree cond;
1031
1032       bb = ifc_bbs [i];
1033
1034       /* Update condition using predicate list.  */
1035       cond = (tree) bb->aux;
1036
1037       /* Process all statements in this basic block.
1038          Remove conditional expression, if any, and annotate
1039          destination basic block(s) appropriately.  */
1040       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1041         {
1042           gimple t = gsi_stmt (itr);
1043           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1044           if (!gsi_end_p (itr))
1045             gsi_next (&itr);
1046         }
1047
1048       /* If current bb has only one successor, then consider it as an
1049          unconditional goto.  */
1050       if (single_succ_p (bb))
1051         {
1052           basic_block bb_n = single_succ (bb);
1053
1054           /* Successor bb inherits predicate of its predecessor.  If there
1055              is no predicate in predecessor bb, then consider successor bb
1056              as always executed.  */
1057           if (cond == NULL_TREE)
1058             cond = boolean_true_node;
1059
1060           add_to_predicate_list (bb_n, cond);
1061         }
1062     }
1063
1064   /* Now, all statements are if-converted and basic blocks are
1065      annotated appropriately.  Combine all basic block into one huge
1066      basic block.  */
1067   combine_blocks (loop);
1068
1069   /* clean up */
1070   clean_predicate_lists (loop);
1071   free (ifc_bbs);
1072   ifc_bbs = NULL;
1073
1074   return true;
1075 }
1076
1077 /* Tree if-conversion pass management.  */
1078
1079 static unsigned int
1080 main_tree_if_conversion (void)
1081 {
1082   loop_iterator li;
1083   struct loop *loop;
1084
1085   if (number_of_loops () <= 1)
1086     return 0;
1087
1088   FOR_EACH_LOOP (li, loop, 0)
1089     tree_if_conversion (loop);
1090
1091   return 0;
1092 }
1093
1094 static bool
1095 gate_tree_if_conversion (void)
1096 {
1097   return flag_tree_vectorize != 0;
1098 }
1099
1100 struct gimple_opt_pass pass_if_conversion =
1101 {
1102  {
1103   GIMPLE_PASS,
1104   "ifcvt",                              /* name */
1105   gate_tree_if_conversion,              /* gate */
1106   main_tree_if_conversion,              /* execute */
1107   NULL,                                 /* sub */
1108   NULL,                                 /* next */
1109   0,                                    /* static_pass_number */
1110   TV_NONE,                              /* tv_id */
1111   PROP_cfg | PROP_ssa,                  /* properties_required */
1112   0,                                    /* properties_provided */
1113   0,                                    /* properties_destroyed */
1114   0,                                    /* todo_flags_start */
1115   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1116                                         /* todo_flags_finish */
1117  }
1118 };