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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 38 julius
/* Dead store elimination
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
7
it under the terms of the GNU General Public License as published by
8
the Free Software Foundation; either version 3, or (at your option)
9
any later version.
10
 
11
GCC is distributed in the hope that it will be useful,
12
but WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
GNU General Public License 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 "tm_p.h"
28
#include "basic-block.h"
29
#include "timevar.h"
30
#include "diagnostic.h"
31
#include "tree-flow.h"
32
#include "tree-pass.h"
33
#include "tree-dump.h"
34
#include "domwalk.h"
35
#include "flags.h"
36
 
37
/* This file implements dead store elimination.
38
 
39
   A dead store is a store into a memory location which will later be
40
   overwritten by another store without any intervening loads.  In this
41
   case the earlier store can be deleted.
42
 
43
   In our SSA + virtual operand world we use immediate uses of virtual
44
   operands to detect dead stores.  If a store's virtual definition
45
   is used precisely once by a later store to the same location which
46
   post dominates the first store, then the first store is dead.
47
 
48
   The single use of the store's virtual definition ensures that
49
   there are no intervening aliased loads and the requirement that
50
   the second load post dominate the first ensures that if the earlier
51
   store executes, then the later stores will execute before the function
52
   exits.
53
 
54
   It may help to think of this as first moving the earlier store to
55
   the point immediately before the later store.  Again, the single
56
   use of the virtual definition and the post-dominance relationship
57
   ensure that such movement would be safe.  Clearly if there are
58
   back to back stores, then the second is redundant.
59
 
60
   Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
61
   may also help in understanding this code since it discusses the
62
   relationship between dead store and redundant load elimination.  In
63
   fact, they are the same transformation applied to different views of
64
   the CFG.  */
65
 
66
 
67
struct dse_global_data
68
{
69
  /* This is the global bitmap for store statements.
70
 
71
     Each statement has a unique ID.  When we encounter a store statement
72
     that we want to record, set the bit corresponding to the statement's
73
     unique ID in this bitmap.  */
74
  bitmap stores;
75
};
76
 
77
/* We allocate a bitmap-per-block for stores which are encountered
78
   during the scan of that block.  This allows us to restore the
79
   global bitmap of stores when we finish processing a block.  */
80
struct dse_block_local_data
81
{
82
  bitmap stores;
83
};
84
 
85
/* Basic blocks of the potentially dead store and the following
86
   store, for memory_address_same.  */
87
struct address_walk_data
88
{
89
  basic_block store1_bb, store2_bb;
90
};
91
 
92
static bool gate_dse (void);
93
static unsigned int tree_ssa_dse (void);
94
static void dse_initialize_block_local_data (struct dom_walk_data *,
95
                                             basic_block,
96
                                             bool);
97
static void dse_optimize_stmt (struct dom_walk_data *,
98
                               basic_block,
99
                               block_stmt_iterator);
100
static void dse_record_phis (struct dom_walk_data *, basic_block);
101
static void dse_finalize_block (struct dom_walk_data *, basic_block);
102
static void record_voperand_set (bitmap, bitmap *, unsigned int);
103
 
104
static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
105
                                   nodes are assigned using the versions of
106
                                   ssa names they define.  */
107
 
108
/* Returns uid of statement STMT.  */
109
 
110
static unsigned
111
get_stmt_uid (tree stmt)
112
{
113
  if (TREE_CODE (stmt) == PHI_NODE)
114
    return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
115
 
116
  return stmt_ann (stmt)->uid;
117
}
118
 
119
/* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
120
 
121
static void
122
record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
123
{
124
  /* Lazily allocate the bitmap.  Note that we do not get a notification
125
     when the block local data structures die, so we allocate the local
126
     bitmap backed by the GC system.  */
127
  if (*local == NULL)
128
    *local = BITMAP_GGC_ALLOC ();
129
 
130
  /* Set the bit in the local and global bitmaps.  */
131
  bitmap_set_bit (*local, uid);
132
  bitmap_set_bit (global, uid);
133
}
134
 
135
/* Initialize block local data structures.  */
136
 
