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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-uncprop.c] - Blame information for rev 708

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

Line No. Rev Author Line
1 684 jeremybenn
/* Routines for discovering and unpropagating edge equivalences.
2
   Copyright (C) 2005, 2007, 2008, 2010
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License 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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "flags.h"
27
#include "tm_p.h"
28
#include "basic-block.h"
29
#include "output.h"
30
#include "function.h"
31
#include "timevar.h"
32
#include "tree-dump.h"
33
#include "tree-flow.h"
34
#include "domwalk.h"
35
#include "tree-pass.h"
36
#include "tree-ssa-propagate.h"
37
#include "langhooks.h"
38
 
39
/* The basic structure describing an equivalency created by traversing
40
   an edge.  Traversing the edge effectively means that we can assume
41
   that we've seen an assignment LHS = RHS.  */
42
struct edge_equivalency
43
{
44
  tree rhs;
45
  tree lhs;
46
};
47
 
48
/* This routine finds and records edge equivalences for every edge
49
   in the CFG.
50
 
51
   When complete, each edge that creates an equivalency will have an
52
   EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
53
   The caller is responsible for freeing the AUX fields.  */
54
 
55
static void
56
associate_equivalences_with_edges (void)
57
{
58
  basic_block bb;
59
 
60
  /* Walk over each block.  If the block ends with a control statement,
61
     then it might create a useful equivalence.  */
62
  FOR_EACH_BB (bb)
63
    {
64
      gimple_stmt_iterator gsi = gsi_last_bb (bb);
65
      gimple stmt;
66
 
67
      /* If the block does not end with a COND_EXPR or SWITCH_EXPR
68
         then there is nothing to do.  */
69
      if (gsi_end_p (gsi))
70
        continue;
71
 
72
      stmt = gsi_stmt (gsi);
73
 
74
      if (!stmt)
75
        continue;
76
 
77
      /* A COND_EXPR may create an equivalency in a variety of different
78
         ways.  */
79
      if (gimple_code (stmt) == GIMPLE_COND)
80
        {
81
          edge true_edge;
82
          edge false_edge;
83
          struct edge_equivalency *equivalency;
84
          enum tree_code code = gimple_cond_code (stmt);
85
 
86
          extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
87
 
88
          /* Equality tests may create one or two equivalences.  */
89
          if (code == EQ_EXPR || code == NE_EXPR)
90
            {
91
              tree op0 = gimple_cond_lhs (stmt);
92
              tree op1 = gimple_cond_rhs (stmt);
93
 
94
              /* Special case comparing booleans against a constant as we
95
                 know the value of OP0 on both arms of the branch.  i.e., we
96
                 can record an equivalence for OP0 rather than COND.  */
97
              if (TREE_CODE (op0) == SSA_NAME
98
                  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
99
                  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
100
                  && is_gimple_min_invariant (op1))
101
                {
102
                  if (code == EQ_EXPR)
103
                    {
104
                      equivalency = XNEW (struct edge_equivalency);
105
                      equivalency->lhs = op0;
106
                      equivalency->rhs = (integer_zerop (op1)
107
                                          ? boolean_false_node
108
                                          : boolean_true_node);
109
                      true_edge->aux = equivalency;
110
 
111
                      equivalency = XNEW (struct edge_equivalency);
112
                      equivalency->lhs = op0;
113
                      equivalency->rhs = (integer_zerop (op1)
114
                                          ? boolean_true_node
115
                                          : boolean_false_node);
116
                      false_edge->aux = equivalency;
117
                    }
118
                  else
119
                    {
120
                      equivalency = XNEW (struct edge_equivalency);
121
                      equivalency->lhs = op0;
122
                      equivalency->rhs = (integer_zerop (op1)
123
                                          ? boolean_true_node
124
                                          : boolean_false_node);
125
                      true_edge->aux = equivalency;
126
 
127
                      equivalency = XNEW (struct edge_equivalency);
128
                      equivalency->lhs = op0;
129
                      equivalency->rhs = (integer_zerop (op1)
130
                                          ? boolean_false_node
131
                                          : boolean_true_node);
132
                      false_edge->aux = equivalency;
133
                    }
134
                }
135
 
136
              else if (TREE_CODE (op0) == SSA_NAME
137
                       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
138
                       && (is_gimple_min_invariant (op1)
139
                           || (TREE_CODE (op1) == SSA_NAME
140
                               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
141
                {
142
                  /* For IEEE, -0.0 == 0.0, so we don't necessarily know
143
                     the sign of a variable compared against zero.  If
144
                     we're honoring signed zeros, then we cannot record
145
                     this value unless we know that the value is nonzero.  */
146
                  if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
147
                      && (TREE_CODE (op1) != REAL_CST
148
                          || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
149
                    continue;
150
 
151
                  equivalency = XNEW (struct edge_equivalency);
152
                  equivalency->lhs = op0;
153
                  equivalency->rhs = op1;
154
                  if (code == EQ_EXPR)
155
                    true_edge->aux = equivalency;
156
                  else
157
                    false_edge->aux = equivalency;
158
 
159
                }
160
            }
161
 
162
          /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
163
        }
164
 
165
      /* For a SWITCH_EXPR, a case label which represents a single
166
         value and which is the only case label which reaches the
167
         target block creates an equivalence.  */
168
      else if (gimple_code (stmt) == GIMPLE_SWITCH)
169
        {
170
          tree cond = gimple_switch_index (stmt);
171
 
172
          if (TREE_CODE (cond) == SSA_NAME
173
              && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
174
            {
175
              int i, n_labels = gimple_switch_num_labels (stmt);
176
              tree *info = XCNEWVEC (tree, last_basic_block);
177
 
178
              /* Walk over the case label vector.  Record blocks
179
                 which are reached by a single case label which represents
180
                 a single value.  */
181
              for (i = 0; i < n_labels; i++)
182
                {
183
                  tree label = gimple_switch_label (stmt, i);
184
                  basic_block bb = label_to_block (CASE_LABEL (label));
185
 
186
                  if (CASE_HIGH (label)
187
                      || !CASE_LOW (label)
188
                      || info[bb->index])
189
                    info[bb->index] = error_mark_node;
190
                  else
191
                    info[bb->index] = label;
192
                }
193
 
194
              /* Now walk over the blocks to determine which ones were
195
                 marked as being reached by a useful case label.  */
196
              for (i = 0; i < n_basic_blocks; i++)
197
                {
198
                  tree node = info[i];
199
 
200
                  if (node != NULL
201
                      && node != error_mark_node)
202
                    {
203
                      tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
204
                      struct edge_equivalency *equivalency;
205
 
206
                      /* Record an equivalency on the edge from BB to basic
207
                         block I.  */
208
                      equivalency = XNEW (struct edge_equivalency);
209
                      equivalency->rhs = x;
210
                      equivalency->lhs = cond;
211
                      find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
212
                    }
213
                }
214
              free (info);
215
            }
216
        }
217
 
218
    }
219
}
220
 
221
 
222
/* Translating out of SSA sometimes requires inserting copies and
223
   constant initializations on edges to eliminate PHI nodes.
224
 
225
   In some cases those copies and constant initializations are
226
   redundant because the target already has the value on the
227
   RHS of the assignment.
228
 
229
   We previously tried to catch these cases after translating
230
   out of SSA form.  However, that code often missed cases.  Worse
231
   yet, the cases it missed were also often missed by the RTL
232
   optimizers.  Thus the resulting code had redundant instructions.
233
 
234
   This pass attempts to detect these situations before translating
235
   out of SSA form.
236
 
237
   The key concept that this pass is built upon is that these
238
   redundant copies and constant initializations often occur
239
   due to constant/copy propagating equivalences resulting from
240
   COND_EXPRs and SWITCH_EXPRs.
241
 
242
   We want to do those propagations as they can sometimes allow
243
   the SSA optimizers to do a better job.  However, in the cases
244
   where such propagations do not result in further optimization,
245
   we would like to "undo" the propagation to avoid the redundant
246
   copies and constant initializations.
247
 
248
   This pass works by first associating equivalences with edges in
249
   the CFG.  For example, the edge leading from a SWITCH_EXPR to
250
   its associated CASE_LABEL will have an equivalency between
251
   SWITCH_COND and the value in the case label.
252
 
253
   Once we have found the edge equivalences, we proceed to walk
254
   the CFG in dominator order.  As we traverse edges we record
255
   equivalences associated with those edges we traverse.
256
 
257
   When we encounter a PHI node, we walk its arguments to see if we
258
   have an equivalence for the PHI argument.  If so, then we replace
259
   the argument.
260
 
261
   Equivalences are looked up based on their value (think of it as
262
   the RHS of an assignment).   A value may be an SSA_NAME or an
263
   invariant.  We may have several SSA_NAMEs with the same value,
264
   so with each value we have a list of SSA_NAMEs that have the
265
   same value.  */
266
 
267
/* As we enter each block we record the value for any edge equivalency
268
   leading to this block.  If no such edge equivalency exists, then we
269
   record NULL.  These equivalences are live until we leave the dominator
270
   subtree rooted at the block where we record the equivalency.  */
271
static VEC(tree,heap) *equiv_stack;
272
 
273
/* Global hash table implementing a mapping from invariant values
274
   to a list of SSA_NAMEs which have the same value.  We might be
275
   able to reuse tree-vn for this code.  */
276
static htab_t equiv;
277
 
278
/* Main structure for recording equivalences into our hash table.  */
279
struct equiv_hash_elt
280
{
281
  /* The value/key of this entry.  */
282
  tree value;
283
 
284
  /* List of SSA_NAMEs which have the same value/key.  */
285
  VEC(tree,heap) *equivalences;
286
};
287
 
288
static void uncprop_enter_block (struct dom_walk_data *, basic_block);
289
static void uncprop_leave_block (struct dom_walk_data *, basic_block);
290
static void uncprop_into_successor_phis (basic_block);
291
 
292
/* Hashing and equality routines for the hash table.  */
293
 
294
static hashval_t
295
equiv_hash (const void *p)
296
{
297
  tree const value = ((const struct equiv_hash_elt *)p)->value;
298
  return iterative_hash_expr (value, 0);
299
}
300
 
301
static int
302
equiv_eq (const void *p1, const void *p2)
303
{
304
  tree value1 = ((const struct equiv_hash_elt *)p1)->value;
305
  tree value2 = ((const struct equiv_hash_elt *)p2)->value;
306
 
307
  return operand_equal_p (value1, value2, 0);
308
}
309
 
310
/* Free an instance of equiv_hash_elt.  */
311
 
312
static void
313
equiv_free (void *p)
314
{
315
  struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
316
  VEC_free (tree, heap, elt->equivalences);
317
  free (elt);
318
}
319
 
320
/* Remove the most recently recorded equivalency for VALUE.  */
321
 
322
static void
323
remove_equivalence (tree value)
324
{
325
  struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
326
  void **slot;
327
 
328
  equiv_hash_elt.value = value;
329
  equiv_hash_elt.equivalences = NULL;
330
 
331
  slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
332
 
333
  equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
334
  VEC_pop (tree, equiv_hash_elt_p->equivalences);
335
}
336
 
337
/* Record EQUIVALENCE = VALUE into our hash table.  */
338
 
339
static void
340
record_equiv (tree value, tree equivalence)
341
{
342
  struct equiv_hash_elt *equiv_hash_elt;
343
  void **slot;
344
 
345
  equiv_hash_elt = XNEW (struct equiv_hash_elt);
346
  equiv_hash_elt->value = value;
347
  equiv_hash_elt->equivalences = NULL;
348
 
349
  slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
350
 
351
  if (*slot == NULL)
352
    *slot = (void *) equiv_hash_elt;
353
  else
354
     free (equiv_hash_elt);
355
 
356
  equiv_hash_elt = (struct equiv_hash_elt *) *slot;
357
 
358
  VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
359
}
360
 
361
/* Main driver for un-cprop.  */
362
 
363
static unsigned int
364
tree_ssa_uncprop (void)
365
{
366
  struct dom_walk_data walk_data;
367
  basic_block bb;
368
 
369
  associate_equivalences_with_edges ();
370
 
371
  /* Create our global data structures.  */
372
  equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
373
  equiv_stack = VEC_alloc (tree, heap, 2);
374
 
375
  /* We're going to do a dominator walk, so ensure that we have
376
     dominance information.  */
377
  calculate_dominance_info (CDI_DOMINATORS);
378
 
379
  /* Setup callbacks for the generic dominator tree walker.  */
380
  walk_data.dom_direction = CDI_DOMINATORS;
381
  walk_data.initialize_block_local_data = NULL;
382
  walk_data.before_dom_children = uncprop_enter_block;
383
  walk_data.after_dom_children = uncprop_leave_block;
384
  walk_data.global_data = NULL;
385
  walk_data.block_local_data_size = 0;
386
 
387
  /* Now initialize the dominator walker.  */
388
  init_walk_dominator_tree (&walk_data);
389
 
390
  /* Recursively walk the dominator tree undoing unprofitable
391
     constant/copy propagations.  */
392
  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
393
 
394
  /* Finalize and clean up.  */
395
  fini_walk_dominator_tree (&walk_data);
396
 
397
  /* EQUIV_STACK should already be empty at this point, so we just
398
     need to empty elements out of the hash table, free EQUIV_STACK,
399
     and cleanup the AUX field on the edges.  */
400
  htab_delete (equiv);
401
  VEC_free (tree, heap, equiv_stack);
402
  FOR_EACH_BB (bb)
403
    {
404
      edge e;
405
      edge_iterator ei;
406
 
407
      FOR_EACH_EDGE (e, ei, bb->succs)
408
        {
409
          if (e->aux)
410
            {
411
              free (e->aux);
412
              e->aux = NULL;
413
            }
414
        }
415
    }
416
  return 0;
417
}
418
 
419
 
420
/* We have finished processing the dominator children of BB, perform
421
   any finalization actions in preparation for leaving this node in
422
   the dominator tree.  */
423
 
424
static void
425
uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
426
                     basic_block bb ATTRIBUTE_UNUSED)
427
{
428
  /* Pop the topmost value off the equiv stack.  */
429
  tree value = VEC_pop (tree, equiv_stack);
430
 
431
  /* If that value was non-null, then pop the topmost equivalency off
432
     its equivalency stack.  */
433
  if (value != NULL)
434
    remove_equivalence (value);
435
}
436
 
437
/* Unpropagate values from PHI nodes in successor blocks of BB.  */
438
 
439
static void
440
uncprop_into_successor_phis (basic_block bb)
441
{
442
  edge e;
443
  edge_iterator ei;
444
 
445
  /* For each successor edge, first temporarily record any equivalence
446
     on that edge.  Then unpropagate values in any PHI nodes at the
447
     destination of the edge.  Then remove the temporary equivalence.  */
448
  FOR_EACH_EDGE (e, ei, bb->succs)
449
    {
450
      gimple_seq phis = phi_nodes (e->dest);
451
      gimple_stmt_iterator gsi;
452
 
453
      /* If there are no PHI nodes in this destination, then there is
454
         no sense in recording any equivalences.  */
455
      if (gimple_seq_empty_p (phis))
456
        continue;
457
 
458
      /* Record any equivalency associated with E.  */
459
      if (e->aux)
460
        {
461
          struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
462
          record_equiv (equiv->rhs, equiv->lhs);
463
        }
464
 
465
      /* Walk over the PHI nodes, unpropagating values.  */
466
      for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
467
        {
468
          gimple phi = gsi_stmt (gsi);
469
          tree arg = PHI_ARG_DEF (phi, e->dest_idx);
470
          struct equiv_hash_elt equiv_hash_elt;
471
          void **slot;
472
 
473
          /* If the argument is not an invariant, or refers to the same
474
             underlying variable as the PHI result, then there's no
475
             point in un-propagating the argument.  */
476
          if (!is_gimple_min_invariant (arg)
477
              && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
478
            continue;
479
 
480
          /* Lookup this argument's value in the hash table.  */
481
          equiv_hash_elt.value = arg;
482
          equiv_hash_elt.equivalences = NULL;
483
          slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
484
 
485
          if (slot)
486
            {
487
              struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
488
              int j;
489
 
490
              /* Walk every equivalence with the same value.  If we find
491
                 one with the same underlying variable as the PHI result,
492
                 then replace the value in the argument with its equivalent
493
                 SSA_NAME.  Use the most recent equivalence as hopefully
494
                 that results in shortest lifetimes.  */
495
              for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
496
                {
497
                  tree equiv = VEC_index (tree, elt->equivalences, j);
498
 
499
                  if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
500
                    {
501
                      SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
502
                      break;
503
                    }
504
                }
505
            }
506
        }
507
 
508
      /* If we had an equivalence associated with this edge, remove it.  */
509
      if (e->aux)
510
        {
511
          struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
512
          remove_equivalence (equiv->rhs);
513
        }
514
    }
515
}
516
 
517
/* Ignoring loop backedges, if BB has precisely one incoming edge then
518
   return that edge.  Otherwise return NULL.  */
519
static edge
520
single_incoming_edge_ignoring_loop_edges (basic_block bb)
521
{
522
  edge retval = NULL;
523
  edge e;
524
  edge_iterator ei;
525
 
526
  FOR_EACH_EDGE (e, ei, bb->preds)
527
    {
528
      /* A loop back edge can be identified by the destination of
529
         the edge dominating the source of the edge.  */
530
      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
531
        continue;
532
 
533
      /* If we have already seen a non-loop edge, then we must have
534
         multiple incoming non-loop edges and thus we return NULL.  */
535
      if (retval)
536
        return NULL;
537
 
538
      /* This is the first non-loop incoming edge we have found.  Record
539
         it.  */
540
      retval = e;
541
    }
542
 
543
  return retval;
544
}
545
 
546
static void
547
uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
548
                     basic_block bb)
549
{
550
  basic_block parent;
551
  edge e;
552
  bool recorded = false;
553
 
554
  /* If this block is dominated by a single incoming edge and that edge
555
     has an equivalency, then record the equivalency and push the
556
     VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
557
  parent = get_immediate_dominator (CDI_DOMINATORS, bb);
558
  if (parent)
559
    {
560
      e = single_incoming_edge_ignoring_loop_edges (bb);
561
 
562
      if (e && e->src == parent && e->aux)
563
        {
564
          struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
565
 
566
          record_equiv (equiv->rhs, equiv->lhs);
567
          VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
568
          recorded = true;
569
        }
570
    }
571
 
572
  if (!recorded)
573
    VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
574
 
575
  uncprop_into_successor_phis (bb);
576
}
577
 
578
static bool
579
gate_uncprop (void)
580
{
581
  return flag_tree_dom != 0;
582
}
583
 
584
struct gimple_opt_pass pass_uncprop =
585
{
586
 {
587
  GIMPLE_PASS,
588
  "uncprop",                            /* name */
589
  gate_uncprop,                         /* gate */
590
  tree_ssa_uncprop,                     /* execute */
591
  NULL,                                 /* sub */
592
  NULL,                                 /* next */
593
  0,                                     /* static_pass_number */
594
  TV_TREE_SSA_UNCPROP,                  /* tv_id */
595
  PROP_cfg | PROP_ssa,                  /* properties_required */
596
  0,                                     /* properties_provided */
597
  0,                                     /* properties_destroyed */
598
  0,                                     /* todo_flags_start */
599
  TODO_verify_ssa                       /* todo_flags_finish */
600
 }
601
};

powered by: WebSVN 2.1.0

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