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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [tree-ssa-phiopt.c] - Blame information for rev 12

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 12 jlechner
/* Optimization of PHI nodes by converting them into straightline code.
2
   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify it
7
under the terms of the GNU General Public License as published by the
8
Free Software Foundation; either version 2, or (at your option) any
9
later version.
10
 
11
GCC is distributed in the hope that it will be useful, but WITHOUT
12
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING.  If not, write to the Free
18
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19
02110-1301, USA.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "ggc.h"
26
#include "tree.h"
27
#include "rtl.h"
28
#include "flags.h"
29
#include "tm_p.h"
30
#include "basic-block.h"
31
#include "timevar.h"
32
#include "diagnostic.h"
33
#include "tree-flow.h"
34
#include "tree-pass.h"
35
#include "tree-dump.h"
36
#include "langhooks.h"
37
 
38
static void tree_ssa_phiopt (void);
39
static bool conditional_replacement (basic_block, basic_block,
40
                                     edge, edge, tree, tree, tree);
41
static bool value_replacement (basic_block, basic_block,
42
                               edge, edge, tree, tree, tree);
43
static bool minmax_replacement (basic_block, basic_block,
44
                                edge, edge, tree, tree, tree);
45
static bool abs_replacement (basic_block, basic_block,
46
                             edge, edge, tree, tree, tree);
47
static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
48
static basic_block *blocks_in_phiopt_order (void);
49
 
50
/* This pass tries to replaces an if-then-else block with an
51
   assignment.  We have four kinds of transformations.  Some of these
52
   transformations are also performed by the ifcvt RTL optimizer.
53
 
54
   Conditional Replacement
55
   -----------------------
56
 
57
   This transformation, implemented in conditional_replacement,
58
   replaces
59
 
60
     bb0:
61
      if (cond) goto bb2; else goto bb1;
62
     bb1:
63
     bb2:
64
      x = PHI <0 (bb1), 1 (bb0), ...>;
65
 
66
   with
67
 
68
     bb0:
69
      x' = cond;
70
      goto bb2;
71
     bb2:
72
      x = PHI <x' (bb0), ...>;
73
 
74
   We remove bb1 as it becomes unreachable.  This occurs often due to
75
   gimplification of conditionals.
76
 
77
   Value Replacement
78
   -----------------
79
 
80
   This transformation, implemented in value_replacement, replaces
81
 
82
     bb0:
83
       if (a != b) goto bb2; else goto bb1;
84
     bb1:
85
     bb2:
86
       x = PHI <a (bb1), b (bb0), ...>;
87
 
88
   with
89
 
90
     bb0:
91
     bb2:
92
       x = PHI <b (bb0), ...>;
93
 
94
   This opportunity can sometimes occur as a result of other
95
   optimizations.
96
 
97
   ABS Replacement
98
   ---------------
99
 
100
   This transformation, implemented in abs_replacement, replaces
101
 
102
     bb0:
103
       if (a >= 0) goto bb2; else goto bb1;
104
     bb1:
105
       x = -a;
106
     bb2:
107
       x = PHI <x (bb1), a (bb0), ...>;
108
 
109
   with
110
 
111
     bb0:
112
       x' = ABS_EXPR< a >;
113
     bb2:
114
       x = PHI <x' (bb0), ...>;
115
 
116
   MIN/MAX Replacement
117
   -------------------
118
 
119
   This transformation, minmax_replacement replaces
120
 
121
     bb0:
122
       if (a <= b) goto bb2; else goto bb1;
123
     bb1:
124
     bb2:
125
       x = PHI <b (bb1), a (bb0), ...>;
126
 
127
   with
128
 
129
     bb0:
130
       x' = MIN_EXPR (a, b)
131
     bb2:
132
       x = PHI <x' (bb0), ...>;
133
 
134
   A similar transformation is done for MAX_EXPR.  */
135
 
