OSDN Git Service

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