OSDN Git Service

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