136
static void
137
tree_ssa_phiopt (void)
138
{
139
  basic_block bb;
140
  basic_block *bb_order;
141
  unsigned n, i;
142
 
143
  /* Search every basic block for COND_EXPR we may be able to optimize.
144
 
145
     We walk the blocks in order that guarantees that a block with
146
     a single predecessor is processed before the predecessor.
147
     This ensures that we collapse inner ifs before visiting the
148
     outer ones, and also that we do not try to visit a removed
149
     block.  */
150
  bb_order = blocks_in_phiopt_order ();
151
  n = n_basic_blocks;
152
 
153
  for (i = 0; i < n; i++)
154
    {
155
      tree cond_expr;
156
      tree phi;
157
      basic_block bb1, bb2;
158
      edge e1, e2;
159
      tree arg0, arg1;
160
 
161
      bb = bb_order[i];
162
 
163
      cond_expr = last_stmt (bb);
164
      /* Check to see if the last statement is a COND_EXPR.  */
165
      if (!cond_expr
166
          || TREE_CODE (cond_expr) != COND_EXPR)
167
        continue;
168
 
169
      e1 = EDGE_SUCC (bb, 0);
170
      bb1 = e1->dest;
171
      e2 = EDGE_SUCC (bb, 1);
172
      bb2 = e2->dest;
173
 
174
      /* We cannot do the optimization on abnormal edges.  */
175
      if ((e1->flags & EDGE_ABNORMAL) != 0
176
          || (e2->flags & EDGE_ABNORMAL) != 0)
177
       continue;
178
 
179
      /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
180
      if (EDGE_COUNT (bb1->succs) == 0
181
          || bb2 == NULL
182
          || EDGE_COUNT (bb2->succs) == 0)
183
        continue;
184
 
185
      /* Find the bb which is the fall through to the other.  */
186
      if (EDGE_SUCC (bb1, 0)->dest == bb2)
187
        ;
188
      else if (EDGE_SUCC (bb2, 0)->dest == bb1)
189
        {
190
          basic_block bb_tmp = bb1;
191
          edge e_tmp = e1;
192
          bb1 = bb2;
193
          bb2 = bb_tmp;
194
          e1 = e2;
195
          e2 = e_tmp;
196
        }
197
      else
198
        continue;
199
 
200
      e1 = EDGE_SUCC (bb1, 0);
201
 
202
      /* Make sure that bb1 is just a fall through.  */
203
      if (!single_succ_p (bb1)
204
          || (e1->flags & EDGE_FALLTHRU) == 0)
205
        continue;
206
 
207
      /* Also make sure that bb1 only have one predecessor and that it
208
         is bb.  */
209
      if (!single_pred_p (bb1)
210
          || single_pred (bb1) != bb)
211
        continue;
212
 
213
      phi = phi_nodes (bb2);
214
 
215
      /* Check to make sure that there is only one PHI node.
216
         TODO: we could do it with more than one iff the other PHI nodes
217
         have the same elements for these two edges.  */
218
      if (!phi || PHI_CHAIN (phi) != NULL)
219
        continue;
220
 
221
      arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
222
      arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
223
 
224
      /* Something is wrong if we cannot find the arguments in the PHI
225
         node.  */
226
      gcc_assert (arg0 != NULL && arg1 != NULL);
227
 
228
      /* Do the replacement of conditional if it can be done.  */
229
      if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
230
        ;
231
      else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
232
        ;
233
      else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
234
        ;
235
      else
236
        minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1);
237
    }
238
 
239
  free (bb_order);
240
}
241
 
242
/* Returns the list of basic blocks in the function in an order that guarantees
243
   that if a block X has just a single predecessor Y, then Y is after X in the
244
   ordering.  */
245
 
246
static basic_block *
247
blocks_in_phiopt_order (void)
248
{
249
  basic_block x, y;
250
  basic_block *order = xmalloc (sizeof (basic_block) * n_basic_blocks);
251
  unsigned n = n_basic_blocks, np, i;
252
  sbitmap visited = sbitmap_alloc (last_basic_block + 2);
253
 
254
#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
255
#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
256
 
257
  sbitmap_zero (visited);
258
 
259
  MARK_VISITED (ENTRY_BLOCK_PTR);
260
  FOR_EACH_BB (x)
261
    {
262
      if (VISITED_P (x))
263
        continue;
264
 
265
      /* Walk the predecessors of x as long as they have precisely one
266
         predecessor and add them to the list, so that they get stored
267
         after x.  */
268
      for (y = x, np = 1;
269
           single_pred_p (y) && !VISITED_P (single_pred (y));
270
           y = single_pred (y))
271
        np++;
272
      for (y = x, i = n - np;
273
           single_pred_p (y) && !VISITED_P (single_pred (y));
274
           y = single_pred (y), i++)
275
        {
276
          order[i] = y;
277
          MARK_VISITED (y);
278
        }
279
      order[i] = y;
280
      MARK_VISITED (y);
281
 
282
      gcc_assert (i == n - 1);
283
      n -= np;
284
    }
285
 
286
  sbitmap_free (visited);
287
  gcc_assert (n == 0);
288
  return order;
289
 
290
#undef MARK_VISITED
291
#undef VISITED_P
292
}
293
 
