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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-phiopt.c] - Blame information for rev 841

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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