OSDN Git Service

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