294
/* Return TRUE if block BB has no executable statements, otherwise return
295
   FALSE.  */
296
bool
297
empty_block_p (basic_block bb)
298
{
299
  block_stmt_iterator bsi;
300
 
301
  /* BB must have no executable statements.  */
302
  bsi = bsi_start (bb);
303
  while (!bsi_end_p (bsi)
304
          && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
305
              || IS_EMPTY_STMT (bsi_stmt (bsi))))
306
    bsi_next (&bsi);
307
 
308
  if (!bsi_end_p (bsi))
309
    return false;
310
 
311
  return true;
312
}
313
 
314
/* Replace PHI node element whose edge is E in block BB with variable NEW.
315
   Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
316
   is known to have two edges, one of which must reach BB).  */
317
 
318
static void
319
replace_phi_edge_with_variable (basic_block cond_block,
320
                                edge e, tree phi, tree new)
321
{
322
  basic_block bb = bb_for_stmt (phi);
323
  basic_block block_to_remove;
324
  block_stmt_iterator bsi;
325
 
326
  /* Change the PHI argument to new.  */
327
  SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new);
328
 
329
  /* Remove the empty basic block.  */
330
  if (EDGE_SUCC (cond_block, 0)->dest == bb)
331
    {
332
      EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
333
      EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
334
      EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
335
      EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
336
 
337
      block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
338
    }
339
  else
340
    {
341
      EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
342
      EDGE_SUCC (cond_block, 1)->flags
343
        &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
344
      EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
345
      EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
346
 
347
      block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
348
    }
349
  delete_basic_block (block_to_remove);
350
 
351
  /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
352
  bsi = bsi_last (cond_block);
353
  bsi_remove (&bsi);
354
 
355
  if (dump_file && (dump_flags & TDF_DETAILS))
356
    fprintf (dump_file,
357
              "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
358
              cond_block->index,
359
              bb->index);
360
}
361
 
362
/*  The function conditional_replacement does the main work of doing the
363
    conditional replacement.  Return true if the replacement is done.
364
    Otherwise return false.
365
    BB is the basic block where the replacement is going to be done on.  ARG0
366
    is argument 0 from PHI.  Likewise for ARG1.  */
367
 
368
static bool
369
conditional_replacement (basic_block cond_bb, basic_block middle_bb,
370
                         edge e0, edge e1, tree phi,
371
                         tree arg0, tree arg1)
