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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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