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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [tree-if-conv.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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