372
{
373
  tree result;
374
  tree old_result = NULL;
375
  tree new, cond;
376
  block_stmt_iterator bsi;
377
  edge true_edge, false_edge;
378
  tree new_var = NULL;
379
  tree new_var1;
380
 
381
  /* The PHI arguments have the constants 0 and 1, then convert
382
     it to the conditional.  */
383
  if ((integer_zerop (arg0) && integer_onep (arg1))
384
      || (integer_zerop (arg1) && integer_onep (arg0)))
385
    ;
386
  else
387
    return false;
388
 
389
  if (!empty_block_p (middle_bb))
390
    return false;
391
 
392
  /* If the condition is not a naked SSA_NAME and its type does not
393
     match the type of the result, then we have to create a new
394
     variable to optimize this case as it would likely create
395
     non-gimple code when the condition was converted to the
396
     result's type.  */
397
  cond = COND_EXPR_COND (last_stmt (cond_bb));
398
  result = PHI_RESULT (phi);
399
  if (TREE_CODE (cond) != SSA_NAME
400
      && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
401
    {
402
      tree tmp;
403
 
404
      if (!COMPARISON_CLASS_P (cond))
405
        return false;
406
 
407
      tmp = create_tmp_var (TREE_TYPE (cond), NULL);
408
      add_referenced_tmp_var (tmp);
409
      new_var = make_ssa_name (tmp, NULL);
410
      old_result = cond;
411
      cond = new_var;
412
    }
413
 
414
  /* If the condition was a naked SSA_NAME and the type is not the
415
     same as the type of the result, then convert the type of the
416
     condition.  */
417
  if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
418
    cond = fold_convert (TREE_TYPE (result), cond);
419
 
420
  /* We need to know which is the true edge and which is the false
421
     edge so that we know when to invert the condition below.  */
422
  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
423
 
424
  /* Insert our new statement at the end of conditional block before the
425
     COND_EXPR.  */
426
  bsi = bsi_last (cond_bb);
427
  bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
428
 
429
  if (old_result)
430
    {
431
      tree new1;
432
 
433
      new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
434
                     TREE_OPERAND (old_result, 0),
435
                     TREE_OPERAND (old_result, 1));
436
 
437
      new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
438
      SSA_NAME_DEF_STMT (new_var) = new1;
439
 
440
      bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
441
    }
442
 
443
  new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
444
 
445
 
446
  /* At this point we know we have a COND_EXPR with two successors.
447
     One successor is BB, the other successor is an empty block which
448
     falls through into BB.
449
 
450
     There is a single PHI node at the join point (BB) and its arguments
451
     are constants (0, 1).
452
 
453
     So, given the condition COND, and the two PHI arguments, we can
454
     rewrite this PHI into non-branching code:
455
 
456
       dest = (COND) or dest = COND'
457
 
458
     We use the condition as-is if the argument associated with the
459
     true edge has the value one or the argument associated with the
460
     false edge as the value zero.  Note that those conditions are not
461
     the same since only one of the outgoing edges from the COND_EXPR
462
     will directly reach BB and thus be associated with an argument.  */
463
  if ((e0 == true_edge && integer_onep (arg0))
464
      || (e0 == false_edge && integer_zerop (arg0))
465
      || (e1 == true_edge && integer_onep (arg1))
466
      || (e1 == false_edge && integer_zerop (arg1)))
467
    {
468
      new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
469
    }
470
  else
471
    {
472
      tree cond1 = invert_truthvalue (cond);
473
 
474
      cond = cond1;
475
 
476
      /* If what we get back is a conditional expression, there is no
477
          way that it can be gimple.  */
478
      if (TREE_CODE (cond) == COND_EXPR)
479
        {
480
          release_ssa_name (new_var1);
481
          return false;
482
        }
483
 
484
      /* If COND is not something we can expect to be reducible to a GIMPLE
485
         condition, return early.  */
486
      if (is_gimple_cast (cond))
487
        cond1 = TREE_OPERAND (cond, 0);
488
      if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
489
          && !is_gimple_val (TREE_OPERAND (cond1, 0)))
490
        {
491
          release_ssa_name (new_var1);
492
          return false;
493
        }
494
 
495
      /* If what we get back is not gimple try to create it as gimple by
496
         using a temporary variable.  */
497
      if (is_gimple_cast (cond)
498
          && !is_gimple_val (TREE_OPERAND (cond, 0)))
499
        {
500
          tree op0, tmp, cond_tmp;
501
 
502
          /* Only "real" casts are OK here, not everything that is
503
             acceptable to is_gimple_cast.  Make sure we don't do
504
             anything stupid here.  */
505
          gcc_assert (TREE_CODE (cond) == NOP_EXPR
506
                      || TREE_CODE (cond) == CONVERT_EXPR);
507
 
508
          op0 = TREE_OPERAND (cond, 0);
509
          tmp = create_tmp_var (TREE_TYPE (op0), NULL);
510
          add_referenced_tmp_var (tmp);
511
          cond_tmp = make_ssa_name (tmp, NULL);
512
          new = build2 (MODIFY_EXPR, TREE_TYPE (cond_tmp), cond_tmp, op0);
513
          SSA_NAME_DEF_STMT (cond_tmp) = new;
514
 
515
          bsi_insert_after (&bsi, new, BSI_NEW_STMT);
516
          cond = fold_convert (TREE_TYPE (result), cond_tmp);
517
        }
518
 
519
      new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
520
    }
