OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-if-conv.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* 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
      gimple stmt;
1547
 
1548
      if (is_true_predicate (cond))
1549
        continue;
1550
 
1551
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1552
        if ((stmt = gsi_stmt (gsi))
1553
            && gimple_assign_single_p (stmt)
1554
            && gimple_vdef (stmt))
1555
          {
1556
            tree lhs = gimple_assign_lhs (stmt);
1557
            tree rhs = gimple_assign_rhs1 (stmt);
1558
            tree type = TREE_TYPE (lhs);
1559
 
1560
            lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
1561
            rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
1562
            rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs);
1563
            gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
1564
            update_stmt (stmt);
1565
          }
1566
    }
1567
}
1568
 
1569
/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1570
   other than the exit and latch of the LOOP.  Also resets the
1571
   GIMPLE_DEBUG information.  */
1572
 
1573
static void
1574
remove_conditions_and_labels (loop_p loop)
1575
{
1576
  gimple_stmt_iterator gsi;
1577
  unsigned int i;
1578
 
1579
  for (i = 0; i < loop->num_nodes; i++)
1580
    {
1581
      basic_block bb = ifc_bbs[i];
1582
 
1583
      if (bb_with_exit_edge_p (loop, bb)
1584
        || bb == loop->latch)
1585
      continue;
1586
 
1587
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1588
        switch (gimple_code (gsi_stmt (gsi)))
1589
          {
1590
          case GIMPLE_COND:
1591
          case GIMPLE_LABEL:
1592
            gsi_remove (&gsi, true);
1593
            break;
1594
 
1595
          case GIMPLE_DEBUG:
1596
            /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
1597
            if (gimple_debug_bind_p (gsi_stmt (gsi)))
1598
              {
1599
                gimple_debug_bind_reset_value (gsi_stmt (gsi));
1600
                update_stmt (gsi_stmt (gsi));
1601
              }
1602
            gsi_next (&gsi);
1603
            break;
1604
 
1605
          default:
1606
            gsi_next (&gsi);
1607
          }
1608
    }
1609
}
1610
 
1611
/* Combine all the basic blocks from LOOP into one or two super basic
1612
   blocks.  Replace PHI nodes with conditional modify expressions.  */
1613
 
1614
static void
1615
combine_blocks (struct loop *loop)
1616
{
1617
  basic_block bb, exit_bb, merge_target_bb;
1618
  unsigned int orig_loop_num_nodes = loop->num_nodes;
1619
  unsigned int i;
1620
  edge e;
1621
  edge_iterator ei;
1622
 
1623
  remove_conditions_and_labels (loop);
1624
  insert_gimplified_predicates (loop);
1625
  predicate_all_scalar_phis (loop);
1626
 
1627
  if (flag_tree_loop_if_convert_stores)
1628
    predicate_mem_writes (loop);
1629
 
1630
  /* Merge basic blocks: first remove all the edges in the loop,
1631
     except for those from the exit block.  */
1632
  exit_bb = NULL;
1633
  for (i = 0; i < orig_loop_num_nodes; i++)
1634
    {
1635
      bb = ifc_bbs[i];
1636
      free_bb_predicate (bb);
1637
      if (bb_with_exit_edge_p (loop, bb))
1638
        {
1639
          exit_bb = bb;
1640
          break;
1641
        }
1642
    }
1643
  gcc_assert (exit_bb != loop->latch);
1644
 
1645
  for (i = 1; i < orig_loop_num_nodes; i++)
1646
    {
1647
      bb = ifc_bbs[i];
1648
 
1649
      for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
1650
        {
1651
          if (e->src == exit_bb)
1652
            ei_next (&ei);
1653
          else
1654
            remove_edge (e);
1655
        }
1656
    }
1657
 
1658
  if (exit_bb != NULL)
1659
    {
1660
      if (exit_bb != loop->header)
1661
        {
1662
          /* Connect this node to loop header.  */
1663
          make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
1664
          set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
1665
        }
1666
 
1667
      /* Redirect non-exit edges to loop->latch.  */
1668
      FOR_EACH_EDGE (e, ei, exit_bb->succs)
1669
        {
1670
          if (!loop_exit_edge_p (loop, e))
1671
            redirect_edge_and_branch (e, loop->latch);
1672
        }
1673
      set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
1674
    }
1675
  else
1676
    {
1677
      /* If the loop does not have an exit, reconnect header and latch.  */
1678
      make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1679
      set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1680
    }
1681
 
1682
  merge_target_bb = loop->header;
1683
  for (i = 1; i < orig_loop_num_nodes; i++)
1684
    {
1685
      gimple_stmt_iterator gsi;
1686
      gimple_stmt_iterator last;
1687
 
1688
      bb = ifc_bbs[i];
1689
 
1690
      if (bb == exit_bb || bb == loop->latch)
1691
        continue;
1692
 
1693
      /* Make stmts member of loop->header.  */
1694
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1695
        gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1696
 
1697
      /* Update stmt list.  */
1698
      last = gsi_last_bb (merge_target_bb);
1699
      gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1700
      set_bb_seq (bb, NULL);
1701
 
1702
      delete_basic_block (bb);
1703
    }
1704
 
1705
  /* If possible, merge loop header to the block with the exit edge.
1706
     This reduces the number of basic blocks to two, to please the
1707
     vectorizer that handles only loops with two nodes.  */
1708
  if (exit_bb
1709
      && exit_bb != loop->header
1710
      && can_merge_blocks_p (loop->header, exit_bb))
1711
    merge_blocks (loop->header, exit_bb);
1712
 
1713
  free (ifc_bbs);
1714
  ifc_bbs = NULL;
1715
}
1716
 
