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