521
 
522
  bsi_insert_after (&bsi, new, BSI_NEW_STMT);
523
 
524
  SSA_NAME_DEF_STMT (new_var1) = new;
525
 
526
  replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
527
 
528
  /* Note that we optimized this PHI.  */
529
  return true;
530
}
531
 
532
/*  The function value_replacement does the main work of doing the value
533
    replacement.  Return true if the replacement is done.  Otherwise return
534
    false.
535
    BB is the basic block where the replacement is going to be done on.  ARG0
536
    is argument 0 from the PHI.  Likewise for ARG1.  */
537
 
538
static bool
539
value_replacement (basic_block cond_bb, basic_block middle_bb,
540
                   edge e0, edge e1, tree phi,
541
                   tree arg0, tree arg1)
542
{
543
  tree cond;
544
  edge true_edge, false_edge;
545
 
546
  /* If the type says honor signed zeros we cannot do this
547
     optimization.  */
548
  if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
549
    return false;
550
 
551
  if (!empty_block_p (middle_bb))
552
    return false;
553
 
554
  cond = COND_EXPR_COND (last_stmt (cond_bb));
555
 
556
  /* This transformation is only valid for equality comparisons.  */
557
  if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
558
    return false;
559
 
560
  /* We need to know which is the true edge and which is the false
561
      edge so that we know if have abs or negative abs.  */
562
  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
563
 
564
  /* At this point we know we have a COND_EXPR with two successors.
565
     One successor is BB, the other successor is an empty block which
566
     falls through into BB.
567
 
568
     The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
569
 
570
     There is a single PHI node at the join point (BB) with two arguments.
571
 
572
     We now need to verify that the two arguments in the PHI node match
573
     the two arguments to the equality comparison.  */
574
 
575
  if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
576
       && operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
577
      || (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
578
          && operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
579
    {
580
      edge e;
581
      tree arg;
582
 
583
      /* For NE_EXPR, we want to build an assignment result = arg where
584
         arg is the PHI argument associated with the true edge.  For
585
         EQ_EXPR we want the PHI argument associated with the false edge.  */
586
      e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
587
 
588
      /* Unfortunately, E may not reach BB (it may instead have gone to
589
         OTHER_BLOCK).  If that is the case, then we want the single outgoing
590
         edge from OTHER_BLOCK which reaches BB and represents the desired
591
         path from COND_BLOCK.  */
592
      if (e->dest == middle_bb)
593
        e = single_succ_edge (e->dest);
594
 
595
      /* Now we know the incoming edge to BB that has the argument for the
596
         RHS of our new assignment statement.  */
597
      if (e0 == e)
598
        arg = arg0;
599
      else
600
        arg = arg1;
601
 
602
      replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
603
 
604
      /* Note that we optimized this PHI.  */
605
      return true;
606
    }
607
  return false;
608
}
609
 
610
/*  The function minmax_replacement does the main work of doing the minmax
611
    replacement.  Return true if the replacement is done.  Otherwise return
612
    false.
613
    BB is the basic block where the replacement is going to be done on.  ARG0
614
    is argument 0 from the PHI.  Likewise for ARG1.  */
615
 
616
static bool
617
minmax_replacement (basic_block cond_bb, basic_block middle_bb,
618
                    edge e0, edge e1, tree phi,
619
                    tree arg0, tree arg1)
620
{
621
  tree result, type;
622
  tree cond, new;
623
  edge true_edge, false_edge;
624
  enum tree_code cmp, minmax, ass_code;
625
  tree smaller, larger, arg_true, arg_false;
626
  block_stmt_iterator bsi, bsi_from;
627
 
628
  type = TREE_TYPE (PHI_RESULT (phi));
629
 
630
  /* The optimization may be unsafe due to NaNs.  */
631
  if (HONOR_NANS (TYPE_MODE (type)))
632
    return false;
633
 
634
  cond = COND_EXPR_COND (last_stmt (cond_bb));
635
  cmp = TREE_CODE (cond);
636
  result = PHI_RESULT (phi);
637
 
638
  /* This transformation is only valid for order comparisons.  Record which
639
     operand is smaller/larger if the result of the comparison is true.  */
640
  if (cmp == LT_EXPR || cmp == LE_EXPR)
641
    {
642
      smaller = TREE_OPERAND (cond, 0);
643
      larger = TREE_OPERAND (cond, 1);
644
    }
645
  else if (cmp == GT_EXPR || cmp == GE_EXPR)
646
    {
647
      smaller = TREE_OPERAND (cond, 1);
648
      larger = TREE_OPERAND (cond, 0);
649
    }
650
  else
651
    return false;
652
 
653
  /* We need to know which is the true edge and which is the false
654
      edge so that we know if have abs or negative abs.  */
655
  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
656
 
657
  /* Forward the edges over the middle basic block.  */
658
  if (true_edge->dest == middle_bb)
659
    true_edge = EDGE_SUCC (true_edge->dest, 0);
660
  if (false_edge->dest == middle_bb)
661
    false_edge = EDGE_SUCC (false_edge->dest, 0);
662
 
663
  if (true_edge == e0)
664
    {
665
      gcc_assert (false_edge == e1);
666
      arg_true = arg0;
667
      arg_false = arg1;
668
    }
669
  else
670
    {
671
      gcc_assert (false_edge == e0);
672
      gcc_assert (true_edge == e1);
673
      arg_true = arg1;
674
      arg_false = arg0;
675
    }
676
 
677
  if (empty_block_p (middle_bb))
678
    {
679
      if (operand_equal_for_phi_arg_p (arg_true, smaller)
680
          && operand_equal_for_phi_arg_p (arg_false, larger))
681
        {
682
          /* Case
683
 
684
             if (smaller < larger)
685
             rslt = smaller;
686
             else
687
             rslt = larger;  */
688
          minmax = MIN_EXPR;
689
        }
690
      else if (operand_equal_for_phi_arg_p (arg_false, smaller)
691
               && operand_equal_for_phi_arg_p (arg_true, larger))
692
        minmax = MAX_EXPR;
693
      else
694
        return false;
695
    }
696
  else
697
    {
698
      /* Recognize the following case, assuming d <= u:
699
 
700
         if (a <= u)
701
           b = MAX (a, d);
702
         x = PHI <b, u>
703
 
704
         This is equivalent to
705
 
706
         b = MAX (a, d);
707
         x = MIN (b, u);  */
708
 
709
      tree assign = last_and_only_stmt (middle_bb);
710
      tree lhs, rhs, op0, op1, bound;
711
 
712
      if (!assign
713
          || TREE_CODE (assign) != MODIFY_EXPR)
714
        return false;
715
 
716
      lhs = TREE_OPERAND (assign, 0);
717
      rhs = TREE_OPERAND (assign, 1);
718
      ass_code = TREE_CODE (rhs);
719
      if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
720
        return false;
721
      op0 = TREE_OPERAND (rhs, 0);
722
      op1 = TREE_OPERAND (rhs, 1);
723
 
724
      if (true_edge->src == middle_bb)
725
        {
726
          /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
727
          if (!operand_equal_for_phi_arg_p (lhs, arg_true))
728
            return false;
729
 
730
          if (operand_equal_for_phi_arg_p (arg_false, larger))
731
            {
732
              /* Case
733
 
734
                 if (smaller < larger)
735
                   {
736
                     r' = MAX_EXPR (smaller, bound)
737
                   }
738
                 r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
739
              if (ass_code != MAX_EXPR)
740
                return false;
741
 
742
              minmax = MIN_EXPR;
743
              if (operand_equal_for_phi_arg_p (op0, smaller))
744
                bound = op1;
745
              else if (operand_equal_for_phi_arg_p (op1, smaller))
746
                bound = op0;
747
              else
748
                return false;
749
 
750
              /* We need BOUND <= LARGER.  */
751
              if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
752
                                                  bound, larger)))
753
                return false;
754
            }
755
          else if (operand_equal_for_phi_arg_p (arg_false, smaller))
756
            {
757
              /* Case
758
 
759
                 if (smaller < larger)
760
                   {
761
                     r' = MIN_EXPR (larger, bound)
762
                   }
763
                 r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
764
              if (ass_code != MIN_EXPR)
765
                return false;
766
 
767
              minmax = MAX_EXPR;
768
              if (operand_equal_for_phi_arg_p (op0, larger))
769
                bound = op1;
770
              else if (operand_equal_for_phi_arg_p (op1, larger))
771
                bound = op0;
772
              else
773
                return false;
774
 
775
              /* We need BOUND >= SMALLER.  */
776
              if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
777
                                                  bound, smaller)))