137
static void
138
dse_initialize_block_local_data (struct dom_walk_data *walk_data,
139
                                 basic_block bb ATTRIBUTE_UNUSED,
140
                                 bool recycled)
141
{
142
  struct dse_block_local_data *bd
143
    = VEC_last (void_p, walk_data->block_data_stack);
144
 
145
  /* If we are given a recycled block local data structure, ensure any
146
     bitmap associated with the block is cleared.  */
147
  if (recycled)
148
    {
149
      if (bd->stores)
150
        bitmap_clear (bd->stores);
151
    }
152
}
153
 
154
/* Helper function for memory_address_same via walk_tree.  Returns
155
   non-NULL if it finds an SSA_NAME which is part of the address,
156
   such that the definition of the SSA_NAME post-dominates the store
157
   we want to delete but not the store that we believe makes it
158
   redundant.  This indicates that the address may change between
159
   the two stores.  */
160
 
161
static tree
162
memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
163
                      void *data)
164
{
165
  struct address_walk_data *walk_data = data;
166
  tree expr = *expr_p;
167
  tree def_stmt;
168
  basic_block def_bb;
169
 
170
  if (TREE_CODE (expr) != SSA_NAME)
171
    return NULL_TREE;
172
 
173
  /* If we've found a default definition, then there's no problem.  Both
174
     stores will post-dominate it.  And def_bb will be NULL.  */
175
  if (expr == default_def (SSA_NAME_VAR (expr)))
176
    return NULL_TREE;
177
 
178
  def_stmt = SSA_NAME_DEF_STMT (expr);
179
  def_bb = bb_for_stmt (def_stmt);
180
 
181
  /* DEF_STMT must dominate both stores.  So if it is in the same
182
     basic block as one, it does not post-dominate that store.  */
183
  if (walk_data->store1_bb != def_bb
184
      && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
185
    {
186
      if (walk_data->store2_bb == def_bb
187
          || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
188
                              def_bb))
189
        /* Return non-NULL to stop the walk.  */
190
        return def_stmt;
191
    }
192
 
193
  return NULL_TREE;
194
}
195
 
196
/* Return TRUE if the destination memory address in STORE1 and STORE2
197
   might be modified after STORE1, before control reaches STORE2.  */
198
 
199
static bool
200
memory_address_same (tree store1, tree store2)
201
{
202
  struct address_walk_data walk_data;
203
 
204
  walk_data.store1_bb = bb_for_stmt (store1);
205
  walk_data.store2_bb = bb_for_stmt (store2);
206
 
207
  return (walk_tree (&TREE_OPERAND (store1, 0), memory_ssa_name_same,
208
                     &walk_data, NULL)
209
          == NULL);
210
}
211
 
212
/* Attempt to eliminate dead stores in the statement referenced by BSI.
213
 
214
   A dead store is a store into a memory location which will later be
215
   overwritten by another store without any intervening loads.  In this
216
   case the earlier store can be deleted.
217
 
218
   In our SSA + virtual operand world we use immediate uses of virtual
219
   operands to detect dead stores.  If a store's virtual definition
220
   is used precisely once by a later store to the same location which
221
   post dominates the first store, then the first store is dead.  */
222
 
223
static void
224
dse_optimize_stmt (struct dom_walk_data *walk_data,
225
                   basic_block bb ATTRIBUTE_UNUSED,
226
                   block_stmt_iterator bsi)
227
{
228
  struct dse_block_local_data *bd
229
    = VEC_last (void_p, walk_data->block_data_stack);
230
  struct dse_global_data *dse_gd = walk_data->global_data;
231
  tree stmt = bsi_stmt (bsi);
232
  stmt_ann_t ann = stmt_ann (stmt);
233
 
234
  /* If this statement has no virtual defs, then there is nothing
235
     to do.  */
236
  if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)))
237
    return;
238
 
239
  /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
240
     not also a function call, then record it into our table.  */
241
  if (get_call_expr_in (stmt))
242
    return;
243
 
244
  if (ann->has_volatile_ops)
245
    return;
246
 
247
  if (TREE_CODE (stmt) == MODIFY_EXPR)