1717
/* If-convert LOOP when it is legal.  For the moment this pass has no
1718
   profitability analysis.  Returns true when something changed.  */
1719
 
1720
static bool
1721
tree_if_conversion (struct loop *loop)
1722
{
1723
  bool changed = false;
1724
  ifc_bbs = NULL;
1725
 
1726
  if (!if_convertible_loop_p (loop)
1727
      || !dbg_cnt (if_conversion_tree))
1728
    goto cleanup;
1729
 
1730
  /* Now all statements are if-convertible.  Combine all the basic
1731
     blocks into one huge basic block doing the if-conversion
1732
     on-the-fly.  */
1733
  combine_blocks (loop);
1734
 
1735
  if (flag_tree_loop_if_convert_stores)
1736
    mark_sym_for_renaming (gimple_vop (cfun));
1737
 
1738
  changed = true;
1739
 
1740
 cleanup:
1741
  if (ifc_bbs)
1742
    {
1743
      unsigned int i;
1744
 
1745
      for (i = 0; i < loop->num_nodes; i++)
1746
        free_bb_predicate (ifc_bbs[i]);
1747
 
1748
      free (ifc_bbs);
1749
      ifc_bbs = NULL;
1750
    }
1751
 
1752
  return changed;
1753
}
1754
 
1755
/* Tree if-conversion pass management.  */
1756
 
1757
static unsigned int
1758
main_tree_if_conversion (void)
1759
{
1760
  loop_iterator li;
1761
  struct loop *loop;
1762
  bool changed = false;
1763
  unsigned todo = 0;
1764
 
1765
  if (number_of_loops () <= 1)
1766
    return 0;
1767
 
1768
  FOR_EACH_LOOP (li, loop, 0)
1769
    changed |= tree_if_conversion (loop);
1770
 
1771
  if (changed)
1772
    todo |= TODO_cleanup_cfg;
1773
 
1774
  if (changed && flag_tree_loop_if_convert_stores)
1775
    todo |= TODO_update_ssa_only_virtuals;
1776
 
1777
  free_dominance_info (CDI_POST_DOMINATORS);
1778
 
1779
  return todo;
1780
}
1781
 
1782
/* Returns true when the if-conversion pass is enabled.  */
1783
 
1784
static bool
1785
gate_tree_if_conversion (void)
1786
{
1787
  return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0)
1788
          || flag_tree_loop_if_convert == 1
1789
          || flag_tree_loop_if_convert_stores == 1);
1790
}
1791
 
1792
struct gimple_opt_pass pass_if_conversion =
1793
{
1794
 {
1795
  GIMPLE_PASS,
1796
  "ifcvt",                              /* name */
1797
  gate_tree_if_conversion,              /* gate */
1798
  main_tree_if_conversion,              /* execute */
1799
  NULL,                                 /* sub */
1800
  NULL,                                 /* next */
1801
  0,                                     /* static_pass_number */
1802
  TV_NONE,                              /* tv_id */
1803
  PROP_cfg | PROP_ssa,                  /* properties_required */
1804
  0,                                     /* properties_provided */
1805
  0,                                     /* properties_destroyed */
1806
  0,                                     /* todo_flags_start */
1807
  TODO_verify_stmts | TODO_verify_flow
1808
                                        /* todo_flags_finish */
1809
 }
1810
};

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.