778
                return false;
779
            }
780
          else
781
            return false;
782
        }
783
      else
784
        {
785
          /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
786
          if (!operand_equal_for_phi_arg_p (lhs, arg_false))
787
            return false;
788
 
789
          if (operand_equal_for_phi_arg_p (arg_true, larger))
790
            {
791
              /* Case
792
 
793
                 if (smaller > larger)
794
                   {
795
                     r' = MIN_EXPR (smaller, bound)
796
                   }
797
                 r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
798
              if (ass_code != MIN_EXPR)
799
                return false;
800
 
801
              minmax = MAX_EXPR;
802
              if (operand_equal_for_phi_arg_p (op0, smaller))
803
                bound = op1;
804
              else if (operand_equal_for_phi_arg_p (op1, smaller))
805
                bound = op0;
806
              else
807
                return false;
808
 
809
              /* We need BOUND >= LARGER.  */
810
              if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
811
                                                  bound, larger)))
812
                return false;
813
            }
814
          else if (operand_equal_for_phi_arg_p (arg_true, smaller))
815
            {
816
              /* Case
817
 
818
                 if (smaller > larger)
819
                   {
820
                     r' = MAX_EXPR (larger, bound)
821
                   }
822
                 r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
823
              if (ass_code != MAX_EXPR)
824
                return false;
825
 
826
              minmax = MIN_EXPR;
827
              if (operand_equal_for_phi_arg_p (op0, larger))
828
                bound = op1;
829
              else if (operand_equal_for_phi_arg_p (op1, larger))
830
                bound = op0;
831
              else
832
                return false;
833
 
834
              /* We need BOUND <= SMALLER.  */
835
              if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
836
                                                  bound, smaller)))
