OSDN Git Service

* configure.host (darwin): On darwin8 or later, no need to build
[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   stmt_ann_t ann = stmt_ann (stmt);
134   v_may_def_optype v_may_defs;
135   unsigned int i;
136   int j;
137
138   get_stmt_operands (stmt);
139   v_may_defs = V_MAY_DEF_OPS (ann);
140
141   /* Walk each V_MAY_DEF in STMT.  */
142   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
143     {
144       tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
145
146       /* Find any uses in the PHI which match V_MAY_DEF and replace
147          them with the appropriate V_MAY_DEF_OP.  */
148       for (j = 0; j < PHI_NUM_ARGS (phi); j++)
149         if (v_may_def == PHI_ARG_DEF (phi, j))
150           SET_PHI_ARG_DEF (phi, j, V_MAY_DEF_OP (v_may_defs, i));
151     }
152 }
153
154 /* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs 
155    in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2.  */
156
157 static void
158 fix_stmt_v_may_defs (tree stmt1, tree stmt2)
159 {
160   stmt_ann_t ann1 = stmt_ann (stmt1);
161   stmt_ann_t ann2 = stmt_ann (stmt2);
162   v_may_def_optype v_may_defs1;
163   v_may_def_optype v_may_defs2;
164   unsigned int i, j;
165
166   get_stmt_operands (stmt1);
167   get_stmt_operands (stmt2);
168   v_may_defs1 = V_MAY_DEF_OPS (ann1);
169   v_may_defs2 = V_MAY_DEF_OPS (ann2);
170
171   /* Walk each V_MAY_DEF_OP in stmt1.  */
172   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs1); i++)
173     {
174       tree v_may_def1 = V_MAY_DEF_OP (v_may_defs1, i);
175
176       /* Find the appropriate V_MAY_DEF_RESULT in STMT2.  */
177       for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs2); j++)
178         {
179           if (v_may_def1 == V_MAY_DEF_RESULT (v_may_defs2, j))
180             {
181               /* Update.  */
182               SET_V_MAY_DEF_OP (v_may_defs1, i, V_MAY_DEF_OP (v_may_defs2, j));
183               break;
184             }
185         }
186
187       /* If we did not find a corresponding V_MAY_DEF_RESULT, then something
188          has gone terribly wrong.  */
189       gcc_assert (j != NUM_V_MAY_DEFS (v_may_defs2));
190     }
191 }
192
193
194 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
195 static void
196 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
197 {
198   /* Lazily allocate the bitmap.  Note that we do not get a notification
199      when the block local data structures die, so we allocate the local
200      bitmap backed by the GC system.  */
201   if (*local == NULL)
202     *local = BITMAP_GGC_ALLOC ();
203
204   /* Set the bit in the local and global bitmaps.  */
205   bitmap_set_bit (*local, uid);
206   bitmap_set_bit (global, uid);
207 }
208 /* Initialize block local data structures.  */
209
210 static void
211 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
212                                  basic_block bb ATTRIBUTE_UNUSED,
213                                  bool recycled)
214 {
215   struct dse_block_local_data *bd
216     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
217
218   /* If we are given a recycled block local data structure, ensure any
219      bitmap associated with the block is cleared.  */
220   if (recycled)
221     {
222       if (bd->stores)
223         bitmap_clear (bd->stores);
224     }
225 }
226
227 /* Attempt to eliminate dead stores in the statement referenced by BSI.
228
229    A dead store is a store into a memory location which will later be
230    overwritten by another store without any intervening loads.  In this
231    case the earlier store can be deleted.
232
233    In our SSA + virtual operand world we use immediate uses of virtual
234    operands to detect dead stores.  If a store's virtual definition
235    is used precisely once by a later store to the same location which
236    post dominates the first store, then the first store is dead.  */
237
238 static void
239 dse_optimize_stmt (struct dom_walk_data *walk_data,
240                    basic_block bb ATTRIBUTE_UNUSED,
241                    block_stmt_iterator bsi)
242 {
243   struct dse_block_local_data *bd
244     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
245   struct dse_global_data *dse_gd = walk_data->global_data;
246   tree stmt = bsi_stmt (bsi);
247   stmt_ann_t ann = stmt_ann (stmt);
248   v_may_def_optype v_may_defs;
249
250   get_stmt_operands (stmt);
251   v_may_defs = V_MAY_DEF_OPS (ann);
252
253   /* If this statement has no virtual uses, then there is nothing
254      to do.  */
255   if (NUM_V_MAY_DEFS (v_may_defs) == 0)
256     return;
257
258   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
259      not also a function call, then record it into our table.  */
260   if (get_call_expr_in (stmt))
261     return;
262
263   if (ann->has_volatile_ops)
264     return;
265
266   if (TREE_CODE (stmt) == MODIFY_EXPR)
267     {
268       dataflow_t df = get_immediate_uses (stmt);
269       unsigned int num_uses = num_immediate_uses (df);
270       tree use;
271       tree skipped_phi;
272
273
274       /* If there are no uses then there is nothing left to do.  */
275       if (num_uses == 0)
276         {
277           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
278           return;
279         }
280
281       use = immediate_use (df, 0);
282       skipped_phi = NULL;
283
284       /* Skip through any PHI nodes we have already seen if the PHI
285          represents the only use of this store.
286
287          Note this does not handle the case where the store has
288          multiple V_MAY_DEFs which all reach a set of PHI nodes in the
289          same block.  */
290       while (num_uses == 1
291              && TREE_CODE (use) == PHI_NODE
292              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use)))
293         {
294           /* Record the first PHI we skip so that we can fix its
295              uses if we find that STMT is a dead store.  */
296           if (!skipped_phi)
297             skipped_phi = use;
298
299           /* Skip past this PHI and loop again in case we had a PHI
300              chain.  */
301           df = get_immediate_uses (use);
302           num_uses = num_immediate_uses (df);
303           use = immediate_use (df, 0);
304         }
305
306       /* If we have precisely one immediate use at this point, then we may
307          have found redundant store.  */
308       if (num_uses == 1
309           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use))
310           && operand_equal_p (TREE_OPERAND (stmt, 0),
311                               TREE_OPERAND (use, 0), 0))
312         {
313           /* We need to fix the operands if either the first PHI we
314              skipped, or the store which we are not deleting if we did
315              not skip any PHIs.  */
316           if (skipped_phi)
317             fix_phi_uses (skipped_phi, stmt);
318           else
319             fix_stmt_v_may_defs (use, stmt);
320
321           if (dump_file && (dump_flags & TDF_DETAILS))
322             {
323               fprintf (dump_file, "  Deleted dead store '");
324               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
325               fprintf (dump_file, "'\n");
326             }
327
328           /* Any immediate uses which reference STMT need to instead
329              reference the new consumer, either SKIPPED_PHI or USE.  
330              This allows us to cascade dead stores.  */
331           redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);
332
333           /* Be sure to remove any dataflow information attached to
334              this statement.  */
335           free_df_for_stmt (stmt);
336
337           /* And release any SSA_NAMEs set in this statement back to the
338              SSA_NAME manager.  */
339           release_defs (stmt);
340
341           /* Finally remove the dead store.  */
342           bsi_remove (&bsi);
343         }
344
345       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
346     }
347 }
348
349 /* Record that we have seen the PHIs at the start of BB which correspond
350    to virtual operands.  */
351 static void
352 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
353 {
354   struct dse_block_local_data *bd
355     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
356   struct dse_global_data *dse_gd = walk_data->global_data;
357   tree phi;
358
359   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
360     if (need_imm_uses_for (PHI_RESULT (phi)))
361       record_voperand_set (dse_gd->stores,
362                            &bd->stores,
363                            get_stmt_uid (phi));
364 }
365
366 static void
367 dse_finalize_block (struct dom_walk_data *walk_data,
368                     basic_block bb ATTRIBUTE_UNUSED)
369 {
370   struct dse_block_local_data *bd
371     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
372   struct dse_global_data *dse_gd = walk_data->global_data;
373   bitmap stores = dse_gd->stores;
374   unsigned int i;
375   bitmap_iterator bi;
376
377   /* Unwind the stores noted in this basic block.  */
378   if (bd->stores)
379     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
380       {
381         bitmap_clear_bit (stores, i);
382       }
383 }
384
385 static void
386 tree_ssa_dse (void)
387 {
388   struct dom_walk_data walk_data;
389   struct dse_global_data dse_gd;
390   basic_block bb;
391
392   /* Create a UID for each statement in the function.  Ordering of the
393      UIDs is not important for this pass.  */
394   max_stmt_uid = 0;
395   FOR_EACH_BB (bb)
396     {
397       block_stmt_iterator bsi;
398
399       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
400         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
401     }
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
409   /* We also need immediate use information for virtual operands.  */
410   compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
411
412   /* Dead store elimination is fundamentally a walk of the post-dominator
413      tree and a backwards walk of statements within each block.  */
414   walk_data.walk_stmts_backward = true;
415   walk_data.dom_direction = CDI_POST_DOMINATORS;
416   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
417   walk_data.before_dom_children_before_stmts = NULL;
418   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
419   walk_data.before_dom_children_after_stmts = dse_record_phis;
420   walk_data.after_dom_children_before_stmts = NULL;
421   walk_data.after_dom_children_walk_stmts = NULL;
422   walk_data.after_dom_children_after_stmts = dse_finalize_block;
423
424   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
425
426   /* This is the main hash table for the dead store elimination pass.  */
427   dse_gd.stores = BITMAP_XMALLOC ();
428   walk_data.global_data = &dse_gd;
429
430   /* Initialize the dominator walker.  */
431   init_walk_dominator_tree (&walk_data);
432
433   /* Recursively walk the dominator tree.  */
434   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
435
436   /* Finalize the dominator walker.  */
437   fini_walk_dominator_tree (&walk_data);
438
439   /* Release the main bitmap.  */
440   BITMAP_XFREE (dse_gd.stores);
441
442   /* Free dataflow information.  It's probably out of date now anyway.  */
443   free_df ();
444
445   /* For now, just wipe the post-dominator information.  */
446   free_dominance_info (CDI_POST_DOMINATORS);
447 }
448
449 static bool
450 gate_dse (void)
451 {
452   return flag_tree_dse != 0;
453 }
454
455 struct tree_opt_pass pass_dse = {
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 | PROP_ssa
464     | PROP_alias,               /* properties_required */
465   0,                            /* properties_provided */
466   0,                            /* properties_destroyed */
467   0,                            /* todo_flags_start */
468   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
469   | TODO_verify_ssa,
470   0                                     /* letter */
471 };