VOP_FSYNC.9: Missing comma
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-if-conv.c
1 /* If-conversion for vectorizer.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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 "basic-block.h"
92 #include "tree-pretty-print.h"
93 #include "gimple-pretty-print.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 "dbgcnt.h"
102
103 /* List of basic blocks in if-conversion-suitable order.  */
104 static basic_block *ifc_bbs;
105
106 /* Structure used to predicate basic blocks.  This is attached to the
107    ->aux field of the BBs in the loop to be if-converted.  */
108 typedef struct bb_predicate_s {
109
110   /* The condition under which this basic block is executed.  */
111   tree predicate;
112
113   /* PREDICATE is gimplified, and the sequence of statements is
114      recorded here, in order to avoid the duplication of computations
115      that occur in previous conditions.  See PR44483.  */
116   gimple_seq predicate_gimplified_stmts;
117 } *bb_predicate_p;
118
119 /* Returns true when the basic block BB has a predicate.  */
120
121 static inline bool
122 bb_has_predicate (basic_block bb)
123 {
124   return bb->aux != NULL;
125 }
126
127 /* Returns the gimplified predicate for basic block BB.  */
128
129 static inline tree
130 bb_predicate (basic_block bb)
131 {
132   return ((bb_predicate_p) bb->aux)->predicate;
133 }
134
135 /* Sets the gimplified predicate COND for basic block BB.  */
136
137 static inline void
138 set_bb_predicate (basic_block bb, tree cond)
139 {
140   gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
141                && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
142               || is_gimple_condexpr (cond));
143   ((bb_predicate_p) bb->aux)->predicate = cond;
144 }
145
146 /* Returns the sequence of statements of the gimplification of the
147    predicate for basic block BB.  */
148
149 static inline gimple_seq
150 bb_predicate_gimplified_stmts (basic_block bb)
151 {
152   return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts;
153 }
154
155 /* Sets the sequence of statements STMTS of the gimplification of the
156    predicate for basic block BB.  */
157
158 static inline void
159 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
160 {
161   ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts;
162 }
163
164 /* Adds the sequence of statements STMTS to the sequence of statements
165    of the predicate for basic block BB.  */
166
167 static inline void
168 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
169 {
170   gimple_seq_add_seq
171     (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts);
172 }
173
174 /* Initializes to TRUE the predicate of basic block BB.  */
175
176 static inline void
177 init_bb_predicate (basic_block bb)
178 {
179   bb->aux = XNEW (struct bb_predicate_s);
180   set_bb_predicate_gimplified_stmts (bb, NULL);
181   set_bb_predicate (bb, boolean_true_node);
182 }
183
184 /* Free the predicate of basic block BB.  */
185
186 static inline void
187 free_bb_predicate (basic_block bb)
188 {
189   gimple_seq stmts;
190
191   if (!bb_has_predicate (bb))
192     return;
193
194   /* Release the SSA_NAMEs created for the gimplification of the
195      predicate.  */
196   stmts = bb_predicate_gimplified_stmts (bb);
197   if (stmts)
198     {
199       gimple_stmt_iterator i;
200
201       for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
202         free_stmt_operands (gsi_stmt (i));
203     }
204
205   free (bb->aux);
206   bb->aux = NULL;
207 }
208
209 /* Free the predicate of BB and reinitialize it with the true
210    predicate.  */
211
212 static inline void
213 reset_bb_predicate (basic_block bb)
214 {
215   free_bb_predicate (bb);
216   init_bb_predicate (bb);
217 }
218
219 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
220    the expression EXPR.  Inserts the statement created for this
221    computation before GSI and leaves the iterator GSI at the same
222    statement.  */
223
224 static tree
225 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
226 {
227   const char *name = "_ifc_";
228   tree var, new_name;
229   gimple stmt;
230
231   /* Create new temporary variable.  */
232   var = create_tmp_var (type, name);
233   add_referenced_var (var);
234
235   /* Build new statement to assign EXPR to new variable.  */
236   stmt = gimple_build_assign (var, expr);
237
238   /* Get SSA name for the new variable and set make new statement
239      its definition statement.  */
240   new_name = make_ssa_name (var, stmt);
241   gimple_assign_set_lhs (stmt, new_name);
242   SSA_NAME_DEF_STMT (new_name) = stmt;
243   update_stmt (stmt);
244
245   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
246   return gimple_assign_lhs (stmt);
247 }
248
249 /* Return true when COND is a true predicate.  */
250
251 static inline bool
252 is_true_predicate (tree cond)
253 {
254   return (cond == NULL_TREE
255           || cond == boolean_true_node
256           || integer_onep (cond));
257 }
258
259 /* Returns true when BB has a predicate that is not trivial: true or
260    NULL_TREE.  */
261
262 static inline bool
263 is_predicated (basic_block bb)
264 {
265   return !is_true_predicate (bb_predicate (bb));
266 }
267
268 /* Parses the predicate COND and returns its comparison code and
269    operands OP0 and OP1.  */
270
271 static enum tree_code
272 parse_predicate (tree cond, tree *op0, tree *op1)
273 {
274   gimple s;
275
276   if (TREE_CODE (cond) == SSA_NAME
277       && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
278     {
279       if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
280         {
281           *op0 = gimple_assign_rhs1 (s);
282           *op1 = gimple_assign_rhs2 (s);
283           return gimple_assign_rhs_code (s);
284         }
285
286       else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
287         {
288           tree op = gimple_assign_rhs1 (s);
289           tree type = TREE_TYPE (op);
290           enum tree_code code = parse_predicate (op, op0, op1);
291
292           return code == ERROR_MARK ? ERROR_MARK
293             : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type)));
294         }
295
296       return ERROR_MARK;
297     }
298
299   if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
300     {
301       *op0 = TREE_OPERAND (cond, 0);
302       *op1 = TREE_OPERAND (cond, 1);
303       return TREE_CODE (cond);
304     }
305
306   return ERROR_MARK;
307 }
308
309 /* Returns the fold of predicate C1 OR C2 at location LOC.  */
310
311 static tree
312 fold_or_predicates (location_t loc, tree c1, tree c2)
313 {
314   tree op1a, op1b, op2a, op2b;
315   enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
316   enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
317
318   if (code1 != ERROR_MARK && code2 != ERROR_MARK)
319     {
320       tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
321                                           code2, op2a, op2b);
322       if (t)
323         return t;
324     }
325
326   return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
327 }
328
329 /* Add condition NC to the predicate list of basic block BB.  */
330
331 static inline void
332 add_to_predicate_list (basic_block bb, tree nc)
333 {
334   tree bc, *tp;
335
336   if (is_true_predicate (nc))
337     return;
338
339   if (!is_predicated (bb))
340     bc = nc;
341   else
342     {
343       bc = bb_predicate (bb);
344       bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
345       if (is_true_predicate (bc))
346         {
347           reset_bb_predicate (bb);
348           return;
349         }
350     }
351
352   /* Allow a TRUTH_NOT_EXPR around the main predicate.  */
353   if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
354     tp = &TREE_OPERAND (bc, 0);
355   else
356     tp = &bc;
357   if (!is_gimple_condexpr (*tp))
358     {
359       gimple_seq stmts;
360       *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
361       add_bb_predicate_gimplified_stmts (bb, stmts);
362     }
363   set_bb_predicate (bb, bc);
364 }
365
366 /* Add the condition COND to the previous condition PREV_COND, and add
367    this to the predicate list of the destination of edge E.  LOOP is
368    the loop to be if-converted.  */
369
370 static void
371 add_to_dst_predicate_list (struct loop *loop, edge e,
372                            tree prev_cond, tree cond)
373 {
374   if (!flow_bb_inside_loop_p (loop, e->dest))
375     return;
376
377   if (!is_true_predicate (prev_cond))
378     cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
379                         prev_cond, cond);
380
381   add_to_predicate_list (e->dest, cond);
382 }
383
384 /* Return true if one of the successor edges of BB exits LOOP.  */
385
386 static bool
387 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
388 {
389   edge e;
390   edge_iterator ei;
391
392   FOR_EACH_EDGE (e, ei, bb->succs)
393     if (loop_exit_edge_p (loop, e))
394       return true;
395
396   return false;
397 }
398
399 /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
400    and it belongs to basic block BB.
401
402    PHI is not if-convertible if:
403    - it has more than 2 arguments.
404
405    When the flag_tree_loop_if_convert_stores is not set, PHI is not
406    if-convertible if:
407    - a virtual PHI is immediately used in another PHI node,
408    - there is a virtual PHI in a BB other than the loop->header.  */
409
410 static bool
411 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
412 {
413   if (dump_file && (dump_flags & TDF_DETAILS))
414     {
415       fprintf (dump_file, "-------------------------\n");
416       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
417     }
418
419   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
420     {
421       if (dump_file && (dump_flags & TDF_DETAILS))
422         fprintf (dump_file, "More than two phi node args.\n");
423       return false;
424     }
425
426   if (flag_tree_loop_if_convert_stores)
427     return true;
428
429   /* When the flag_tree_loop_if_convert_stores is not set, check
430      that there are no memory writes in the branches of the loop to be
431      if-converted.  */
432   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
433     {
434       imm_use_iterator imm_iter;
435       use_operand_p use_p;
436
437       if (bb != loop->header)
438         {
439           if (dump_file && (dump_flags & TDF_DETAILS))
440             fprintf (dump_file, "Virtual phi not on loop->header.\n");
441           return false;
442         }
443
444       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
445         {
446           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
447             {
448               if (dump_file && (dump_flags & TDF_DETAILS))
449                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
450               return false;
451             }
452         }
453     }
454
455   return true;
456 }
457
458 /* Records the status of a data reference.  This struct is attached to
459    each DR->aux field.  */
460
461 struct ifc_dr {
462   /* -1 when not initialized, 0 when false, 1 when true.  */
463   int written_at_least_once;
464
465   /* -1 when not initialized, 0 when false, 1 when true.  */
466   int rw_unconditionally;
467 };
468
469 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
470 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
471 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
472
473 /* Returns true when the memory references of STMT are read or written
474    unconditionally.  In other words, this function returns true when
475    for every data reference A in STMT there exist other accesses to
476    a data reference with the same base with predicates that add up (OR-up) to
477    the true predicate: this ensures that the data reference A is touched
478    (read or written) on every iteration of the if-converted loop.  */
479
480 static bool
481 memrefs_read_or_written_unconditionally (gimple stmt,
482                                          VEC (data_reference_p, heap) *drs)
483 {
484   int i, j;
485   data_reference_p a, b;
486   tree ca = bb_predicate (gimple_bb (stmt));
487
488   for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
489     if (DR_STMT (a) == stmt)
490       {
491         bool found = false;
492         int x = DR_RW_UNCONDITIONALLY (a);
493
494         if (x == 0)
495           return false;
496
497         if (x == 1)
498           continue;
499
500         for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
501           {
502             tree ref_base_a = DR_REF (a);
503             tree ref_base_b = DR_REF (b);
504
505             if (DR_STMT (b) == stmt)
506               continue;
507
508             while (TREE_CODE (ref_base_a) == COMPONENT_REF
509                    || TREE_CODE (ref_base_a) == IMAGPART_EXPR
510                    || TREE_CODE (ref_base_a) == REALPART_EXPR)
511               ref_base_a = TREE_OPERAND (ref_base_a, 0);
512
513             while (TREE_CODE (ref_base_b) == COMPONENT_REF
514                    || TREE_CODE (ref_base_b) == IMAGPART_EXPR
515                    || TREE_CODE (ref_base_b) == REALPART_EXPR)
516               ref_base_b = TREE_OPERAND (ref_base_b, 0);
517
518             if (!operand_equal_p (ref_base_a, ref_base_b, 0))
519               {
520                 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
521
522                 if (DR_RW_UNCONDITIONALLY (b) == 1
523                     || is_true_predicate (cb)
524                     || is_true_predicate (ca
525                         = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
526                   {
527                     DR_RW_UNCONDITIONALLY (a) = 1;
528                     DR_RW_UNCONDITIONALLY (b) = 1;
529                     found = true;
530                     break;
531                   }
532                }
533             }
534
535         if (!found)
536           {
537             DR_RW_UNCONDITIONALLY (a) = 0;
538             return false;
539           }
540       }
541
542   return true;
543 }
544
545 /* Returns true when the memory references of STMT are unconditionally
546    written.  In other words, this function returns true when for every
547    data reference A written in STMT, there exist other writes to the
548    same data reference with predicates that add up (OR-up) to the true
549    predicate: this ensures that the data reference A is written on
550    every iteration of the if-converted loop.  */
551
552 static bool
553 write_memrefs_written_at_least_once (gimple stmt,
554                                      VEC (data_reference_p, heap) *drs)
555 {
556   int i, j;
557   data_reference_p a, b;
558   tree ca = bb_predicate (gimple_bb (stmt));
559
560   for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
561     if (DR_STMT (a) == stmt
562         && DR_IS_WRITE (a))
563       {
564         bool found = false;
565         int x = DR_WRITTEN_AT_LEAST_ONCE (a);
566
567         if (x == 0)
568           return false;
569
570         if (x == 1)
571           continue;
572
573         for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
574           if (DR_STMT (b) != stmt
575               && DR_IS_WRITE (b)
576               && same_data_refs_base_objects (a, b))
577             {
578               tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
579
580               if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
581                   || is_true_predicate (cb)
582                   || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
583                                                                  ca, cb)))
584                 {
585                   DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
586                   DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
587                   found = true;
588                   break;
589                 }
590             }
591
592         if (!found)
593           {
594             DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
595             return false;
596           }
597       }
598
599   return true;
600 }
601
602 /* Return true when the memory references of STMT won't trap in the
603    if-converted code.  There are two things that we have to check for:
604
605    - writes to memory occur to writable memory: if-conversion of
606    memory writes transforms the conditional memory writes into
607    unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
608    into "A[i] = cond ? foo : A[i]", and as the write to memory may not
609    be executed at all in the original code, it may be a readonly
610    memory.  To check that A is not const-qualified, we check that
611    there exists at least an unconditional write to A in the current
612    function.
613
614    - reads or writes to memory are valid memory accesses for every
615    iteration.  To check that the memory accesses are correctly formed
616    and that we are allowed to read and write in these locations, we
617    check that the memory accesses to be if-converted occur at every
618    iteration unconditionally.  */
619
620 static bool
621 ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs)
622 {
623   return write_memrefs_written_at_least_once (stmt, refs)
624     && memrefs_read_or_written_unconditionally (stmt, refs);
625 }
626
627 /* Wrapper around gimple_could_trap_p refined for the needs of the
628    if-conversion.  Try to prove that the memory accesses of STMT could
629    not trap in the innermost loop containing STMT.  */
630
631 static bool
632 ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs)
633 {
634   if (gimple_vuse (stmt)
635       && !gimple_could_trap_p_1 (stmt, false, false)
636       && ifcvt_memrefs_wont_trap (stmt, refs))
637     return false;
638
639   return gimple_could_trap_p (stmt);
640 }
641
642 /* Return true when STMT is if-convertible.
643
644    GIMPLE_ASSIGN statement is not if-convertible if,
645    - it is not movable,
646    - it could trap,
647    - LHS is not var decl.  */
648
649 static bool
650 if_convertible_gimple_assign_stmt_p (gimple stmt,
651                                      VEC (data_reference_p, heap) *refs)
652 {
653   tree lhs = gimple_assign_lhs (stmt);
654   basic_block bb;
655
656   if (dump_file && (dump_flags & TDF_DETAILS))
657     {
658       fprintf (dump_file, "-------------------------\n");
659       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
660     }
661
662   if (!is_gimple_reg_type (TREE_TYPE (lhs)))
663     return false;
664
665   /* Some of these constrains might be too conservative.  */
666   if (stmt_ends_bb_p (stmt)
667       || gimple_has_volatile_ops (stmt)
668       || (TREE_CODE (lhs) == SSA_NAME
669           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
670       || gimple_has_side_effects (stmt))
671     {
672       if (dump_file && (dump_flags & TDF_DETAILS))
673         fprintf (dump_file, "stmt not suitable for ifcvt\n");
674       return false;
675     }
676
677   if (flag_tree_loop_if_convert_stores)
678     {
679       if (ifcvt_could_trap_p (stmt, refs))
680         {
681           if (dump_file && (dump_flags & TDF_DETAILS))
682             fprintf (dump_file, "tree could trap...\n");
683           return false;
684         }
685       return true;
686     }
687
688   if (gimple_assign_rhs_could_trap_p (stmt))
689     {
690       if (dump_file && (dump_flags & TDF_DETAILS))
691         fprintf (dump_file, "tree could trap...\n");
692       return false;
693     }
694
695   bb = gimple_bb (stmt);
696
697   if (TREE_CODE (lhs) != SSA_NAME
698       && bb != bb->loop_father->header
699       && !bb_with_exit_edge_p (bb->loop_father, bb))
700     {
701       if (dump_file && (dump_flags & TDF_DETAILS))
702         {
703           fprintf (dump_file, "LHS is not var\n");
704           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
705         }
706       return false;
707     }
708
709   return true;
710 }
711
712 /* Return true when STMT is if-convertible.
713
714    A statement is if-convertible if:
715    - it is an if-convertible GIMPLE_ASSGIN,
716    - it is a GIMPLE_LABEL or a GIMPLE_COND.  */
717
718 static bool
719 if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs)
720 {
721   switch (gimple_code (stmt))
722     {
723     case GIMPLE_LABEL:
724     case GIMPLE_DEBUG:
725     case GIMPLE_COND:
726       return true;
727
728     case GIMPLE_ASSIGN:
729       return if_convertible_gimple_assign_stmt_p (stmt, refs);
730
731     case GIMPLE_CALL:
732       {
733         tree fndecl = gimple_call_fndecl (stmt);
734         if (fndecl)
735           {
736             int flags = gimple_call_flags (stmt);
737             if ((flags & ECF_CONST)
738                 && !(flags & ECF_LOOPING_CONST_OR_PURE)
739                 /* We can only vectorize some builtins at the moment,
740                    so restrict if-conversion to those.  */
741                 && DECL_BUILT_IN (fndecl))
742               return true;
743           }
744         return false;
745       }
746
747     default:
748       /* Don't know what to do with 'em so don't do anything.  */
749       if (dump_file && (dump_flags & TDF_DETAILS))
750         {
751           fprintf (dump_file, "don't know what to do\n");
752           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
753         }
754       return false;
755       break;
756     }
757
758   return true;
759 }
760
761 /* Return true when BB post-dominates all its predecessors.  */
762
763 static bool
764 bb_postdominates_preds (basic_block bb)
765 {
766   unsigned i;
767
768   for (i = 0; i < EDGE_COUNT (bb->preds); i++)
769     if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb))
770       return false;
771
772   return true;
773 }
774
775 /* Return true when BB is if-convertible.  This routine does not check
776    basic block's statements and phis.
777
778    A basic block is not if-convertible if:
779    - it is non-empty and it is after the exit block (in BFS order),
780    - it is after the exit block but before the latch,
781    - its edges are not normal.
782
783    EXIT_BB is the basic block containing the exit of the LOOP.  BB is
784    inside LOOP.  */
785
786 static bool
787 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
788 {
789   edge e;
790   edge_iterator ei;
791
792   if (dump_file && (dump_flags & TDF_DETAILS))
793     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
794
795   if (EDGE_COUNT (bb->preds) > 2
796       || EDGE_COUNT (bb->succs) > 2)
797     return false;
798
799   if (exit_bb)
800     {
801       if (bb != loop->latch)
802         {
803           if (dump_file && (dump_flags & TDF_DETAILS))
804             fprintf (dump_file, "basic block after exit bb but before latch\n");
805           return false;
806         }
807       else if (!empty_block_p (bb))
808         {
809           if (dump_file && (dump_flags & TDF_DETAILS))
810             fprintf (dump_file, "non empty basic block after exit bb\n");
811           return false;
812         }
813       else if (bb == loop->latch
814                && bb != exit_bb
815                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
816           {
817             if (dump_file && (dump_flags & TDF_DETAILS))
818               fprintf (dump_file, "latch is not dominated by exit_block\n");
819             return false;
820           }
821     }
822
823   /* Be less adventurous and handle only normal edges.  */
824   FOR_EACH_EDGE (e, ei, bb->succs)
825     if (e->flags &
826         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
827       {
828         if (dump_file && (dump_flags & TDF_DETAILS))
829           fprintf (dump_file, "Difficult to handle edges\n");
830         return false;
831       }
832
833   if (EDGE_COUNT (bb->preds) == 2
834       && bb != loop->header
835       && !bb_postdominates_preds (bb))
836     return false;
837
838   return true;
839 }
840
841 /* Return true when all predecessor blocks of BB are visited.  The
842    VISITED bitmap keeps track of the visited blocks.  */
843
844 static bool
845 pred_blocks_visited_p (basic_block bb, bitmap *visited)
846 {
847   edge e;
848   edge_iterator ei;
849   FOR_EACH_EDGE (e, ei, bb->preds)
850     if (!bitmap_bit_p (*visited, e->src->index))
851       return false;
852
853   return true;
854 }
855
856 /* Get body of a LOOP in suitable order for if-conversion.  It is
857    caller's responsibility to deallocate basic block list.
858    If-conversion suitable order is, breadth first sort (BFS) order
859    with an additional constraint: select a block only if all its
860    predecessors are already selected.  */
861
862 static basic_block *
863 get_loop_body_in_if_conv_order (const struct loop *loop)
864 {
865   basic_block *blocks, *blocks_in_bfs_order;
866   basic_block bb;
867   bitmap visited;
868   unsigned int index = 0;
869   unsigned int visited_count = 0;
870
871   gcc_assert (loop->num_nodes);
872   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
873
874   blocks = XCNEWVEC (basic_block, loop->num_nodes);
875   visited = BITMAP_ALLOC (NULL);
876
877   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
878
879   index = 0;
880   while (index < loop->num_nodes)
881     {
882       bb = blocks_in_bfs_order [index];
883
884       if (bb->flags & BB_IRREDUCIBLE_LOOP)
885         {
886           free (blocks_in_bfs_order);
887           BITMAP_FREE (visited);
888           free (blocks);
889           return NULL;
890         }
891
892       if (!bitmap_bit_p (visited, bb->index))
893         {
894           if (pred_blocks_visited_p (bb, &visited)
895               || bb == loop->header)
896             {
897               /* This block is now visited.  */
898               bitmap_set_bit (visited, bb->index);
899               blocks[visited_count++] = bb;
900             }
901         }
902
903       index++;
904
905       if (index == loop->num_nodes
906           && visited_count != loop->num_nodes)
907         /* Not done yet.  */
908         index = 0;
909     }
910   free (blocks_in_bfs_order);
911   BITMAP_FREE (visited);
912   return blocks;
913 }
914
915 /* Returns true when the analysis of the predicates for all the basic
916    blocks in LOOP succeeded.
917
918    predicate_bbs first allocates the predicates of the basic blocks.
919    These fields are then initialized with the tree expressions
920    representing the predicates under which a basic block is executed
921    in the LOOP.  As the loop->header is executed at each iteration, it
922    has the "true" predicate.  Other statements executed under a
923    condition are predicated with that condition, for example
924
925    | if (x)
926    |   S1;
927    | else
928    |   S2;
929
930    S1 will be predicated with "x", and
931    S2 will be predicated with "!x".  */
932
933 static bool
934 predicate_bbs (loop_p loop)
935 {
936   unsigned int i;
937
938   for (i = 0; i < loop->num_nodes; i++)
939     init_bb_predicate (ifc_bbs[i]);
940
941   for (i = 0; i < loop->num_nodes; i++)
942     {
943       basic_block bb = ifc_bbs[i];
944       tree cond;
945       gimple_stmt_iterator itr;
946
947       /* The loop latch is always executed and has no extra conditions
948          to be processed: skip it.  */
949       if (bb == loop->latch)
950         {
951           reset_bb_predicate (loop->latch);
952           continue;
953         }
954
955       cond = bb_predicate (bb);
956
957       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
958         {
959           gimple stmt = gsi_stmt (itr);
960
961           switch (gimple_code (stmt))
962             {
963             case GIMPLE_LABEL:
964             case GIMPLE_ASSIGN:
965             case GIMPLE_CALL:
966             case GIMPLE_DEBUG:
967               break;
968
969             case GIMPLE_COND:
970               {
971                 tree c2, tem;
972                 edge true_edge, false_edge;
973                 location_t loc = gimple_location (stmt);
974                 tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
975                                           boolean_type_node,
976                                           gimple_cond_lhs (stmt),
977                                           gimple_cond_rhs (stmt));
978
979                 /* Add new condition into destination's predicate list.  */
980                 extract_true_false_edges_from_block (gimple_bb (stmt),
981                                                      &true_edge, &false_edge);
982
983                 /* If C is true, then TRUE_EDGE is taken.  */
984                 add_to_dst_predicate_list (loop, true_edge,
985                                            unshare_expr (cond),
986                                            unshare_expr (c));
987
988                 /* If C is false, then FALSE_EDGE is taken.  */
989                 c2 = invert_truthvalue_loc (loc, unshare_expr (c));
990                 tem = canonicalize_cond_expr_cond (c2);
991                 if (tem)
992                   c2 = tem;
993                 add_to_dst_predicate_list (loop, false_edge,
994                                            unshare_expr (cond), c2);
995
996                 cond = NULL_TREE;
997                 break;
998               }
999
1000             default:
1001               /* Not handled yet in if-conversion.  */
1002               return false;
1003             }
1004         }
1005
1006       /* If current bb has only one successor, then consider it as an
1007          unconditional goto.  */
1008       if (single_succ_p (bb))
1009         {
1010           basic_block bb_n = single_succ (bb);
1011
1012           /* The successor bb inherits the predicate of its
1013              predecessor.  If there is no predicate in the predecessor
1014              bb, then consider the successor bb as always executed.  */
1015           if (cond == NULL_TREE)
1016             cond = boolean_true_node;
1017
1018           add_to_predicate_list (bb_n, cond);
1019         }
1020     }
1021
1022   /* The loop header is always executed.  */
1023   reset_bb_predicate (loop->header);
1024   gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1025               && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1026
1027   return true;
1028 }
1029
1030 /* Return true when LOOP is if-convertible.  This is a helper function
1031    for if_convertible_loop_p.  REFS and DDRS are initialized and freed
1032    in if_convertible_loop_p.  */
1033
1034 static bool
1035 if_convertible_loop_p_1 (struct loop *loop,
1036                          VEC (loop_p, heap) **loop_nest,
1037                          VEC (data_reference_p, heap) **refs,
1038                          VEC (ddr_p, heap) **ddrs)
1039 {
1040   bool res;
1041   unsigned int i;
1042   basic_block exit_bb = NULL;
1043
1044   /* Don't if-convert the loop when the data dependences cannot be
1045      computed: the loop won't be vectorized in that case.  */
1046   res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
1047   if (!res)
1048     return false;
1049
1050   calculate_dominance_info (CDI_DOMINATORS);
1051   calculate_dominance_info (CDI_POST_DOMINATORS);
1052
1053   /* Allow statements that can be handled during if-conversion.  */
1054   ifc_bbs = get_loop_body_in_if_conv_order (loop);
1055   if (!ifc_bbs)
1056     {
1057       if (dump_file && (dump_flags & TDF_DETAILS))
1058         fprintf (dump_file, "Irreducible loop\n");
1059       return false;
1060     }
1061
1062   for (i = 0; i < loop->num_nodes; i++)
1063     {
1064       basic_block bb = ifc_bbs[i];
1065
1066       if (!if_convertible_bb_p (loop, bb, exit_bb))
1067         return false;
1068
1069       if (bb_with_exit_edge_p (loop, bb))
1070         exit_bb = bb;
1071     }
1072
1073   res = predicate_bbs (loop);
1074   if (!res)
1075     return false;
1076
1077   if (flag_tree_loop_if_convert_stores)
1078     {
1079       data_reference_p dr;
1080
1081       for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++)
1082         {
1083           dr->aux = XNEW (struct ifc_dr);
1084           DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1085           DR_RW_UNCONDITIONALLY (dr) = -1;
1086         }
1087     }
1088
1089   for (i = 0; i < loop->num_nodes; i++)
1090     {
1091       basic_block bb = ifc_bbs[i];
1092       gimple_stmt_iterator itr;
1093
1094       for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1095         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
1096           return false;
1097
1098       /* Check the if-convertibility of statements in predicated BBs.  */
1099       if (is_predicated (bb))
1100         for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1101           if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1102             return false;
1103     }
1104
1105   if (dump_file)
1106     fprintf (dump_file, "Applying if-conversion\n");
1107
1108   return true;
1109 }
1110
1111 /* Return true when LOOP is if-convertible.
1112    LOOP is if-convertible if:
1113    - it is innermost,
1114    - it has two or more basic blocks,
1115    - it has only one exit,
1116    - loop header is not the exit edge,
1117    - if its basic blocks and phi nodes are if convertible.  */
1118
1119 static bool
1120 if_convertible_loop_p (struct loop *loop)
1121 {
1122   edge e;
1123   edge_iterator ei;
1124   bool res = false;
1125   VEC (data_reference_p, heap) *refs;
1126   VEC (ddr_p, heap) *ddrs;
1127   VEC (loop_p, heap) *loop_nest;
1128
1129   /* Handle only innermost loop.  */
1130   if (!loop || loop->inner)
1131     {
1132       if (dump_file && (dump_flags & TDF_DETAILS))
1133         fprintf (dump_file, "not innermost loop\n");
1134       return false;
1135     }
1136
1137   /* If only one block, no need for if-conversion.  */
1138   if (loop->num_nodes <= 2)
1139     {
1140       if (dump_file && (dump_flags & TDF_DETAILS))
1141         fprintf (dump_file, "less than 2 basic blocks\n");
1142       return false;
1143     }
1144
1145   /* More than one loop exit is too much to handle.  */
1146   if (!single_exit (loop))
1147     {
1148       if (dump_file && (dump_flags & TDF_DETAILS))
1149         fprintf (dump_file, "multiple exits\n");
1150       return false;
1151     }
1152
1153   /* If one of the loop header's edge is an exit edge then do not
1154      apply if-conversion.  */
1155   FOR_EACH_EDGE (e, ei, loop->header->succs)
1156     if (loop_exit_edge_p (loop, e))
1157       return false;
1158
1159   refs = VEC_alloc (data_reference_p, heap, 5);
1160   ddrs = VEC_alloc (ddr_p, heap, 25);
1161   loop_nest = VEC_alloc (loop_p, heap, 3);
1162   res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs);
1163
1164   if (flag_tree_loop_if_convert_stores)
1165     {
1166       data_reference_p dr;
1167       unsigned int i;
1168
1169       for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
1170         free (dr->aux);
1171     }
1172
1173   VEC_free (loop_p, heap, loop_nest);
1174   free_data_refs (refs);
1175   free_dependence_relations (ddrs);
1176   return res;
1177 }
1178
1179 /* Basic block BB has two predecessors.  Using predecessor's bb
1180    predicate, set an appropriate condition COND for the PHI node
1181    replacement.  Return the true block whose phi arguments are
1182    selected when cond is true.  LOOP is the loop containing the
1183    if-converted region, GSI is the place to insert the code for the
1184    if-conversion.  */
1185
1186 static basic_block
1187 find_phi_replacement_condition (struct loop *loop,
1188                                 basic_block bb, tree *cond,
1189                                 gimple_stmt_iterator *gsi)
1190 {
1191   edge first_edge, second_edge;
1192   tree tmp_cond;
1193
1194   gcc_assert (EDGE_COUNT (bb->preds) == 2);
1195   first_edge = EDGE_PRED (bb, 0);
1196   second_edge = EDGE_PRED (bb, 1);
1197
1198   /* Use condition based on following criteria:
1199      1)
1200        S1: x = !c ? a : b;
1201
1202        S2: x = c ? b : a;
1203
1204        S2 is preferred over S1. Make 'b' first_bb and use its condition.
1205
1206      2) Do not make loop header first_bb.
1207
1208      3)
1209        S1: x = !(c == d)? a : b;
1210
1211        S21: t1 = c == d;
1212        S22: x = t1 ? b : a;
1213
1214        S3: x = (c == d) ? b : a;
1215
1216        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
1217        its condition.
1218
1219      4) If  pred B is dominated by pred A then use pred B's condition.
1220         See PR23115.  */
1221
1222   /* Select condition that is not TRUTH_NOT_EXPR.  */
1223   tmp_cond = bb_predicate (first_edge->src);
1224   gcc_assert (tmp_cond);
1225
1226   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
1227     {
1228       edge tmp_edge;
1229
1230       tmp_edge = first_edge;
1231       first_edge = second_edge;
1232       second_edge = tmp_edge;
1233     }
1234
1235   /* Check if FIRST_BB is loop header or not and make sure that
1236      FIRST_BB does not dominate SECOND_BB.  */
1237   if (first_edge->src == loop->header
1238       || dominated_by_p (CDI_DOMINATORS,
1239                          second_edge->src, first_edge->src))
1240     {
1241       *cond = bb_predicate (second_edge->src);
1242
1243       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
1244         *cond = TREE_OPERAND (*cond, 0);
1245       else
1246         /* Select non loop header bb.  */
1247         first_edge = second_edge;
1248     }
1249   else
1250     *cond = bb_predicate (first_edge->src);
1251
1252   /* Gimplify the condition to a valid cond-expr conditonal operand.  */
1253   *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond),
1254                                       is_gimple_condexpr, NULL_TREE,
1255                                       true, GSI_SAME_STMT);
1256
1257   return first_edge->src;
1258 }
1259
1260 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1261    This routine does not handle PHI nodes with more than two
1262    arguments.
1263
1264    For example,
1265      S1: A = PHI <x1(1), x2(5)>
1266    is converted into,
1267      S2: A = cond ? x1 : x2;
1268
1269    The generated code is inserted at GSI that points to the top of
1270    basic block's statement list.  When COND is true, phi arg from
1271    TRUE_BB is selected.  */
1272
1273 static void
1274 predicate_scalar_phi (gimple phi, tree cond,
1275                       basic_block true_bb,
1276                       gimple_stmt_iterator *gsi)
1277 {
1278   gimple new_stmt;
1279   basic_block bb;
1280   tree rhs, res, arg, scev;
1281
1282   gcc_assert (gimple_code (phi) == GIMPLE_PHI
1283               && gimple_phi_num_args (phi) == 2);
1284
1285   res = gimple_phi_result (phi);
1286   /* Do not handle virtual phi nodes.  */
1287   if (!is_gimple_reg (SSA_NAME_VAR (res)))
1288     return;
1289
1290   bb = gimple_bb (phi);
1291
1292   if ((arg = degenerate_phi_result (phi))
1293       || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1294                                             res))
1295           && !chrec_contains_undetermined (scev)
1296           && scev != res
1297           && (arg = gimple_phi_arg_def (phi, 0))))
1298     rhs = arg;
1299   else
1300     {
1301       tree arg_0, arg_1;
1302       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
1303       if (EDGE_PRED (bb, 1)->src == true_bb)
1304         {
1305           arg_0 = gimple_phi_arg_def (phi, 1);
1306           arg_1 = gimple_phi_arg_def (phi, 0);
1307         }
1308       else
1309         {
1310           arg_0 = gimple_phi_arg_def (phi, 0);
1311           arg_1 = gimple_phi_arg_def (phi, 1);
1312         }
1313
1314       gcc_checking_assert (bb == bb->loop_father->header
1315                            || bb_postdominates_preds (bb));
1316
1317       /* Build new RHS using selected condition and arguments.  */
1318       rhs = build3 (COND_EXPR, TREE_TYPE (res),
1319                     unshare_expr (cond), arg_0, arg_1);
1320     }
1321
1322   new_stmt = gimple_build_assign (res, rhs);
1323   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
1324   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1325   update_stmt (new_stmt);
1326
1327   if (dump_file && (dump_flags & TDF_DETAILS))
1328     {
1329       fprintf (dump_file, "new phi replacement stmt\n");
1330       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1331     }
1332 }
1333
1334 /* Replaces in LOOP all the scalar phi nodes other than those in the
1335    LOOP->header block with conditional modify expressions.  */
1336
1337 static void
1338 predicate_all_scalar_phis (struct loop *loop)
1339 {
1340   basic_block bb;
1341   unsigned int orig_loop_num_nodes = loop->num_nodes;
1342   unsigned int i;
1343
1344   for (i = 1; i < orig_loop_num_nodes; i++)
1345     {
1346       gimple phi;
1347       tree cond = NULL_TREE;
1348       gimple_stmt_iterator gsi, phi_gsi;
1349       basic_block true_bb = NULL;
1350       bb = ifc_bbs[i];
1351
1352       if (bb == loop->header)
1353         continue;
1354
1355       phi_gsi = gsi_start_phis (bb);
1356       if (gsi_end_p (phi_gsi))
1357         continue;
1358
1359       /* BB has two predecessors.  Using predecessor's aux field, set
1360          appropriate condition for the PHI node replacement.  */
1361       gsi = gsi_after_labels (bb);
1362       true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
1363
1364       while (!gsi_end_p (phi_gsi))
1365         {
1366           phi = gsi_stmt (phi_gsi);
1367           predicate_scalar_phi (phi, cond, true_bb, &gsi);
1368           release_phi_node (phi);
1369           gsi_next (&phi_gsi);
1370         }
1371
1372       set_phi_nodes (bb, NULL);
1373     }
1374 }
1375
1376 /* Insert in each basic block of LOOP the statements produced by the
1377    gimplification of the predicates.  */
1378
1379 static void
1380 insert_gimplified_predicates (loop_p loop)
1381 {
1382   unsigned int i;
1383
1384   for (i = 0; i < loop->num_nodes; i++)
1385     {
1386       basic_block bb = ifc_bbs[i];
1387       gimple_seq stmts;
1388
1389       if (!is_predicated (bb))
1390         {
1391           /* Do not insert statements for a basic block that is not
1392              predicated.  Also make sure that the predicate of the
1393              basic block is set to true.  */
1394           reset_bb_predicate (bb);
1395           continue;
1396         }
1397
1398       stmts = bb_predicate_gimplified_stmts (bb);
1399       if (stmts)
1400         {
1401           if (flag_tree_loop_if_convert_stores)
1402             {
1403               /* Insert the predicate of the BB just after the label,
1404                  as the if-conversion of memory writes will use this
1405                  predicate.  */
1406               gimple_stmt_iterator gsi = gsi_after_labels (bb);
1407               gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1408             }
1409           else
1410             {
1411               /* Insert the predicate of the BB at the end of the BB
1412                  as this would reduce the register pressure: the only
1413                  use of this predicate will be in successor BBs.  */
1414               gimple_stmt_iterator gsi = gsi_last_bb (bb);
1415
1416               if (gsi_end_p (gsi)
1417                   || stmt_ends_bb_p (gsi_stmt (gsi)))
1418                 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1419               else
1420                 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1421             }
1422
1423           /* Once the sequence is code generated, set it to NULL.  */
1424           set_bb_predicate_gimplified_stmts (bb, NULL);
1425         }
1426     }
1427 }
1428
1429 /* Predicate each write to memory in LOOP.
1430
1431    This function transforms control flow constructs containing memory
1432    writes of the form:
1433
1434    | for (i = 0; i < N; i++)
1435    |   if (cond)
1436    |     A[i] = expr;
1437
1438    into the following form that does not contain control flow:
1439
1440    | for (i = 0; i < N; i++)
1441    |   A[i] = cond ? expr : A[i];
1442
1443    The original CFG looks like this:
1444
1445    | bb_0
1446    |   i = 0
1447    | end_bb_0
1448    |
1449    | bb_1
1450    |   if (i < N) goto bb_5 else goto bb_2
1451    | end_bb_1
1452    |
1453    | bb_2
1454    |   cond = some_computation;
1455    |   if (cond) goto bb_3 else goto bb_4
1456    | end_bb_2
1457    |
1458    | bb_3
1459    |   A[i] = expr;
1460    |   goto bb_4
1461    | end_bb_3
1462    |
1463    | bb_4
1464    |   goto bb_1
1465    | end_bb_4
1466
1467    insert_gimplified_predicates inserts the computation of the COND
1468    expression at the beginning of the destination basic block:
1469
1470    | bb_0
1471    |   i = 0
1472    | end_bb_0
1473    |
1474    | bb_1
1475    |   if (i < N) goto bb_5 else goto bb_2
1476    | end_bb_1
1477    |
1478    | bb_2
1479    |   cond = some_computation;
1480    |   if (cond) goto bb_3 else goto bb_4
1481    | end_bb_2
1482    |
1483    | bb_3
1484    |   cond = some_computation;
1485    |   A[i] = expr;
1486    |   goto bb_4
1487    | end_bb_3
1488    |
1489    | bb_4
1490    |   goto bb_1
1491    | end_bb_4
1492
1493    predicate_mem_writes is then predicating the memory write as follows:
1494
1495    | bb_0
1496    |   i = 0
1497    | end_bb_0
1498    |
1499    | bb_1
1500    |   if (i < N) goto bb_5 else goto bb_2
1501    | end_bb_1
1502    |
1503    | bb_2
1504    |   if (cond) goto bb_3 else goto bb_4
1505    | end_bb_2
1506    |
1507    | bb_3
1508    |   cond = some_computation;
1509    |   A[i] = cond ? expr : A[i];
1510    |   goto bb_4
1511    | end_bb_3
1512    |
1513    | bb_4
1514    |   goto bb_1
1515    | end_bb_4
1516
1517    and finally combine_blocks removes the basic block boundaries making
1518    the loop vectorizable:
1519
1520    | bb_0
1521    |   i = 0
1522    |   if (i < N) goto bb_5 else goto bb_1
1523    | end_bb_0
1524    |
1525    | bb_1
1526    |   cond = some_computation;
1527    |   A[i] = cond ? expr : A[i];
1528    |   if (i < N) goto bb_5 else goto bb_4
1529    | end_bb_1
1530    |
1531    | bb_4
1532    |   goto bb_1
1533    | end_bb_4
1534 */
1535
1536 static void
1537 predicate_mem_writes (loop_p loop)
1538 {
1539   unsigned int i, orig_loop_num_nodes = loop->num_nodes;
1540
1541   for (i = 1; i < orig_loop_num_nodes; i++)
1542     {
1543       gimple_stmt_iterator gsi;
1544       basic_block bb = ifc_bbs[i];
1545       tree cond = bb_predicate (bb);
1546       bool swap;
1547       gimple stmt;
1548
1549       if (is_true_predicate (cond))
1550         continue;
1551
1552       swap = false;
1553       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1554         {
1555           swap = true;
1556           cond = TREE_OPERAND (cond, 0);
1557         }
1558
1559       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1560         if ((stmt = gsi_stmt (gsi))
1561             && gimple_assign_single_p (stmt)
1562             && gimple_vdef (stmt))
1563           {
1564             tree lhs = gimple_assign_lhs (stmt);
1565             tree rhs = gimple_assign_rhs1 (stmt);
1566             tree type = TREE_TYPE (lhs);
1567
1568             lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
1569             rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
1570             if (swap)
1571               {
1572                 tree tem = lhs;
1573                 lhs = rhs;
1574                 rhs = tem;
1575               }
1576             cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
1577                                                is_gimple_condexpr, NULL_TREE,
1578                                                true, GSI_SAME_STMT);
1579             rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs);
1580             gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
1581             update_stmt (stmt);
1582           }
1583     }
1584 }
1585
1586 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1587    other than the exit and latch of the LOOP.  Also resets the
1588    GIMPLE_DEBUG information.  */
1589
1590 static void
1591 remove_conditions_and_labels (loop_p loop)
1592 {
1593   gimple_stmt_iterator gsi;
1594   unsigned int i;
1595
1596   for (i = 0; i < loop->num_nodes; i++)
1597     {
1598       basic_block bb = ifc_bbs[i];
1599
1600       if (bb_with_exit_edge_p (loop, bb)
1601         || bb == loop->latch)
1602       continue;
1603
1604       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1605         switch (gimple_code (gsi_stmt (gsi)))
1606           {
1607           case GIMPLE_COND:
1608           case GIMPLE_LABEL:
1609             gsi_remove (&gsi, true);
1610             break;
1611
1612           case GIMPLE_DEBUG:
1613             /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
1614             if (gimple_debug_bind_p (gsi_stmt (gsi)))
1615               {
1616                 gimple_debug_bind_reset_value (gsi_stmt (gsi));
1617                 update_stmt (gsi_stmt (gsi));
1618               }
1619             gsi_next (&gsi);
1620             break;
1621
1622           default:
1623             gsi_next (&gsi);
1624           }
1625     }
1626 }
1627
1628 /* Combine all the basic blocks from LOOP into one or two super basic
1629    blocks.  Replace PHI nodes with conditional modify expressions.  */
1630
1631 static void
1632 combine_blocks (struct loop *loop)
1633 {
1634   basic_block bb, exit_bb, merge_target_bb;
1635   unsigned int orig_loop_num_nodes = loop->num_nodes;
1636   unsigned int i;
1637   edge e;
1638   edge_iterator ei;
1639
1640   remove_conditions_and_labels (loop);
1641   insert_gimplified_predicates (loop);
1642   predicate_all_scalar_phis (loop);
1643
1644   if (flag_tree_loop_if_convert_stores)
1645     predicate_mem_writes (loop);
1646
1647   /* Merge basic blocks: first remove all the edges in the loop,
1648      except for those from the exit block.  */
1649   exit_bb = NULL;
1650   for (i = 0; i < orig_loop_num_nodes; i++)
1651     {
1652       bb = ifc_bbs[i];
1653       free_bb_predicate (bb);
1654       if (bb_with_exit_edge_p (loop, bb))
1655         {
1656           exit_bb = bb;
1657           break;
1658         }
1659     }
1660   gcc_assert (exit_bb != loop->latch);
1661
1662   for (i = 1; i < orig_loop_num_nodes; i++)
1663     {
1664       bb = ifc_bbs[i];
1665
1666       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
1667         {
1668           if (e->src == exit_bb)
1669             ei_next (&ei);
1670           else
1671             remove_edge (e);
1672         }
1673     }
1674
1675   if (exit_bb != NULL)
1676     {
1677       if (exit_bb != loop->header)
1678         {
1679           /* Connect this node to loop header.  */
1680           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
1681           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
1682         }
1683
1684       /* Redirect non-exit edges to loop->latch.  */
1685       FOR_EACH_EDGE (e, ei, exit_bb->succs)
1686         {
1687           if (!loop_exit_edge_p (loop, e))
1688             redirect_edge_and_branch (e, loop->latch);
1689         }
1690       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
1691     }
1692   else
1693     {
1694       /* If the loop does not have an exit, reconnect header and latch.  */
1695       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1696       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1697     }
1698
1699   merge_target_bb = loop->header;
1700   for (i = 1; i < orig_loop_num_nodes; i++)
1701     {
1702       gimple_stmt_iterator gsi;
1703       gimple_stmt_iterator last;
1704
1705       bb = ifc_bbs[i];
1706
1707       if (bb == exit_bb || bb == loop->latch)
1708         continue;
1709
1710       /* Make stmts member of loop->header.  */
1711       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1712         gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1713
1714       /* Update stmt list.  */
1715       last = gsi_last_bb (merge_target_bb);
1716       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1717       set_bb_seq (bb, NULL);
1718
1719       delete_basic_block (bb);
1720     }
1721
1722   /* If possible, merge loop header to the block with the exit edge.
1723      This reduces the number of basic blocks to two, to please the
1724      vectorizer that handles only loops with two nodes.  */
1725   if (exit_bb
1726       && exit_bb != loop->header
1727       && can_merge_blocks_p (loop->header, exit_bb))
1728     merge_blocks (loop->header, exit_bb);
1729
1730   free (ifc_bbs);
1731   ifc_bbs = NULL;
1732 }
1733
1734 /* If-convert LOOP when it is legal.  For the moment this pass has no
1735    profitability analysis.  Returns true when something changed.  */
1736
1737 static bool
1738 tree_if_conversion (struct loop *loop)
1739 {
1740   bool changed = false;
1741   ifc_bbs = NULL;
1742
1743   if (!if_convertible_loop_p (loop)
1744       || !dbg_cnt (if_conversion_tree))
1745     goto cleanup;
1746
1747   /* Now all statements are if-convertible.  Combine all the basic
1748      blocks into one huge basic block doing the if-conversion
1749      on-the-fly.  */
1750   combine_blocks (loop);
1751
1752   if (flag_tree_loop_if_convert_stores)
1753     mark_sym_for_renaming (gimple_vop (cfun));
1754
1755   changed = true;
1756
1757  cleanup:
1758   if (ifc_bbs)
1759     {
1760       unsigned int i;
1761
1762       for (i = 0; i < loop->num_nodes; i++)
1763         free_bb_predicate (ifc_bbs[i]);
1764
1765       free (ifc_bbs);
1766       ifc_bbs = NULL;
1767     }
1768
1769   return changed;
1770 }
1771
1772 /* Tree if-conversion pass management.  */
1773
1774 static unsigned int
1775 main_tree_if_conversion (void)
1776 {
1777   loop_iterator li;
1778   struct loop *loop;
1779   bool changed = false;
1780   unsigned todo = 0;
1781
1782   if (number_of_loops () <= 1)
1783     return 0;
1784
1785   FOR_EACH_LOOP (li, loop, 0)
1786     changed |= tree_if_conversion (loop);
1787
1788   if (changed)
1789     todo |= TODO_cleanup_cfg;
1790
1791   if (changed && flag_tree_loop_if_convert_stores)
1792     todo |= TODO_update_ssa_only_virtuals;
1793
1794   free_dominance_info (CDI_POST_DOMINATORS);
1795
1796   return todo;
1797 }
1798
1799 /* Returns true when the if-conversion pass is enabled.  */
1800
1801 static bool
1802 gate_tree_if_conversion (void)
1803 {
1804   return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0)
1805           || flag_tree_loop_if_convert == 1
1806           || flag_tree_loop_if_convert_stores == 1);
1807 }
1808
1809 struct gimple_opt_pass pass_if_conversion =
1810 {
1811  {
1812   GIMPLE_PASS,
1813   "ifcvt",                              /* name */
1814   gate_tree_if_conversion,              /* gate */
1815   main_tree_if_conversion,              /* execute */
1816   NULL,                                 /* sub */
1817   NULL,                                 /* next */
1818   0,                                    /* static_pass_number */
1819   TV_NONE,                              /* tv_id */
1820   PROP_cfg | PROP_ssa,                  /* properties_required */
1821   0,                                    /* properties_provided */
1822   0,                                    /* properties_destroyed */
1823   0,                                    /* todo_flags_start */
1824   TODO_verify_stmts | TODO_verify_flow
1825                                         /* todo_flags_finish */
1826  }
1827 };