837
                return false;
838
            }
839
          else
840
            return false;
841
        }
842
 
843
      /* Move the statement from the middle block.  */
844
      bsi = bsi_last (cond_bb);
845
      bsi_from = bsi_last (middle_bb);
846
      bsi_move_before (&bsi_from, &bsi);
847
    }
848
 
849
  /* Emit the statement to compute min/max.  */
850
  result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
851
  new = build2 (MODIFY_EXPR, type, result,
852
                build2 (minmax, type, arg0, arg1));
853
  SSA_NAME_DEF_STMT (result) = new;
854
  bsi = bsi_last (cond_bb);
855
  bsi_insert_before (&bsi, new, BSI_NEW_STMT);
856
 
857
  replace_phi_edge_with_variable (cond_bb, e1, phi, result);
858
  return true;
859
}
860
 
861
/*  The function absolute_replacement does the main work of doing the absolute
862
    replacement.  Return true if the replacement is done.  Otherwise return
863
    false.
864
    bb is the basic block where the replacement is going to be done on.  arg0
865
    is argument 0 from the phi.  Likewise for arg1.  */
866
 
867
static bool
868
abs_replacement (basic_block cond_bb, basic_block middle_bb,
869
                 edge e0 ATTRIBUTE_UNUSED, edge e1,
870
                 tree phi, tree arg0, tree arg1)
