OSDN Git Service

* tree-ssa-dse.c (fix_phi_uses): Use SSA operand iterators.
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dse.c
1 /* Dead store elimination
2    Copyright (C) 2004 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 2, 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 COPYING.  If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "errors.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "basic-block.h"
31 #include "timevar.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
36 #include "domwalk.h"
37 #include "flags.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 void 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                                block_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 fix_phi_uses (tree, tree);
98 static void fix_stmt_v_may_defs (tree, tree);
99 static void record_voperand_set (bitmap, bitmap *, unsigned int);
100
101 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
102                                    nodes are assigned using the versions of
103                                    ssa names they define.  */
104
105 /* Returns uid of statement STMT.  */
106
107 static unsigned
108 get_stmt_uid (tree stmt)
109 {
110   if (TREE_CODE (stmt) == PHI_NODE)
111     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
112
113   return stmt_ann (stmt)->uid;
114 }
115
116 /* Function indicating whether we ought to include information for 'var'
117    when calculating immediate uses.  For this pass we only want use
118    information for virtual variables.  */
119
120 static bool
121 need_imm_uses_for (tree var)
122 {
123   return !is_gimple_reg (var);
124 }
125
126
127 /* Replace uses in PHI which match V_MAY_DEF_RESULTs in STMT with the 
128    corresponding V_MAY_DEF_OP in STMT.  */
129
130 static void
131 fix_phi_uses (tree phi, tree stmt)
132 {
133   use_operand_p use_p;
134   def_operand_p def_p;
135   ssa_op_iter iter;
136   int i;
137
138   get_stmt_operands (stmt);
139
140   FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
141     {
142       tree v_may_def = DEF_FROM_PTR (def_p);
143       tree v_may_use = USE_FROM_PTR (use_p);
144
145       /* Find any uses in the PHI which match V_MAY_DEF and replace
146          them with the appropriate V_MAY_DEF_OP.  */
147       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
148         if (v_may_def == PHI_ARG_DEF (phi, i))
149           SET_PHI_ARG_DEF (phi, i, v_may_use);
150     }
151 }
152
153 /* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs 
154    in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2.  */
155
156 static void
157 fix_stmt_v_may_defs (tree stmt1, tree stmt2)
158 {
159   bool found = false;
160   ssa_op_iter iter1;
161   ssa_op_iter iter2;
162   use_operand_p use1_p, use2_p;
163   def_operand_p def1_p, def2_p;
164
165   get_stmt_operands (stmt1);
166   get_stmt_operands (stmt2);
167
168   /* Walk each V_MAY_DEF_OP in stmt1.  */
169   FOR_EACH_SSA_MAYDEF_OPERAND (def1_p, use1_p, stmt1, iter1)
170     {
171       tree use = USE_FROM_PTR (use1_p);
172
173       /* Find the appropriate V_MAY_DEF_RESULT in STMT2.  */
174       FOR_EACH_SSA_MAYDEF_OPERAND (def2_p, use2_p, stmt2, iter2)
175         {
176           tree def = DEF_FROM_PTR (def2_p);
177           if (use == def)
178             {
179               /* Update.  */
180               SET_USE (use1_p, USE_FROM_PTR (use2_p));
181               found = true;
182               break;
183             }
184         }
185
186       /* If we did not find a corresponding V_MAY_DEF_RESULT,
187          then something has gone terribly wrong.  */
188       gcc_assert (found);
189     }
190 }
191
192
193 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
194 static void
195 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
196 {
197   /* Lazily allocate the bitmap.  Note that we do not get a notification
198      when the block local data structures die, so we allocate the local
199      bitmap backed by the GC system.  */
200   if (*local == NULL)
201     *local = BITMAP_GGC_ALLOC ();
202
203   /* Set the bit in the local and global bitmaps.  */
204   bitmap_set_bit (*local, uid);
205   bitmap_set_bit (global, uid);
206 }
207 /* Initialize block local data structures.  */
208
209 static void
210 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
211                                  basic_block bb ATTRIBUTE_UNUSED,
212                                  bool recycled)
213 {
214   struct dse_block_local_data *bd
215     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
216
217   /* If we are given a recycled block local data structure, ensure any
218      bitmap associated with the block is cleared.  */
219   if (recycled)
220     {
221       if (bd->stores)
222         bitmap_clear (bd->stores);
223     }
224 }
225
226 /* Attempt to eliminate dead stores in the statement referenced by BSI.
227
228    A dead store is a store into a memory location which will later be
229    overwritten by another store without any intervening loads.  In this
230    case the earlier store can be deleted.
231
232    In our SSA + virtual operand world we use immediate uses of virtual
233    operands to detect dead stores.  If a store's virtual definition
234    is used precisely once by a later store to the same location which
235    post dominates the first store, then the first store is dead.  */
236
237 static void
238 dse_optimize_stmt (struct dom_walk_data *walk_data,
239                    basic_block bb ATTRIBUTE_UNUSED,
240                    block_stmt_iterator bsi)
241 {
242   struct dse_block_local_data *bd
243     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
244   struct dse_global_data *dse_gd = walk_data->global_data;
245   tree stmt = bsi_stmt (bsi);
246   stmt_ann_t ann = stmt_ann (stmt);
247   v_may_def_optype v_may_defs;
248
249   get_stmt_operands (stmt);
250   v_may_defs = V_MAY_DEF_OPS (ann);
251
252   /* If this statement has no virtual uses, then there is nothing
253      to do.  */
254   if (NUM_V_MAY_DEFS (v_may_defs) == 0)
255     return;
256
257   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
258      not also a function call, then record it into our table.  */
259   if (get_call_expr_in (stmt))
260     return;
261
262   if (ann->has_volatile_ops)
263     return;
264
265   if (TREE_CODE (stmt) == MODIFY_EXPR)
266     {
267       dataflow_t df = get_immediate_uses (stmt);
268       unsigned int num_uses = num_immediate_uses (df);
269       tree use;
270       tree skipped_phi;
271
272       /* If there are no uses then there is nothing left to do.  */
273       if (num_uses == 0)
274         {
275           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
276           return;
277         }
278
279       use = immediate_use (df, 0);
280       skipped_phi = NULL;
281
282       /* Skip through any PHI nodes we have already seen if the PHI
283          represents the only use of this store.
284
285          Note this does not handle the case where the store has
286          multiple V_MAY_DEFs which all reach a set of PHI nodes in the
287          same block.  */
288       while (num_uses == 1
289              && TREE_CODE (use) == PHI_NODE
290              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use)))
291         {
292           /* Record the first PHI we skip so that we can fix its
293              uses if we find that STMT is a dead store.  */
294           if (!skipped_phi)
295             skipped_phi = use;
296
297           /* Skip past this PHI and loop again in case we had a PHI
298              chain.  */
299           df = get_immediate_uses (use);
300           num_uses = num_immediate_uses (df);
301           use = immediate_use (df, 0);
302         }
303
304       /* If we have precisely one immediate use at this point, then we may
305          have found redundant store.  */
306       if (num_uses == 1
307           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use))
308           && operand_equal_p (TREE_OPERAND (stmt, 0),
309                               TREE_OPERAND (use, 0), 0))
310         {
311           /* We need to fix the operands if either the first PHI we
312              skipped, or the store which we are not deleting if we did
313              not skip any PHIs.  */
314           if (skipped_phi)
315             fix_phi_uses (skipped_phi, stmt);
316           else
317             fix_stmt_v_may_defs (use, stmt);
318
319           if (dump_file && (dump_flags & TDF_DETAILS))
320             {
321               fprintf (dump_file, "  Deleted dead store '");
322               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
323               fprintf (dump_file, "'\n");
324             }
325
326           /* Any immediate uses which reference STMT need to instead
327              reference the new consumer, either SKIPPED_PHI or USE.  
328              This allows us to cascade dead stores.  */
329           redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);
330
331           /* Be sure to remove any dataflow information attached to
332              this statement.  */
333           free_df_for_stmt (stmt);
334
335           /* And release any SSA_NAMEs set in this statement back to the
336              SSA_NAME manager.  */
337           release_defs (stmt);
338
339           /* Finally remove the dead store.  */
340           bsi_remove (&bsi);
341         }
342
343       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
344     }
345 }
346
347 /* Record that we have seen the PHIs at the start of BB which correspond
348    to virtual operands.  */
349 static void
350 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
351 {
352   struct dse_block_local_data *bd
353     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
354   struct dse_global_data *dse_gd = walk_data->global_data;
355   tree phi;
356
357   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
358     if (need_imm_uses_for (PHI_RESULT (phi)))
359       record_voperand_set (dse_gd->stores,
360                            &bd->stores,
361                            get_stmt_uid (phi));
362 }
363
364 static void
365 dse_finalize_block (struct dom_walk_data *walk_data,
366                     basic_block bb ATTRIBUTE_UNUSED)
367 {
368   struct dse_block_local_data *bd
369     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
370   struct dse_global_data *dse_gd = walk_data->global_data;
371   bitmap stores = dse_gd->stores;
372   unsigned int i;
373   bitmap_iterator bi;
374
375   /* Unwind the stores noted in this basic block.  */
376   if (bd->stores)
377     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
378       {
379         bitmap_clear_bit (stores, i);
380       }
381 }
382
383 static void
384 tree_ssa_dse (void)
385 {
386   struct dom_walk_data walk_data;
387   struct dse_global_data dse_gd;
388   basic_block bb;
389
390   /* Create a UID for each statement in the function.  Ordering of the
391      UIDs is not important for this pass.  */
392   max_stmt_uid = 0;
393   FOR_EACH_BB (bb)
394     {
395       block_stmt_iterator bsi;
396
397       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
398         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
399     }
400
401   /* We might consider making this a property of each pass so that it
402      can be [re]computed on an as-needed basis.  Particularly since
403      this pass could be seen as an extension of DCE which needs post
404      dominators.  */
405   calculate_dominance_info (CDI_POST_DOMINATORS);
406
407   /* We also need immediate use information for virtual operands.  */
408   compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
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
422   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
423
424   /* This is the main hash table for the dead store elimination pass.  */
425   dse_gd.stores = BITMAP_XMALLOC ();
426   walk_data.global_data = &dse_gd;
427
428   /* Initialize the dominator walker.  */
429   init_walk_dominator_tree (&walk_data);
430
431   /* Recursively walk the dominator tree.  */
432   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
433
434   /* Finalize the dominator walker.  */
435   fini_walk_dominator_tree (&walk_data);
436
437   /* Release the main bitmap.  */
438   BITMAP_XFREE (dse_gd.stores);
439
440   /* Free dataflow information.  It's probably out of date now anyway.  */
441   free_df ();
442
443   /* For now, just wipe the post-dominator information.  */
444   free_dominance_info (CDI_POST_DOMINATORS);
445 }
446
447 static bool
448 gate_dse (void)
449 {
450   return flag_tree_dse != 0;
451 }
452
453 struct tree_opt_pass pass_dse = {
454   "dse",                        /* name */
455   gate_dse,                     /* gate */
456   tree_ssa_dse,                 /* execute */
457   NULL,                         /* sub */
458   NULL,                         /* next */
459   0,                            /* static_pass_number */
460   TV_TREE_DSE,                  /* tv_id */
461   PROP_cfg | PROP_ssa
462     | PROP_alias,               /* properties_required */
463   0,                            /* properties_provided */
464   0,                            /* properties_destroyed */
465   0,                            /* todo_flags_start */
466   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
467   | TODO_verify_ssa,
468   0                                     /* letter */
469 };