OSDN Git Service

3b2386aa329a620a0322dbb053860f836e11b4a7
[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 /* 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 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 /* Add condition COND into BB's predicate list.  PREV_COND is
151    existing condition.  */
152
153 static tree
154 add_to_dst_predicate_list (struct loop *loop, edge e,
155                            tree prev_cond, tree cond,
156                            gimple_stmt_iterator *gsi)
157 {
158   tree new_cond = NULL_TREE;
159
160   if (!flow_bb_inside_loop_p (loop, e->dest))
161     return NULL_TREE;
162
163   if (prev_cond == boolean_true_node || !prev_cond)
164     new_cond = unshare_expr (cond);
165   else
166     {
167       tree tmp;
168       gimple tmp_stmt = NULL;
169
170       prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
171                                             true, NULL, true, GSI_SAME_STMT);
172
173       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
174                                        true, NULL, true, GSI_SAME_STMT);
175
176       /* Add the condition to aux field of the edge.  In case edge
177          destination is a PHI node, this condition will be ANDed with
178          block predicate to construct complete condition.  */
179       e->aux = cond;
180
181       tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
182                     unshare_expr (prev_cond), cond);
183       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
184       gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
185       new_cond = gimple_assign_lhs (tmp_stmt);
186     }
187
188   add_to_predicate_list (e->dest, new_cond);
189   return new_cond;
190 }
191
192 /* Return true if one of the basic block BB edge is exit of LOOP.  */
193
194 static bool
195 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
196 {
197   edge e;
198   edge_iterator ei;
199   bool exit_edge_found = false;
200
201   FOR_EACH_EDGE (e, ei, bb->succs)
202     if (loop_exit_edge_p (loop, e))
203       {
204         exit_edge_found = true;
205         break;
206       }
207
208   return exit_edge_found;
209 }
210
211 /* STMT is a GIMPLE_COND.  Update two destination's predicate list.
212    Remove COND_EXPR, if it is not the loop exit condition.  Otherwise
213    update loop exit condition appropriately.  GSI is the iterator
214    used to traverse statement list.  STMT is part of loop LOOP.  */
215
216 static void
217 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
218                            gimple_stmt_iterator *gsi)
219 {
220   tree c2;
221   edge true_edge, false_edge;
222   location_t loc = gimple_location (stmt);
223   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
224                             gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
225
226   extract_true_false_edges_from_block (gimple_bb (stmt),
227                                        &true_edge, &false_edge);
228
229   /* Add new condition into destination's predicate list.  */
230
231   /* If C is true, then TRUE_EDGE is taken.  */
232   add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
233
234   /* If C is false, then FALSE_EDGE is taken.  */
235   c2 = invert_truthvalue_loc (loc, unshare_expr (c));
236   add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
237
238   /* Now this conditional statement is redundant.  Remove it.
239      But, do not remove exit condition!  Update exit condition
240      using new condition.  */
241   if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
242     {
243       gsi_remove (gsi, true);
244       cond = NULL_TREE;
245     }
246   return;
247 }
248
249 /* If-convert stmt T which is part of LOOP.
250    If T is a GIMPLE_ASSIGN then it is converted into conditional modify
251    expression using COND.  For conditional expressions, add condition in the
252    destination basic block's predicate list and remove conditional
253    expression itself.  BSI is the iterator used to traverse statements of
254    loop.  It is used here when it is required to delete current statement.  */
255
256 static tree
257 tree_if_convert_stmt (struct loop *  loop, gimple t, tree cond,
258                       gimple_stmt_iterator *gsi)
259 {
260   if (dump_file && (dump_flags & TDF_DETAILS))
261     {
262       fprintf (dump_file, "------if-convert stmt\n");
263       print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
264       print_generic_stmt (dump_file, cond, TDF_SLIM);
265     }
266
267   switch (gimple_code (t))
268     {
269       /* Labels are harmless here.  */
270     case GIMPLE_LABEL:
271       break;
272
273     case GIMPLE_DEBUG:
274       /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
275       if (gimple_debug_bind_p (gsi_stmt (*gsi)))
276         {
277           gimple_debug_bind_reset_value (gsi_stmt (*gsi));
278           update_stmt (gsi_stmt (*gsi));
279         }
280       break;
281
282     case GIMPLE_ASSIGN:
283       /* This GIMPLE_ASSIGN is killing previous value of LHS.  Appropriate
284          value will be selected by PHI node based on condition.  It is possible
285          that before this transformation, PHI nodes was selecting default
286          value and now it will use this new value.  This is OK because it does
287          not change the validity of the program.  */
288       break;
289
290     case GIMPLE_COND:
291       /* Update destination blocks' predicate list and remove this
292          condition expression.  */
293       tree_if_convert_cond_stmt (loop, t, cond, gsi);
294       cond = NULL_TREE;
295       break;
296
297     default:
298       gcc_unreachable ();
299     }
300   return cond;
301 }
302
303 /* Return true, iff PHI is if-convertible.  PHI is part of loop LOOP
304    and it belongs to basic block BB.
305    PHI is not if-convertible
306    - if it has more than 2 arguments,
307    - virtual PHI is immediately used in another PHI node,
308    - virtual PHI on BB other than header.  */
309
310 static bool
311 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
312 {
313   if (dump_file && (dump_flags & TDF_DETAILS))
314     {
315       fprintf (dump_file, "-------------------------\n");
316       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
317     }
318
319   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
320     {
321       if (dump_file && (dump_flags & TDF_DETAILS))
322         fprintf (dump_file, "More than two phi node args.\n");
323       return false;
324     }
325
326   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
327     {
328       imm_use_iterator imm_iter;
329       use_operand_p use_p;
330
331       if (bb != loop->header)
332         {
333           if (dump_file && (dump_flags & TDF_DETAILS))
334             fprintf (dump_file, "Virtual phi not on loop header.\n");
335           return false;
336         }
337       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
338         {
339           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
340             {
341               if (dump_file && (dump_flags & TDF_DETAILS))
342                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
343               return false;
344             }
345         }
346     }
347
348   return true;
349 }
350
351 /* Return true, if STMT is if-convertible.
352    GIMPLE_ASSIGN statement is not if-convertible if,
353    - it is not movable,
354    - it could trap,
355    - LHS is not var decl.
356    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
357
358 static bool
359 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
360                                      gimple stmt)
361 {
362   tree lhs;
363
364   if (!is_gimple_assign (stmt))
365     return false;
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   lhs = gimple_assign_lhs (stmt);
374
375   /* Some of these constrains might be too conservative.  */
376   if (stmt_ends_bb_p (stmt)
377       || gimple_has_volatile_ops (stmt)
378       || (TREE_CODE (lhs) == SSA_NAME
379           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
380       || gimple_has_side_effects (stmt))
381     {
382       if (dump_file && (dump_flags & TDF_DETAILS))
383         fprintf (dump_file, "stmt not suitable for ifcvt\n");
384       return false;
385     }
386
387   /* See if it needs speculative loading or not.  */
388   if (bb != loop->header
389       && gimple_assign_rhs_could_trap_p (stmt))
390     {
391       if (dump_file && (dump_flags & TDF_DETAILS))
392         fprintf (dump_file, "tree could trap...\n");
393       return false;
394     }
395
396   if (TREE_CODE (lhs) != SSA_NAME
397       && bb != loop->header
398       && !bb_with_exit_edge_p (loop, bb))
399     {
400       if (dump_file && (dump_flags & TDF_DETAILS))
401         {
402           fprintf (dump_file, "LHS is not var\n");
403           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
404         }
405       return false;
406     }
407
408   return true;
409 }
410
411 /* Return true, iff STMT is if-convertible.
412    Statement is if-convertible if,
413    - it is if-convertible GIMPLE_ASSGIN,
414    - it is GIMPLE_LABEL or GIMPLE_COND.
415    STMT is inside block BB, which is inside loop LOOP.  */
416
417 static bool
418 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
419 {
420   switch (gimple_code (stmt))
421     {
422     case GIMPLE_LABEL:
423       break;
424
425     case GIMPLE_DEBUG:
426       break;
427
428     case GIMPLE_ASSIGN:
429       if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt))
430         return false;
431       break;
432
433     case GIMPLE_COND:
434       break;
435
436     default:
437       /* Don't know what to do with 'em so don't do anything.  */
438       if (dump_file && (dump_flags & TDF_DETAILS))
439         {
440           fprintf (dump_file, "don't know what to do\n");
441           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
442         }
443       return false;
444       break;
445     }
446
447   return true;
448 }
449
450 /* Return true, iff BB is if-convertible.
451    Note: This routine does _not_ check basic block statements and phis.
452    Basic block is not if-convertible if:
453    - basic block is non-empty and it is after exit block (in BFS order),
454    - basic block is after exit block but before latch,
455    - basic block edge(s) is not normal.
456    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
457    BB is inside loop LOOP.  */
458
459 static bool
460 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
461 {
462   edge e;
463   edge_iterator ei;
464
465   if (dump_file && (dump_flags & TDF_DETAILS))
466     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
467
468   if (exit_bb)
469     {
470       if (bb != loop->latch)
471         {
472           if (dump_file && (dump_flags & TDF_DETAILS))
473             fprintf (dump_file, "basic block after exit bb but before latch\n");
474           return false;
475         }
476       else if (!empty_block_p (bb))
477         {
478           if (dump_file && (dump_flags & TDF_DETAILS))
479             fprintf (dump_file, "non empty basic block after exit bb\n");
480           return false;
481         }
482       else if (bb == loop->latch
483                && bb != exit_bb
484                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
485           {
486             if (dump_file && (dump_flags & TDF_DETAILS))
487               fprintf (dump_file, "latch is not dominated by exit_block\n");
488             return false;
489           }
490     }
491
492   /* Be less adventurous and handle only normal edges.  */
493   FOR_EACH_EDGE (e, ei, bb->succs)
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, all pred blocks of BB are visited.
506    Bitmap VISITED keeps history of visited blocks.  */
507
508 static bool
509 pred_blocks_visited_p (basic_block bb, bitmap *visited)
510 {
511   edge e;
512   edge_iterator ei;
513   FOR_EACH_EDGE (e, ei, bb->preds)
514     if (!bitmap_bit_p (*visited, e->src->index))
515       return false;
516
517   return true;
518 }
519
520 /* Get body of a LOOP in suitable order for if-conversion.  It is
521    caller's responsibility to deallocate basic block list.
522    If-conversion suitable order is, breadth first sort (BFS) order
523    with an additional constraint: select a block only if all its
524    predecessors are already selected.  */
525
526 static basic_block *
527 get_loop_body_in_if_conv_order (const struct loop *loop)
528 {
529   basic_block *blocks, *blocks_in_bfs_order;
530   basic_block bb;
531   bitmap visited;
532   unsigned int index = 0;
533   unsigned int visited_count = 0;
534
535   gcc_assert (loop->num_nodes);
536   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
537
538   blocks = XCNEWVEC (basic_block, loop->num_nodes);
539   visited = BITMAP_ALLOC (NULL);
540
541   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
542
543   index = 0;
544   while (index < loop->num_nodes)
545     {
546       bb = blocks_in_bfs_order [index];
547
548       if (bb->flags & BB_IRREDUCIBLE_LOOP)
549         {
550           free (blocks_in_bfs_order);
551           BITMAP_FREE (visited);
552           free (blocks);
553           return NULL;
554         }
555
556       if (!bitmap_bit_p (visited, bb->index))
557         {
558           if (pred_blocks_visited_p (bb, &visited)
559               || bb == loop->header)
560             {
561               /* This block is now visited.  */
562               bitmap_set_bit (visited, bb->index);
563               blocks[visited_count++] = bb;
564             }
565         }
566
567       index++;
568
569       if (index == loop->num_nodes
570           && visited_count != loop->num_nodes)
571         /* Not done yet.  */
572         index = 0;
573     }
574   free (blocks_in_bfs_order);
575   BITMAP_FREE (visited);
576   return blocks;
577 }
578
579 /* Return true, iff LOOP is if-convertible.
580    LOOP is if-convertible if:
581    - it is innermost,
582    - it has two or more basic blocks,
583    - it has only one exit,
584    - loop header is not the exit edge,
585    - if its basic blocks and phi nodes are if convertible.  See above for
586      more info.
587    FOR_VECTORIZER enables vectorizer specific checks, for example, support
588    for vector conditions, data dependency checks, etc.
589    (Not implemented yet).  */
590
591 static bool
592 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
593 {
594   basic_block bb;
595   gimple_stmt_iterator itr;
596   unsigned int i;
597   edge e;
598   edge_iterator ei;
599   basic_block exit_bb = NULL;
600
601   /* Handle only inner most loop.  */
602   if (!loop || loop->inner)
603     {
604       if (dump_file && (dump_flags & TDF_DETAILS))
605         fprintf (dump_file, "not inner most loop\n");
606       return false;
607     }
608
609   /* If only one block, no need for if-conversion.  */
610   if (loop->num_nodes <= 2)
611     {
612       if (dump_file && (dump_flags & TDF_DETAILS))
613         fprintf (dump_file, "less than 2 basic blocks\n");
614       return false;
615     }
616
617   /* More than one loop exit is too much to handle.  */
618   if (!single_exit (loop))
619     {
620       if (dump_file && (dump_flags & TDF_DETAILS))
621         fprintf (dump_file, "multiple exits\n");
622       return false;
623     }
624
625   /* ??? Check target's vector conditional operation support for vectorizer.  */
626
627   /* If one of the loop header's edge is exit edge then do not apply
628      if-conversion.  */
629   FOR_EACH_EDGE (e, ei, loop->header->succs)
630     {
631       if (loop_exit_edge_p (loop, e))
632         return false;
633     }
634
635   calculate_dominance_info (CDI_DOMINATORS);
636   calculate_dominance_info (CDI_POST_DOMINATORS);
637
638   /* Allow statements that can be handled during if-conversion.  */
639   ifc_bbs = get_loop_body_in_if_conv_order (loop);
640   if (!ifc_bbs)
641     {
642       if (dump_file && (dump_flags & TDF_DETAILS))
643         fprintf (dump_file,"Irreducible loop\n");
644       free_dominance_info (CDI_POST_DOMINATORS);
645       return false;
646     }
647
648   for (i = 0; i < loop->num_nodes; i++)
649     {
650       bb = ifc_bbs[i];
651
652       if (!if_convertible_bb_p (loop, bb, exit_bb))
653         return false;
654
655       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
656         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
657           return false;
658
659       itr = gsi_start_phis (bb);
660
661       if (!gsi_end_p (itr))
662         FOR_EACH_EDGE (e, ei, bb->preds)
663           e->aux = NULL;
664
665       for (; !gsi_end_p (itr); gsi_next (&itr))
666         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
667           return false;
668
669       if (bb_with_exit_edge_p (loop, bb))
670         exit_bb = bb;
671     }
672
673   if (dump_file)
674     fprintf (dump_file,"Applying if-conversion\n");
675
676   free_dominance_info (CDI_POST_DOMINATORS);
677   return true;
678 }
679
680 /* During if-conversion aux field from basic block structure is used to hold
681    predicate list.  Clean each basic block's predicate list for the given LOOP.
682    Also clean aux field of successor edges, used to hold true and false
683    condition from conditional expression.  */
684
685 static void
686 clean_predicate_lists (struct loop *loop)
687 {
688   basic_block *bb;
689   unsigned int i;
690   edge e;
691   edge_iterator ei;
692
693   bb = get_loop_body (loop);
694   for (i = 0; i < loop->num_nodes; i++)
695     {
696       bb[i]->aux = NULL;
697       FOR_EACH_EDGE (e, ei, bb[i]->succs)
698         e->aux = NULL;
699     }
700   free (bb);
701 }
702
703 /* Basic block BB has two predecessors. Using predecessor's aux field, set
704    appropriate condition COND for the PHI node replacement.  Return true block
705    whose phi arguments are selected when cond is true.  */
706
707 static basic_block
708 find_phi_replacement_condition (struct loop *loop,
709                                 basic_block bb, tree *cond,
710                                 gimple_stmt_iterator *gsi)
711 {
712   edge first_edge, second_edge;
713   tree tmp_cond;
714
715   gcc_assert (EDGE_COUNT (bb->preds) == 2);
716   first_edge = EDGE_PRED (bb, 0);
717   second_edge = EDGE_PRED (bb, 1);
718
719   /* Use condition based on following criteria:
720      1)
721        S1: x = !c ? a : b;
722
723        S2: x = c ? b : a;
724
725        S2 is preferred over S1. Make 'b' first_bb and use its condition.
726
727      2) Do not make loop header first_bb.
728
729      3)
730        S1: x = !(c == d)? a : b;
731
732        S21: t1 = c == d;
733        S22: x = t1 ? b : a;
734
735        S3: x = (c == d) ? b : a;
736
737        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
738        its condition.
739
740      4) If  pred B is dominated by pred A then use pred B's condition.
741         See PR23115.  */
742
743   /* Select condition that is not TRUTH_NOT_EXPR.  */
744   tmp_cond = (tree) (first_edge->src)->aux;
745   gcc_assert (tmp_cond);
746
747   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
748     {
749       edge tmp_edge;
750
751       tmp_edge = first_edge;
752       first_edge = second_edge;
753       second_edge = tmp_edge;
754     }
755
756   /* Check if FIRST_BB is loop header or not and make sure that
757      FIRST_BB does not dominate SECOND_BB.  */
758   if (first_edge->src == loop->header
759       || dominated_by_p (CDI_DOMINATORS,
760                          second_edge->src, first_edge->src))
761     {
762       *cond = (tree) (second_edge->src)->aux;
763
764       /* If there is a condition on an incoming edge,
765          AND it with the incoming bb predicate.  */
766       if (second_edge->aux)
767         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
768                         *cond, (tree) second_edge->aux);
769
770       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
771         /* We can be smart here and choose inverted
772            condition without switching bbs.  */
773         *cond = invert_truthvalue (*cond);
774       else
775         /* Select non loop header bb.  */
776         first_edge = second_edge;
777     }
778   else
779     {
780       /* FIRST_BB is not loop header */
781       *cond = (tree) (first_edge->src)->aux;
782
783       /* If there is a condition on an incoming edge,
784          AND it with the incoming bb predicate.  */
785       if (first_edge->aux)
786         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
787                         *cond, (tree) first_edge->aux);
788     }
789
790   /* Create temp. for the condition. Vectorizer prefers to have gimple
791      value as condition. Various targets use different means to communicate
792      condition in vector compare operation. Using gimple value allows
793      compiler to emit vector compare and select RTL without exposing
794      compare's result.  */
795   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
796                                     false, NULL_TREE,
797                                     true, GSI_SAME_STMT);
798   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
799     {
800       gimple new_stmt;
801
802       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
803       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
804       *cond = gimple_assign_lhs (new_stmt);
805     }
806
807   gcc_assert (*cond);
808
809   return first_edge->src;
810 }
811
812
813 /* Replace PHI node with conditional modify expr using COND.
814    This routine does not handle PHI nodes with more than two arguments.
815    For example,
816      S1: A = PHI <x1(1), x2(5)
817    is converted into,
818      S2: A = cond ? x1 : x2;
819    S2 is inserted at the top of basic block's statement list.
820    When COND is true, phi arg from TRUE_BB is selected.
821 */
822
823 static void
824 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
825                                           basic_block true_bb,
826                                           gimple_stmt_iterator *gsi)
827 {
828   gimple new_stmt;
829   basic_block bb;
830   tree rhs;
831   tree arg_0, arg_1;
832
833   gcc_assert (gimple_code (phi) == GIMPLE_PHI);
834
835   /* If this is not filtered earlier, then now it is too late.  */
836   gcc_assert (gimple_phi_num_args (phi) == 2);
837
838   /* Find basic block and initialize iterator.  */
839   bb = gimple_bb (phi);
840
841   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
842   if (EDGE_PRED (bb, 1)->src == true_bb)
843     {
844       arg_0 = gimple_phi_arg_def (phi, 1);
845       arg_1 = gimple_phi_arg_def (phi, 0);
846     }
847   else
848     {
849       arg_0 = gimple_phi_arg_def (phi, 0);
850       arg_1 = gimple_phi_arg_def (phi, 1);
851     }
852
853   /* Build new RHS using selected condition and arguments.  */
854   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
855                 unshare_expr (cond), unshare_expr (arg_0),
856                 unshare_expr (arg_1));
857
858   /* Create new GIMPLE_ASSIGN statement using RHS.  */
859   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
860
861   /* Make new statement definition of the original phi result.  */
862   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
863
864   /* Insert using iterator.  */
865   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
866   update_stmt (new_stmt);
867
868   if (dump_file && (dump_flags & TDF_DETAILS))
869     {
870       fprintf (dump_file, "new phi replacement stmt\n");
871       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
872     }
873 }
874
875 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
876    modify expr.  */
877
878 static void
879 process_phi_nodes (struct loop *loop)
880 {
881   basic_block bb;
882   unsigned int orig_loop_num_nodes = loop->num_nodes;
883   unsigned int i;
884
885   /* Replace phi nodes with cond. modify expr.  */
886   for (i = 1; i < orig_loop_num_nodes; i++)
887     {
888       gimple phi;
889       tree cond = NULL_TREE;
890       gimple_stmt_iterator gsi, phi_gsi;
891       basic_block true_bb = NULL;
892       bb = ifc_bbs[i];
893
894       if (bb == loop->header)
895         continue;
896
897       phi_gsi = gsi_start_phis (bb);
898       gsi = gsi_after_labels (bb);
899
900       /* BB has two predecessors. Using predecessor's aux field, set
901          appropriate condition for the PHI node replacement.  */
902       if (!gsi_end_p (phi_gsi))
903         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
904
905       while (!gsi_end_p (phi_gsi))
906         {
907           phi = gsi_stmt (phi_gsi);
908           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
909           release_phi_node (phi);
910           gsi_next (&phi_gsi);
911         }
912       set_phi_nodes (bb, NULL);
913     }
914   return;
915 }
916
917 /* Combine all basic block from the given LOOP into one or two super
918    basic block.  Replace PHI nodes with conditional modify expression.  */
919
920 static void
921 combine_blocks (struct loop *loop)
922 {
923   basic_block bb, exit_bb, merge_target_bb;
924   unsigned int orig_loop_num_nodes = loop->num_nodes;
925   unsigned int i;
926   edge e;
927   edge_iterator ei;
928
929   /* Process phi nodes to prepare blocks for merge.  */
930   process_phi_nodes (loop);
931
932   /* Merge basic blocks.  First remove all the edges in the loop, except
933      for those from the exit block.  */
934   exit_bb = NULL;
935   for (i = 0; i < orig_loop_num_nodes; i++)
936     {
937       bb = ifc_bbs[i];
938       if (bb_with_exit_edge_p (loop, bb))
939         {
940           exit_bb = bb;
941           break;
942         }
943     }
944   gcc_assert (exit_bb != loop->latch);
945
946   for (i = 1; i < orig_loop_num_nodes; i++)
947     {
948       bb = ifc_bbs[i];
949
950       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
951         {
952           if (e->src == exit_bb)
953             ei_next (&ei);
954           else
955             remove_edge (e);
956         }
957     }
958
959   if (exit_bb != NULL)
960     {
961       if (exit_bb != loop->header)
962         {
963           /* Connect this node with loop header.  */
964           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
965           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
966         }
967
968       /* Redirect non-exit edges to loop->latch.  */
969       FOR_EACH_EDGE (e, ei, exit_bb->succs)
970         {
971           if (!loop_exit_edge_p (loop, e))
972             redirect_edge_and_branch (e, loop->latch);
973         }
974       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
975     }
976   else
977     {
978       /* If the loop does not have exit then reconnect header and latch.  */
979       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
980       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
981     }
982
983   merge_target_bb = loop->header;
984   for (i = 1; i < orig_loop_num_nodes; i++)
985     {
986       gimple_stmt_iterator gsi;
987       gimple_stmt_iterator last;
988
989       bb = ifc_bbs[i];
990
991       if (bb == exit_bb || bb == loop->latch)
992         continue;
993
994       /* Remove labels and make stmts member of loop->header.  */
995       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
996         {
997           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
998             gsi_remove (&gsi, true);
999           else
1000             {
1001               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1002               gsi_next (&gsi);
1003             }
1004         }
1005
1006       /* Update stmt list.  */
1007       last = gsi_last_bb (merge_target_bb);
1008       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1009       set_bb_seq (bb, NULL);
1010
1011       delete_basic_block (bb);
1012     }
1013
1014   /* Now if possible, merge loop header and block with exit edge.
1015      This reduces number of basic blocks to 2.  Auto vectorizer addresses
1016      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1017   if (exit_bb
1018       && exit_bb != loop->header
1019       && can_merge_blocks_p (loop->header, exit_bb))
1020     merge_blocks (loop->header, exit_bb);
1021 }
1022
1023 /* Main entry point.  Apply if-conversion to the LOOP.  Return true if
1024    successful otherwise return false.  If false is returned then loop
1025    remains unchanged.  FOR_VECTORIZER is a boolean flag.  It indicates
1026    whether if-conversion is used for vectorizer or not.  If it is used
1027    for vectorizer, additional checks are used. (Vectorization checks
1028    are not yet implemented).  */
1029
1030 static bool
1031 tree_if_conversion (struct loop *loop, bool for_vectorizer)
1032 {
1033   basic_block bb;
1034   gimple_stmt_iterator itr;
1035   unsigned int i;
1036
1037   ifc_bbs = NULL;
1038
1039   /* If-conversion is not appropriate for all loops.  First, check if
1040      loop is if-convertible or not.  */
1041   if (!if_convertible_loop_p (loop, for_vectorizer))
1042     {
1043       if (dump_file && (dump_flags & TDF_DETAILS))
1044         fprintf (dump_file,"-------------------------\n");
1045       if (ifc_bbs)
1046         {
1047           free (ifc_bbs);
1048           ifc_bbs = NULL;
1049         }
1050       free_dominance_info (CDI_POST_DOMINATORS);
1051       return false;
1052     }
1053
1054   /* Do actual work now.  */
1055   for (i = 0; i < loop->num_nodes; i++)
1056     {
1057       tree cond;
1058
1059       bb = ifc_bbs [i];
1060
1061       /* Update condition using predicate list.  */
1062       cond = (tree) bb->aux;
1063
1064       /* Process all statements in this basic block.
1065          Remove conditional expression, if any, and annotate
1066          destination basic block(s) appropriately.  */
1067       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1068         {
1069           gimple t = gsi_stmt (itr);
1070           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1071           if (!gsi_end_p (itr))
1072             gsi_next (&itr);
1073         }
1074
1075       /* If current bb has only one successor, then consider it as an
1076          unconditional goto.  */
1077       if (single_succ_p (bb))
1078         {
1079           basic_block bb_n = single_succ (bb);
1080
1081           /* Successor bb inherits predicate of its predecessor.  If there
1082              is no predicate in predecessor bb, then consider successor bb
1083              as always executed.  */
1084           if (cond == NULL_TREE)
1085             cond = boolean_true_node;
1086
1087           add_to_predicate_list (bb_n, cond);
1088         }
1089     }
1090
1091   /* Now, all statements are if-converted and basic blocks are
1092      annotated appropriately.  Combine all basic block into one huge
1093      basic block.  */
1094   combine_blocks (loop);
1095
1096   /* clean up */
1097   clean_predicate_lists (loop);
1098   free (ifc_bbs);
1099   ifc_bbs = NULL;
1100
1101   return true;
1102 }
1103
1104 /* Tree if-conversion pass management.  */
1105
1106 static unsigned int
1107 main_tree_if_conversion (void)
1108 {
1109   loop_iterator li;
1110   struct loop *loop;
1111
1112   if (number_of_loops () <= 1)
1113     return 0;
1114
1115   FOR_EACH_LOOP (li, loop, 0)
1116     {
1117       tree_if_conversion (loop, true);
1118     }
1119   return 0;
1120 }
1121
1122 static bool
1123 gate_tree_if_conversion (void)
1124 {
1125   return flag_tree_vectorize != 0;
1126 }
1127
1128 struct gimple_opt_pass pass_if_conversion =
1129 {
1130  {
1131   GIMPLE_PASS,
1132   "ifcvt",                              /* name */
1133   gate_tree_if_conversion,              /* gate */
1134   main_tree_if_conversion,              /* execute */
1135   NULL,                                 /* sub */
1136   NULL,                                 /* next */
1137   0,                                    /* static_pass_number */
1138   TV_NONE,                              /* tv_id */
1139   PROP_cfg | PROP_ssa,                  /* properties_required */
1140   0,                                    /* properties_provided */
1141   0,                                    /* properties_destroyed */
1142   0,                                    /* todo_flags_start */
1143   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1144                                         /* todo_flags_finish */
1145  }
1146 };