OSDN Git Service

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