871
{
872
  tree result;
873
  tree new, cond;
874
  block_stmt_iterator bsi;
875
  edge true_edge, false_edge;
876
  tree assign;
877
  edge e;
878
  tree rhs, lhs;
879
  bool negate;
880
  enum tree_code cond_code;
881
 
882
  /* If the type says honor signed zeros we cannot do this
883
     optimization.  */
884
  if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
885
    return false;
886
 
887
  /* OTHER_BLOCK must have only one executable statement which must have the
888
     form arg0 = -arg1 or arg1 = -arg0.  */
889
 
890
  assign = last_and_only_stmt (middle_bb);
891
  /* If we did not find the proper negation assignment, then we can not
892
     optimize.  */
893
  if (assign == NULL)
894
    return false;
895
 
896
  /* If we got here, then we have found the only executable statement
897
     in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
898
     arg1 = -arg0, then we can not optimize.  */
899
  if (TREE_CODE (assign) != MODIFY_EXPR)
900
    return false;
901
 
902
  lhs = TREE_OPERAND (assign, 0);
903
  rhs = TREE_OPERAND (assign, 1);
904
 
905
  if (TREE_CODE (rhs) != NEGATE_EXPR)
906
    return false;
907
 
908
  rhs = TREE_OPERAND (rhs, 0);
909
 
910
  /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
911
  if (!(lhs == arg0 && rhs == arg1)
912
      && !(lhs == arg1 && rhs == arg0))
913
    return false;
914
 
915
  cond = COND_EXPR_COND (last_stmt (cond_bb));
916
  result = PHI_RESULT (phi);
917
 
918
  /* Only relationals comparing arg[01] against zero are interesting.  */
919
  cond_code = TREE_CODE (cond);
920
  if (cond_code != GT_EXPR && cond_code != GE_EXPR
921
      && cond_code != LT_EXPR && cond_code != LE_EXPR)
922
    return false;
923
 
924
  /* Make sure the conditional is arg[01] OP y.  */
925
  if (TREE_OPERAND (cond, 0) != rhs)
926
    return false;
927
 
928
  if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
929
               ? real_zerop (TREE_OPERAND (cond, 1))
930
               : integer_zerop (TREE_OPERAND (cond, 1)))
931
    ;
932
  else
933
    return false;
934
 
935
  /* We need to know which is the true edge and which is the false
936
     edge so that we know if have abs or negative abs.  */
937
  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
938
 
939
  /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
940
     will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
941
     the false edge goes to OTHER_BLOCK.  */
942
  if (cond_code == GT_EXPR || cond_code == GE_EXPR)
943
    e = true_edge;
944
  else
945
    e = false_edge;
946
 
947
  if (e->dest == middle_bb)
948
    negate = true;
949
  else
950
    negate = false;
951
 
952
  result = duplicate_ssa_name (result, NULL);
953
 
954
  if (negate)
955
    {
956
      tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
957
      add_referenced_tmp_var (tmp);
958
      lhs = make_ssa_name (tmp, NULL);
959
    }
960
  else
961
    lhs = result;
962
 
963
  /* Build the modify expression with abs expression.  */
964
  new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
965
                lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
966
  SSA_NAME_DEF_STMT (lhs) = new;
967
 
968
  bsi = bsi_last (cond_bb);
969
  bsi_insert_before (&bsi, new, BSI_NEW_STMT);
970
 
971
  if (negate)
972
    {
973
      /* Get the right BSI.  We want to insert after the recently
974
         added ABS_EXPR statement (which we know is the first statement
975
         in the block.  */
976
      new = build2 (MODIFY_EXPR, TREE_TYPE (result),
977
                    result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
978
      SSA_NAME_DEF_STMT (result) = new;
979
 
980
      bsi_insert_after (&bsi, new, BSI_NEW_STMT);
981
    }
982
 
983
  replace_phi_edge_with_variable (cond_bb, e1, phi, result);
984
 
985
  /* Note that we optimized this PHI.  */
986
  return true;
987
}
988
 
989
 
990
/* Always do these optimizations if we have SSA
991
   trees to work on.  */
992
static bool
993
gate_phiopt (void)
994
{
995
  return 1;
996
}
997
 
998
struct tree_opt_pass pass_phiopt =
999
{
1000
  "phiopt",                             /* name */
1001
  gate_phiopt,                          /* gate */
1002
  tree_ssa_phiopt,                      /* execute */
1003
  NULL,                                 /* sub */
1004
  NULL,                                 /* next */
1005
  0,                                     /* static_pass_number */
1006
  TV_TREE_PHIOPT,                       /* tv_id */
1007
  PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1008
  0,                                     /* properties_provided */
1009
  0,                                     /* properties_destroyed */
1010
  0,                                     /* todo_flags_start */
1011
  TODO_cleanup_cfg
1012
    | TODO_dump_func
1013
    | TODO_ggc_collect
1014
    | TODO_verify_ssa
1015
    | TODO_verify_flow
1016
    | TODO_verify_stmts,                /* todo_flags_finish */
1017
 
1018
};

powered by: WebSVN 2.1.0

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