OSDN Git Service

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