248
    {
249
      use_operand_p first_use_p = NULL_USE_OPERAND_P;
250
      use_operand_p use_p = NULL;
251
      tree use_stmt, temp;
252
      tree defvar = NULL_TREE, usevar = NULL_TREE;
253
      bool fail = false;
254
      use_operand_p var2;
255
      def_operand_p var1;
256
      ssa_op_iter op_iter;
257
 
258
      /* We want to verify that each virtual definition in STMT has
259
         precisely one use and that all the virtual definitions are
260
         used by the same single statement.  When complete, we
261
         want USE_STMT to refer to the one statement which uses
262
         all of the virtual definitions from STMT.  */
263
      use_stmt = NULL;
264
      FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
265
        {
266
          defvar = DEF_FROM_PTR (var1);
267
          usevar = USE_FROM_PTR (var2);
268
 
269
          /* If this virtual def does not have precisely one use, then
270
             we will not be able to eliminate STMT.  */
271
          if (! has_single_use (defvar))
272
            {
273
              fail = true;
274
              break;
275
            }
276
 
277
          /* Get the one and only immediate use of DEFVAR.  */
278
          single_imm_use (defvar, &use_p, &temp);
279
          gcc_assert (use_p != NULL_USE_OPERAND_P);
280
          first_use_p = use_p;
281
 
282
          /* If the immediate use of DEF_VAR is not the same as the
283
             previously find immediate uses, then we will not be able
284
             to eliminate STMT.  */
285
          if (use_stmt == NULL)
286
            use_stmt = temp;
287
          else if (temp != use_stmt)
288
            {
289
              fail = true;
290
              break;
291
            }
292
        }
293
 
294
      if (fail)
295
        {
296
          record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
297
          return;
298
        }
299
 
300
      /* Skip through any PHI nodes we have already seen if the PHI
301
         represents the only use of this store.
302
 
303
         Note this does not handle the case where the store has
304
         multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
305
         same block.  */
306
      while (use_p != NULL_USE_OPERAND_P
307
             && TREE_CODE (use_stmt) == PHI_NODE
308
             && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
309
        {
310
          /* A PHI node can both define and use the same SSA_NAME if
311
             the PHI is at the top of a loop and the PHI_RESULT is
312
             a loop invariant and copies have not been fully propagated.
313
 
314
             The safe thing to do is exit assuming no optimization is
315
             possible.  */
316
          if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt)
317
            return;
318
 
319
          /* Skip past this PHI and loop again in case we had a PHI
320
             chain.  */
321
          single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt);
322
        }
323
 
324
      /* If we have precisely one immediate use at this point, then we may
325
         have found redundant store.  Make sure that the stores are to
326
         the same memory location.  This includes checking that any
327
         SSA-form variables in the address will have the same values.  */
328
      if (use_p != NULL_USE_OPERAND_P
329
          && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
330
          && operand_equal_p (TREE_OPERAND (stmt, 0),
331
                              TREE_OPERAND (use_stmt, 0), 0)
332
          && memory_address_same (stmt, use_stmt))
333
        {
334
          /* Make sure we propagate the ABNORMAL bit setting.  */
335
          if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
336
            SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
337
 
338
          if (dump_file && (dump_flags & TDF_DETAILS))
339
            {
340
              fprintf (dump_file, "  Deleted dead store '");
341
              print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
342
              fprintf (dump_file, "'\n");
343
            }
344
          /* Then we need to fix the operand of the consuming stmt.  */
345
          FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
346
            {
347
              single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
348
              SET_USE (use_p, USE_FROM_PTR (var2));
349
            }
350
          /* Remove the dead store.  */
351
          bsi_remove (&bsi, true);
352
 
353
          /* And release any SSA_NAMEs set in this statement back to the
354
             SSA_NAME manager.  */
355
          release_defs (stmt);
356
        }
357
 
358
      record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
359
    }
360
}
361
 
362
/* Record that we have seen the PHIs at the start of BB which correspond
363
   to virtual operands.  */
364
static void
365
dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
366
{
367
  struct dse_block_local_data *bd
368
    = VEC_last (void_p, walk_data->block_data_stack);
369
  struct dse_global_data *dse_gd = walk_data->global_data;
370
  tree phi;
371
 
372
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
373
    if (!is_gimple_reg (PHI_RESULT (phi)))
374
      record_voperand_set (dse_gd->stores,
375
                           &bd->stores,
376
                           get_stmt_uid (phi));
377
}
378
 
