OSDN Git Service

315b5507b711e9a18e58dd38b7aa23f14bcd9452
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dse.c
1 /* Dead store elimination
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
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 "ggc.h"
26 #include "tree.h"
27 #include "rtl.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 "domwalk.h"
36 #include "flags.h"
37 #include "langhooks.h"
38
39 /* This file implements dead store elimination.
40
41    A dead store is a store into a memory location which will later be
42    overwritten by another store without any intervening loads.  In this
43    case the earlier store can be deleted.
44
45    In our SSA + virtual operand world we use immediate uses of virtual
46    operands to detect dead stores.  If a store's virtual definition
47    is used precisely once by a later store to the same location which
48    post dominates the first store, then the first store is dead. 
49
50    The single use of the store's virtual definition ensures that
51    there are no intervening aliased loads and the requirement that
52    the second load post dominate the first ensures that if the earlier
53    store executes, then the later stores will execute before the function
54    exits.
55
56    It may help to think of this as first moving the earlier store to
57    the point immediately before the later store.  Again, the single
58    use of the virtual definition and the post-dominance relationship
59    ensure that such movement would be safe.  Clearly if there are 
60    back to back stores, then the second is redundant.
61
62    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
63    may also help in understanding this code since it discusses the
64    relationship between dead store and redundant load elimination.  In
65    fact, they are the same transformation applied to different views of
66    the CFG.  */
67
68
69 struct dse_global_data
70 {
71   /* This is the global bitmap for store statements.
72
73      Each statement has a unique ID.  When we encounter a store statement
74      that we want to record, set the bit corresponding to the statement's
75      unique ID in this bitmap.  */
76   bitmap stores;
77 };
78
79 /* We allocate a bitmap-per-block for stores which are encountered
80    during the scan of that block.  This allows us to restore the 
81    global bitmap of stores when we finish processing a block.  */
82 struct dse_block_local_data
83 {
84   bitmap stores;
85 };
86
87 static bool gate_dse (void);
88 static unsigned int tree_ssa_dse (void);
89 static void dse_initialize_block_local_data (struct dom_walk_data *,
90                                              basic_block,
91                                              bool);
92 static void dse_optimize_stmt (struct dom_walk_data *,
93                                basic_block,
94                                gimple_stmt_iterator);
95 static void dse_record_phis (struct dom_walk_data *, basic_block);
96 static void dse_finalize_block (struct dom_walk_data *, basic_block);
97 static void record_voperand_set (bitmap, bitmap *, unsigned int);
98
99 /* Returns uid of statement STMT.  */
100
101 static unsigned
102 get_stmt_uid (gimple stmt)
103 {
104   if (gimple_code (stmt) == GIMPLE_PHI)
105     return SSA_NAME_VERSION (gimple_phi_result (stmt))
106            + gimple_stmt_max_uid (cfun);
107
108   return gimple_uid (stmt);
109 }
110
111 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
112
113 static void
114 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
115 {
116   /* Lazily allocate the bitmap.  Note that we do not get a notification
117      when the block local data structures die, so we allocate the local
118      bitmap backed by the GC system.  */
119   if (*local == NULL)
120     *local = BITMAP_GGC_ALLOC ();
121
122   /* Set the bit in the local and global bitmaps.  */
123   bitmap_set_bit (*local, uid);
124   bitmap_set_bit (global, uid);
125 }
126
127 /* Initialize block local data structures.  */
128
129 static void
130 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
131                                  basic_block bb ATTRIBUTE_UNUSED,
132                                  bool recycled)
133 {
134   struct dse_block_local_data *bd
135     = (struct dse_block_local_data *)
136         VEC_last (void_p, walk_data->block_data_stack);
137
138   /* If we are given a recycled block local data structure, ensure any
139      bitmap associated with the block is cleared.  */
140   if (recycled)
141     {
142       if (bd->stores)
143         bitmap_clear (bd->stores);
144     }
145 }
146
147 /* A helper of dse_optimize_stmt.
148    Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
149    may prove STMT to be dead.
150    Return TRUE if the above conditions are met, otherwise FALSE.  */
151
152 static bool
153 dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
154 {
155   gimple temp;
156   unsigned cnt = 0;
157
158   *use_stmt = NULL;
159
160   /* Find the first dominated statement that clobbers (part of) the
161      memory stmt stores to with no intermediate statement that may use
162      part of the memory stmt stores.  That is, find a store that may
163      prove stmt to be a dead store.  */
164   temp = stmt;
165   do
166     {
167       gimple prev, use_stmt;
168       imm_use_iterator ui;
169       bool fail = false;
170       tree defvar;
171
172       /* Limit stmt walking to be linear in the number of possibly
173          dead stores.  */
174       if (++cnt > 256)
175         return false;
176
177       if (gimple_code (temp) == GIMPLE_PHI)
178         defvar = PHI_RESULT (temp);
179       else
180         defvar = gimple_vdef (temp);
181       prev = temp;
182       temp = NULL;
183       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
184         {
185           cnt++;
186
187           /* In simple cases we can look through PHI nodes, but we
188              have to be careful with loops and with memory references
189              containing operands that are also operands of PHI nodes.
190              See gcc.c-torture/execute/20051110-*.c.  */
191           if (gimple_code (use_stmt) == GIMPLE_PHI)
192             {
193               if (temp
194                   /* We can look through PHIs to post-dominated regions
195                      without worrying if the use not also dominates prev
196                      (in which case it would be a loop PHI with the use
197                      in a latch block).  */
198                   || gimple_bb (prev) == gimple_bb (use_stmt)
199                   || !dominated_by_p (CDI_POST_DOMINATORS,
200                                       gimple_bb (prev), gimple_bb (use_stmt))
201                   || dominated_by_p (CDI_DOMINATORS,
202                                      gimple_bb (prev), gimple_bb (use_stmt)))
203                 {
204                   fail = true;
205                   BREAK_FROM_IMM_USE_STMT (ui);
206                 }
207               temp = use_stmt;
208             }
209           /* If the statement is a use the store is not dead.  */
210           else if (ref_maybe_used_by_stmt_p (use_stmt,
211                                              gimple_assign_lhs (stmt)))
212             {
213               fail = true;
214               BREAK_FROM_IMM_USE_STMT (ui);
215             }
216           /* If this is a store, remember it or bail out if we have
217              multiple ones (the will be in different CFG parts then).  */
218           else if (gimple_vdef (use_stmt))
219             {
220               if (temp)
221                 {
222                   fail = true;
223                   BREAK_FROM_IMM_USE_STMT (ui);
224                 }
225               temp = use_stmt;
226             }
227         }
228
229       if (fail)
230         return false;
231
232       /* If we didn't find any definition this means the store is dead
233          if it isn't a store to global reachable memory.  In this case
234          just pretend the stmt makes itself dead.  Otherwise fail.  */
235       if (!temp)
236         {
237           if (is_hidden_global_store (stmt))
238             return false;
239
240           temp = stmt;
241           break;
242         }
243     }
244   /* We deliberately stop on clobbering statements and not only on
245      killing ones to make walking cheaper.  Otherwise we can just
246      continue walking until both stores have equal reference trees.  */
247   while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt)));
248
249   if (!is_gimple_assign (temp))
250     return false;
251
252   *use_stmt = temp;
253
254   return true;
255 }
256
257
258 /* Attempt to eliminate dead stores in the statement referenced by BSI.
259
260    A dead store is a store into a memory location which will later be
261    overwritten by another store without any intervening loads.  In this
262    case the earlier store can be deleted.
263
264    In our SSA + virtual operand world we use immediate uses of virtual
265    operands to detect dead stores.  If a store's virtual definition
266    is used precisely once by a later store to the same location which
267    post dominates the first store, then the first store is dead.  */
268
269 static void
270 dse_optimize_stmt (struct dom_walk_data *walk_data,
271                    basic_block bb ATTRIBUTE_UNUSED,
272                    gimple_stmt_iterator gsi)
273 {
274   struct dse_block_local_data *bd
275     = (struct dse_block_local_data *)
276         VEC_last (void_p, walk_data->block_data_stack);
277   struct dse_global_data *dse_gd
278     = (struct dse_global_data *) walk_data->global_data;
279   gimple stmt = gsi_stmt (gsi);
280
281   /* If this statement has no virtual defs, then there is nothing
282      to do.  */
283   if (!gimple_vdef (stmt))
284     return;
285
286   /* We know we have virtual definitions.  If this is a GIMPLE_ASSIGN
287      that's not also a function call, then record it into our table.  */
288   if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
289     return;
290
291   if (gimple_has_volatile_ops (stmt))
292     return;
293
294   if (is_gimple_assign (stmt))
295     {
296       gimple use_stmt;
297
298       record_voperand_set (dse_gd->stores, &bd->stores, gimple_uid (stmt));
299
300       if (!dse_possible_dead_store_p (stmt, &use_stmt))
301         return;
302
303       /* If we have precisely one immediate use at this point and the
304          stores are to the same memory location or there is a chain of
305          virtual uses from stmt and the stmt which stores to that same
306          memory location, then we may have found redundant store.  */
307       if (bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
308           && operand_equal_p (gimple_assign_lhs (stmt),
309                               gimple_assign_lhs (use_stmt), 0))
310         {
311           /* If use_stmt is or might be a nop assignment, e.g. for
312              struct { ... } S a, b, *p; ...
313              b = a; b = b;
314              or
315              b = a; b = *p; where p might be &b,
316              or
317              *p = a; *p = b; where p might be &b,
318              or
319              *p = *u; *p = *v; where p might be v, then USE_STMT
320              acts as a use as well as definition, so store in STMT
321              is not dead.  */
322           if (stmt != use_stmt
323               && !is_gimple_reg (gimple_assign_rhs1 (use_stmt))
324               && !is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))
325               /* ???  Should {} be invariant?  */
326               && gimple_assign_rhs_code (use_stmt) != CONSTRUCTOR
327               && refs_may_alias_p (gimple_assign_lhs (use_stmt),
328                                    gimple_assign_rhs1 (use_stmt)))
329             return;
330
331           if (dump_file && (dump_flags & TDF_DETAILS))
332             {
333               fprintf (dump_file, "  Deleted dead store '");
334               print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0);
335               fprintf (dump_file, "'\n");
336             }
337
338           /* Then we need to fix the operand of the consuming stmt.  */
339           unlink_stmt_vdef (stmt);
340
341           /* Remove the dead store.  */
342           gsi_remove (&gsi, true);
343
344           /* And release any SSA_NAMEs set in this statement back to the
345              SSA_NAME manager.  */
346           release_defs (stmt);
347         }
348     }
349 }
350
351 /* Record that we have seen the PHIs at the start of BB which correspond
352    to virtual operands.  */
353 static void
354 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
355 {
356   struct dse_block_local_data *bd
357     = (struct dse_block_local_data *)
358         VEC_last (void_p, walk_data->block_data_stack);
359   struct dse_global_data *dse_gd
360     = (struct dse_global_data *) walk_data->global_data;
361   gimple phi;
362   gimple_stmt_iterator gsi;
363
364   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
365     {
366       phi = gsi_stmt (gsi);
367       if (!is_gimple_reg (gimple_phi_result (phi)))
368         record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi));
369     }
370 }
371
372 static void
373 dse_finalize_block (struct dom_walk_data *walk_data,
374                     basic_block bb ATTRIBUTE_UNUSED)
375 {
376   struct dse_block_local_data *bd
377     = (struct dse_block_local_data *)
378         VEC_last (void_p, walk_data->block_data_stack);
379   struct dse_global_data *dse_gd
380     = (struct dse_global_data *) walk_data->global_data;
381   bitmap stores = dse_gd->stores;
382   unsigned int i;
383   bitmap_iterator bi;
384
385   /* Unwind the stores noted in this basic block.  */
386   if (bd->stores)
387     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
388       {
389         bitmap_clear_bit (stores, i);
390       }
391 }
392
393 /* Main entry point.  */
394
395 static unsigned int
396 tree_ssa_dse (void)
397 {
398   struct dom_walk_data walk_data;
399   struct dse_global_data dse_gd;
400
401   renumber_gimple_stmt_uids ();
402
403   /* We might consider making this a property of each pass so that it
404      can be [re]computed on an as-needed basis.  Particularly since
405      this pass could be seen as an extension of DCE which needs post
406      dominators.  */
407   calculate_dominance_info (CDI_POST_DOMINATORS);
408   calculate_dominance_info (CDI_DOMINATORS);
409
410   /* Dead store elimination is fundamentally a walk of the post-dominator
411      tree and a backwards walk of statements within each block.  */
412   walk_data.walk_stmts_backward = true;
413   walk_data.dom_direction = CDI_POST_DOMINATORS;
414   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
415   walk_data.before_dom_children_before_stmts = NULL;
416   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
417   walk_data.before_dom_children_after_stmts = dse_record_phis;
418   walk_data.after_dom_children_before_stmts = NULL;
419   walk_data.after_dom_children_walk_stmts = NULL;
420   walk_data.after_dom_children_after_stmts = dse_finalize_block;
421   walk_data.interesting_blocks = NULL;
422
423   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
424
425   /* This is the main hash table for the dead store elimination pass.  */
426   dse_gd.stores = BITMAP_ALLOC (NULL);
427   walk_data.global_data = &dse_gd;
428
429   /* Initialize the dominator walker.  */
430   init_walk_dominator_tree (&walk_data);
431
432   /* Recursively walk the dominator tree.  */
433   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
434
435   /* Finalize the dominator walker.  */
436   fini_walk_dominator_tree (&walk_data);
437
438   /* Release the main bitmap.  */
439   BITMAP_FREE (dse_gd.stores);
440
441   /* For now, just wipe the post-dominator information.  */
442   free_dominance_info (CDI_POST_DOMINATORS);
443   return 0;
444 }
445
446 static bool
447 gate_dse (void)
448 {
449   return flag_tree_dse != 0;
450 }
451
452 struct gimple_opt_pass pass_dse = 
453 {
454  {
455   GIMPLE_PASS,
456   "dse",                        /* name */
457   gate_dse,                     /* gate */
458   tree_ssa_dse,                 /* execute */
459   NULL,                         /* sub */
460   NULL,                         /* next */
461   0,                            /* static_pass_number */
462   TV_TREE_DSE,                  /* tv_id */
463   PROP_cfg
464     | PROP_ssa
465     | PROP_alias,               /* properties_required */
466   0,                            /* properties_provided */
467   0,                            /* properties_destroyed */
468   0,                            /* todo_flags_start */
469   TODO_dump_func
470     | TODO_ggc_collect
471     | TODO_verify_ssa           /* todo_flags_finish */
472  }
473 };
474