379
static void
380
dse_finalize_block (struct dom_walk_data *walk_data,
381
                    basic_block bb ATTRIBUTE_UNUSED)
382
{
383
  struct dse_block_local_data *bd
384
    = VEC_last (void_p, walk_data->block_data_stack);
385
  struct dse_global_data *dse_gd = walk_data->global_data;
386
  bitmap stores = dse_gd->stores;
387
  unsigned int i;
388
  bitmap_iterator bi;
389
 
390
  /* Unwind the stores noted in this basic block.  */
391
  if (bd->stores)
392
    EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
393
      {
394
        bitmap_clear_bit (stores, i);
395
      }
396
}
397
 
398
static unsigned int
399
tree_ssa_dse (void)
400
{
401
  struct dom_walk_data walk_data;
402
  struct dse_global_data dse_gd;
403
  basic_block bb;
404
 
405
  /* Create a UID for each statement in the function.  Ordering of the
406
     UIDs is not important for this pass.  */
407
  max_stmt_uid = 0;
408
  FOR_EACH_BB (bb)
409
    {
410
      block_stmt_iterator bsi;
411
 
412
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
413
        stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
414
    }
415
 
416
  /* We might consider making this a property of each pass so that it
417
     can be [re]computed on an as-needed basis.  Particularly since
418
     this pass could be seen as an extension of DCE which needs post
419
     dominators.  */
420
  calculate_dominance_info (CDI_POST_DOMINATORS);
421
 
422
  /* Dead store elimination is fundamentally a walk of the post-dominator
423
     tree and a backwards walk of statements within each block.  */
424
  walk_data.walk_stmts_backward = true;
425
  walk_data.dom_direction = CDI_POST_DOMINATORS;
426
  walk_data.initialize_block_local_data = dse_initialize_block_local_data;
427
  walk_data.before_dom_children_before_stmts = NULL;
428
  walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
429
  walk_data.before_dom_children_after_stmts = dse_record_phis;
430
  walk_data.after_dom_children_before_stmts = NULL;
431
  walk_data.after_dom_children_walk_stmts = NULL;
432
  walk_data.after_dom_children_after_stmts = dse_finalize_block;
433
  walk_data.interesting_blocks = NULL;
434
 
435
  walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
436
 
437
  /* This is the main hash table for the dead store elimination pass.  */
438
  dse_gd.stores = BITMAP_ALLOC (NULL);
439
  walk_data.global_data = &dse_gd;
440
 
441
  /* Initialize the dominator walker.  */
442
  init_walk_dominator_tree (&walk_data);
443
 
444
  /* Recursively walk the dominator tree.  */
445
  walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
446
 
447
  /* Finalize the dominator walker.  */
448
  fini_walk_dominator_tree (&walk_data);
449
 
450
  /* Release the main bitmap.  */
451
  BITMAP_FREE (dse_gd.stores);
452
 
453
  /* For now, just wipe the post-dominator information.  */
454
  free_dominance_info (CDI_POST_DOMINATORS);
455
  return 0;
456
}
457
 
458
static bool
459
gate_dse (void)
460
{
461
  return flag_tree_dse != 0;
462
}
463
 
464
struct tree_opt_pass pass_dse = {
465
  "dse",                        /* name */
466
  gate_dse,                     /* gate */
467
  tree_ssa_dse,                 /* execute */
468
  NULL,                         /* sub */
469
  NULL,                         /* next */
470
  0,                             /* static_pass_number */
471
  TV_TREE_DSE,                  /* tv_id */
472
  PROP_cfg
473
    | PROP_ssa
474
    | PROP_alias,               /* properties_required */
475
  0,                             /* properties_provided */
476
  0,                             /* properties_destroyed */
477
  0,                             /* todo_flags_start */
478
  TODO_dump_func
479
    | TODO_ggc_collect
480
    | TODO_verify_ssa,          /* todo_flags_finish */
481
 
482
};

powered by: WebSVN 2.1.0

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