1/* Dead code elimination pass for the GNU compiler.
2   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3   Free Software Foundation, Inc.
4   Contributed by Ben Elliston <bje@redhat.com>
5   and Andrew MacLeod <amacleod@redhat.com>
6   Adapted to use control dependence by Steven Bosscher, SUSE Labs.
7
8This file is part of GCC.
9
10GCC is free software; you can redistribute it and/or modify it
11under the terms of the GNU General Public License as published by the
12Free Software Foundation; either version 3, or (at your option) any
13later version.
14
15GCC is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18for more details.
19
20You should have received a copy of the GNU General Public License
21along with GCC; see the file COPYING3.  If not see
22<http://www.gnu.org/licenses/>.  */
23
24/* Dead code elimination.
25
26   References:
27
28     Building an Optimizing Compiler,
29     Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
30
31     Advanced Compiler Design and Implementation,
32     Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
33
34   Dead-code elimination is the removal of statements which have no
35   impact on the program's output.  "Dead statements" have no impact
36   on the program's output, while "necessary statements" may have
37   impact on the output.
38
39   The algorithm consists of three phases:
40   1. Marking as necessary all statements known to be necessary,
41      e.g. most function calls, writing a value to memory, etc;
42   2. Propagating necessary statements, e.g., the statements
43      giving values to operands in necessary statements; and
44   3. Removing dead statements.  */
45
46#include "config.h"
47#include "system.h"
48#include "coretypes.h"
49#include "tm.h"
50#include "ggc.h"
51
52/* These RTL headers are needed for basic-block.h.  */
53#include "rtl.h"
54#include "tm_p.h"
55#include "hard-reg-set.h"
56#include "obstack.h"
57#include "basic-block.h"
58
59#include "tree.h"
60#include "diagnostic.h"
61#include "tree-flow.h"
62#include "gimple.h"
63#include "tree-dump.h"
64#include "tree-pass.h"
65#include "timevar.h"
66#include "flags.h"
67#include "cfgloop.h"
68#include "tree-scalar-evolution.h"
69
70static struct stmt_stats
71{
72  int total;
73  int total_phis;
74  int removed;
75  int removed_phis;
76} stats;
77
78#define STMT_NECESSARY GF_PLF_1
79
80static VEC(gimple,heap) *worklist;
81
82/* Vector indicating an SSA name has already been processed and marked
83   as necessary.  */
84static sbitmap processed;
85
86/* Vector indicating that last_stmt if a basic block has already been
87   marked as necessary.  */
88static sbitmap last_stmt_necessary;
89
90/* Vector indicating that BB contains statements that are live.  */
91static sbitmap bb_contains_live_stmts;
92
93/* Before we can determine whether a control branch is dead, we need to
94   compute which blocks are control dependent on which edges.
95
96   We expect each block to be control dependent on very few edges so we
97   use a bitmap for each block recording its edges.  An array holds the
98   bitmap.  The Ith bit in the bitmap is set if that block is dependent
99   on the Ith edge.  */
100static bitmap *control_dependence_map;
101
102/* Vector indicating that a basic block has already had all the edges
103   processed that it is control dependent on.  */
104static sbitmap visited_control_parents;
105
106/* TRUE if this pass alters the CFG (by removing control statements).
107   FALSE otherwise.
108
109   If this pass alters the CFG, then it will arrange for the dominators
110   to be recomputed.  */
111static bool cfg_altered;
112
113/* Execute code that follows the macro for each edge (given number
114   EDGE_NUMBER within the CODE) for which the block with index N is
115   control dependent.  */
116#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)	\
117  EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,	\
118			    (EDGE_NUMBER), (BI))
119
120
121/* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
122static inline void
123set_control_dependence_map_bit (basic_block bb, int edge_index)
124{
125  if (bb == ENTRY_BLOCK_PTR)
126    return;
127  gcc_assert (bb != EXIT_BLOCK_PTR);
128  bitmap_set_bit (control_dependence_map[bb->index], edge_index);
129}
130
131/* Clear all control dependences for block BB.  */
132static inline void
133clear_control_dependence_bitmap (basic_block bb)
134{
135  bitmap_clear (control_dependence_map[bb->index]);
136}
137
138
139/* Find the immediate postdominator PDOM of the specified basic block BLOCK.
140   This function is necessary because some blocks have negative numbers.  */
141
142static inline basic_block
143find_pdom (basic_block block)
144{
145  gcc_assert (block != ENTRY_BLOCK_PTR);
146
147  if (block == EXIT_BLOCK_PTR)
148    return EXIT_BLOCK_PTR;
149  else
150    {
151      basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
152      if (! bb)
153	return EXIT_BLOCK_PTR;
154      return bb;
155    }
156}
157
158
159/* Determine all blocks' control dependences on the given edge with edge_list
160   EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
161
162static void
163find_control_dependence (struct edge_list *el, int edge_index)
164{
165  basic_block current_block;
166  basic_block ending_block;
167
168  gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
169
170  if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
171    ending_block = single_succ (ENTRY_BLOCK_PTR);
172  else
173    ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
174
175  for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
176       current_block != ending_block && current_block != EXIT_BLOCK_PTR;
177       current_block = find_pdom (current_block))
178    {
179      edge e = INDEX_EDGE (el, edge_index);
180
181      /* For abnormal edges, we don't make current_block control
182	 dependent because instructions that throw are always necessary
183	 anyway.  */
184      if (e->flags & EDGE_ABNORMAL)
185	continue;
186
187      set_control_dependence_map_bit (current_block, edge_index);
188    }
189}
190
191
192/* Record all blocks' control dependences on all edges in the edge
193   list EL, ala Morgan, Section 3.6.  */
194
195static void
196find_all_control_dependences (struct edge_list *el)
197{
198  int i;
199
200  for (i = 0; i < NUM_EDGES (el); ++i)
201    find_control_dependence (el, i);
202}
203
204/* If STMT is not already marked necessary, mark it, and add it to the
205   worklist if ADD_TO_WORKLIST is true.  */
206static inline void
207mark_stmt_necessary (gimple stmt, bool add_to_worklist)
208{
209  gcc_assert (stmt);
210
211  if (gimple_plf (stmt, STMT_NECESSARY))
212    return;
213
214  if (dump_file && (dump_flags & TDF_DETAILS))
215    {
216      fprintf (dump_file, "Marking useful stmt: ");
217      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
218      fprintf (dump_file, "\n");
219    }
220
221  gimple_set_plf (stmt, STMT_NECESSARY, true);
222  if (add_to_worklist)
223    VEC_safe_push (gimple, heap, worklist, stmt);
224  if (bb_contains_live_stmts && !is_gimple_debug (stmt))
225    SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
226}
227
228
229/* Mark the statement defining operand OP as necessary.  */
230
231static inline void
232mark_operand_necessary (tree op)
233{
234  gimple stmt;
235  int ver;
236
237  gcc_assert (op);
238
239  ver = SSA_NAME_VERSION (op);
240  if (TEST_BIT (processed, ver))
241    {
242      stmt = SSA_NAME_DEF_STMT (op);
243      gcc_assert (gimple_nop_p (stmt)
244		  || gimple_plf (stmt, STMT_NECESSARY));
245      return;
246    }
247  SET_BIT (processed, ver);
248
249  stmt = SSA_NAME_DEF_STMT (op);
250  gcc_assert (stmt);
251
252  if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
253    return;
254
255  if (dump_file && (dump_flags & TDF_DETAILS))
256    {
257      fprintf (dump_file, "marking necessary through ");
258      print_generic_expr (dump_file, op, 0);
259      fprintf (dump_file, " stmt ");
260      print_gimple_stmt (dump_file, stmt, 0, 0);
261    }
262
263  gimple_set_plf (stmt, STMT_NECESSARY, true);
264  if (bb_contains_live_stmts)
265    SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
266  VEC_safe_push (gimple, heap, worklist, stmt);
267}
268
269
270/* Mark STMT as necessary if it obviously is.  Add it to the worklist if
271   it can make other statements necessary.
272
273   If AGGRESSIVE is false, control statements are conservatively marked as
274   necessary.  */
275
276static void
277mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
278{
279  tree lhs = NULL_TREE;
280  /* With non-call exceptions, we have to assume that all statements could
281     throw.  If a statement may throw, it is inherently necessary.  */
282  if (flag_non_call_exceptions
283      && stmt_could_throw_p (stmt))
284    {
285      mark_stmt_necessary (stmt, true);
286      return;
287    }
288
289  /* Statements that are implicitly live.  Most function calls, asm
290     and return statements are required.  Labels and GIMPLE_BIND nodes
291     are kept because they are control flow, and we have no way of
292     knowing whether they can be removed.  DCE can eliminate all the
293     other statements in a block, and CFG can then remove the block
294     and labels.  */
295  switch (gimple_code (stmt))
296    {
297    case GIMPLE_PREDICT:
298    case GIMPLE_LABEL:
299      mark_stmt_necessary (stmt, false);
300      return;
301
302    case GIMPLE_ASM:
303    case GIMPLE_RESX:
304    case GIMPLE_RETURN:
305      mark_stmt_necessary (stmt, true);
306      return;
307
308    case GIMPLE_CALL:
309      /* Most, but not all function calls are required.  Function calls that
310	 produce no result and have no side effects (i.e. const pure
311	 functions) are unnecessary.  */
312      if (gimple_has_side_effects (stmt))
313	{
314	  mark_stmt_necessary (stmt, true);
315	  return;
316	}
317      if (!gimple_call_lhs (stmt))
318        return;
319      lhs = gimple_call_lhs (stmt);
320      /* Fall through */
321
322    case GIMPLE_ASSIGN:
323      if (!lhs)
324        lhs = gimple_assign_lhs (stmt);
325      break;
326
327    case GIMPLE_DEBUG:
328      /* Debug temps without a value are not useful.  ??? If we could
329	 easily locate the debug temp bind stmt for a use thereof,
330	 would could refrain from marking all debug temps here, and
331	 mark them only if they're used.  */
332      if (gimple_debug_bind_has_value_p (stmt)
333	  || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
334	mark_stmt_necessary (stmt, false);
335      return;
336
337    case GIMPLE_GOTO:
338      gcc_assert (!simple_goto_p (stmt));
339      mark_stmt_necessary (stmt, true);
340      return;
341
342    case GIMPLE_COND:
343      gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
344      /* Fall through.  */
345
346    case GIMPLE_SWITCH:
347      if (! aggressive)
348	mark_stmt_necessary (stmt, true);
349      break;
350
351    default:
352      break;
353    }
354
355  /* If the statement has volatile operands, it needs to be preserved.
356     Same for statements that can alter control flow in unpredictable
357     ways.  */
358  if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
359    {
360      mark_stmt_necessary (stmt, true);
361      return;
362    }
363
364  if (is_hidden_global_store (stmt))
365    {
366      mark_stmt_necessary (stmt, true);
367      return;
368    }
369
370  return;
371}
372
373
374/* Make corresponding control dependent edges necessary.  We only
375   have to do this once for each basic block, so we clear the bitmap
376   after we're done.  */
377static void
378mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
379{
380  bitmap_iterator bi;
381  unsigned edge_number;
382
383  gcc_assert (bb != EXIT_BLOCK_PTR);
384
385  if (bb == ENTRY_BLOCK_PTR)
386    return;
387
388  EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
389    {
390      gimple stmt;
391      basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
392
393      if (TEST_BIT (last_stmt_necessary, cd_bb->index))
394	continue;
395      SET_BIT (last_stmt_necessary, cd_bb->index);
396      SET_BIT (bb_contains_live_stmts, cd_bb->index);
397
398      stmt = last_stmt (cd_bb);
399      if (stmt && is_ctrl_stmt (stmt))
400	mark_stmt_necessary (stmt, true);
401    }
402}
403
404
405/* Find obviously necessary statements.  These are things like most function
406   calls, and stores to file level variables.
407
408   If EL is NULL, control statements are conservatively marked as
409   necessary.  Otherwise it contains the list of edges used by control
410   dependence analysis.  */
411
412static void
413find_obviously_necessary_stmts (struct edge_list *el)
414{
415  basic_block bb;
416  gimple_stmt_iterator gsi;
417  edge e;
418  gimple phi, stmt;
419
420  FOR_EACH_BB (bb)
421    {
422      /* PHI nodes are never inherently necessary.  */
423      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
424	{
425	  phi = gsi_stmt (gsi);
426	  gimple_set_plf (phi, STMT_NECESSARY, false);
427	}
428
429      /* Check all statements in the block.  */
430      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
431	{
432	  stmt = gsi_stmt (gsi);
433	  gimple_set_plf (stmt, STMT_NECESSARY, false);
434	  mark_stmt_if_obviously_necessary (stmt, el != NULL);
435	}
436    }
437
438  /* Pure and const functions are finite and thus have no infinite loops in
439     them.  */
440  if ((TREE_READONLY (current_function_decl)
441       || DECL_PURE_P (current_function_decl))
442      && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
443    return;
444
445  /* Prevent the empty possibly infinite loops from being removed.  */
446  if (el)
447    {
448      loop_iterator li;
449      struct loop *loop;
450      scev_initialize ();
451      if (mark_irreducible_loops ())
452	FOR_EACH_BB (bb)
453	  {
454	    edge_iterator ei;
455	    FOR_EACH_EDGE (e, ei, bb->succs)
456	      if ((e->flags & EDGE_DFS_BACK)
457		  && (e->flags & EDGE_IRREDUCIBLE_LOOP))
458		{
459	          if (dump_file)
460	            fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
461		    	     e->src->index, e->dest->index);
462		  mark_control_dependent_edges_necessary (e->dest, el);
463		}
464	  }
465
466      FOR_EACH_LOOP (li, loop, 0)
467	if (!finite_loop_p (loop))
468	  {
469	    if (dump_file)
470	      fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
471	    mark_control_dependent_edges_necessary (loop->latch, el);
472	  }
473      scev_finalize ();
474    }
475}
476
477
478/* Return true if REF is based on an aliased base, otherwise false.  */
479
480static bool
481ref_may_be_aliased (tree ref)
482{
483  while (handled_component_p (ref))
484    ref = TREE_OPERAND (ref, 0);
485  return !(DECL_P (ref)
486	   && !may_be_aliased (ref));
487}
488
489static bitmap visited = NULL;
490static unsigned int longest_chain = 0;
491static unsigned int total_chain = 0;
492static unsigned int nr_walks = 0;
493static bool chain_ovfl = false;
494
495/* Worker for the walker that marks reaching definitions of REF,
496   which is based on a non-aliased decl, necessary.  It returns
497   true whenever the defining statement of the current VDEF is
498   a kill for REF, as no dominating may-defs are necessary for REF
499   anymore.  DATA points to the basic-block that contains the
500   stmt that refers to REF.  */
501
502static bool
503mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
504{
505  gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
506
507  /* All stmts we visit are necessary.  */
508  mark_operand_necessary (vdef);
509
510  /* If the stmt lhs kills ref, then we can stop walking.  */
511  if (gimple_has_lhs (def_stmt)
512      && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
513    {
514      tree base, lhs = gimple_get_lhs (def_stmt);
515      HOST_WIDE_INT size, offset, max_size;
516      ao_ref_base (ref);
517      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
518      /* We can get MEM[symbol: sZ, index: D.8862_1] here,
519	 so base == refd->base does not always hold.  */
520      if (base == ref->base)
521	{
522	  /* For a must-alias check we need to be able to constrain
523	     the accesses properly.  */
524	  if (size != -1 && size == max_size
525	      && ref->max_size != -1)
526	    {
527	      if (offset <= ref->offset
528		  && offset + size >= ref->offset + ref->max_size)
529		return true;
530	    }
531	  /* Or they need to be exactly the same.  */
532	  else if (ref->ref
533		   /* Make sure there is no induction variable involved
534		      in the references (gcc.c-torture/execute/pr42142.c).
535		      The simplest way is to check if the kill dominates
536		      the use.  */
537		   && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
538				      gimple_bb (def_stmt))
539		   && operand_equal_p (ref->ref, lhs, 0))
540	    return true;
541	}
542    }
543
544  /* Otherwise keep walking.  */
545  return false;
546}
547
548static void
549mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
550{
551  unsigned int chain;
552  ao_ref refd;
553  gcc_assert (!chain_ovfl);
554  ao_ref_init (&refd, ref);
555  chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
556			      mark_aliased_reaching_defs_necessary_1,
557			      gimple_bb (stmt), NULL);
558  if (chain > longest_chain)
559    longest_chain = chain;
560  total_chain += chain;
561  nr_walks++;
562}
563
564/* Worker for the walker that marks reaching definitions of REF, which
565   is not based on a non-aliased decl.  For simplicity we need to end
566   up marking all may-defs necessary that are not based on a non-aliased
567   decl.  The only job of this walker is to skip may-defs based on
568   a non-aliased decl.  */
569
570static bool
571mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
572				    tree vdef, void *data ATTRIBUTE_UNUSED)
573{
574  gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
575
576  /* We have to skip already visited (and thus necessary) statements
577     to make the chaining work after we dropped back to simple mode.  */
578  if (chain_ovfl
579      && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
580    {
581      gcc_assert (gimple_nop_p (def_stmt)
582		  || gimple_plf (def_stmt, STMT_NECESSARY));
583      return false;
584    }
585
586  /* We want to skip stores to non-aliased variables.  */
587  if (!chain_ovfl
588      && gimple_assign_single_p (def_stmt))
589    {
590      tree lhs = gimple_assign_lhs (def_stmt);
591      if (!ref_may_be_aliased (lhs))
592	return false;
593    }
594
595  mark_operand_necessary (vdef);
596
597  return false;
598}
599
600static void
601mark_all_reaching_defs_necessary (gimple stmt)
602{
603  walk_aliased_vdefs (NULL, gimple_vuse (stmt),
604		      mark_all_reaching_defs_necessary_1, NULL, &visited);
605}
606
607/* Return true for PHI nodes with one or identical arguments
608   can be removed.  */
609static bool
610degenerate_phi_p (gimple phi)
611{
612  unsigned int i;
613  tree op = gimple_phi_arg_def (phi, 0);
614  for (i = 1; i < gimple_phi_num_args (phi); i++)
615    if (gimple_phi_arg_def (phi, i) != op)
616      return false;
617  return true;
618}
619
620/* Propagate necessity using the operands of necessary statements.
621   Process the uses on each statement in the worklist, and add all
622   feeding statements which contribute to the calculation of this
623   value to the worklist.
624
625   In conservative mode, EL is NULL.  */
626
627static void
628propagate_necessity (struct edge_list *el)
629{
630  gimple stmt;
631  bool aggressive = (el ? true : false);
632
633  if (dump_file && (dump_flags & TDF_DETAILS))
634    fprintf (dump_file, "\nProcessing worklist:\n");
635
636  while (VEC_length (gimple, worklist) > 0)
637    {
638      /* Take STMT from worklist.  */
639      stmt = VEC_pop (gimple, worklist);
640
641      if (dump_file && (dump_flags & TDF_DETAILS))
642	{
643	  fprintf (dump_file, "processing: ");
644	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
645	  fprintf (dump_file, "\n");
646	}
647
648      if (aggressive)
649	{
650	  /* Mark the last statements of the basic blocks that the block
651	     containing STMT is control dependent on, but only if we haven't
652	     already done so.  */
653	  basic_block bb = gimple_bb (stmt);
654	  if (bb != ENTRY_BLOCK_PTR
655	      && ! TEST_BIT (visited_control_parents, bb->index))
656	    {
657	      SET_BIT (visited_control_parents, bb->index);
658	      mark_control_dependent_edges_necessary (bb, el);
659	    }
660	}
661
662      if (gimple_code (stmt) == GIMPLE_PHI
663	  /* We do not process virtual PHI nodes nor do we track their
664	     necessity.  */
665	  && is_gimple_reg (gimple_phi_result (stmt)))
666	{
667	  /* PHI nodes are somewhat special in that each PHI alternative has
668	     data and control dependencies.  All the statements feeding the
669	     PHI node's arguments are always necessary.  In aggressive mode,
670	     we also consider the control dependent edges leading to the
671	     predecessor block associated with each PHI alternative as
672	     necessary.  */
673	  size_t k;
674
675	  for (k = 0; k < gimple_phi_num_args (stmt); k++)
676            {
677	      tree arg = PHI_ARG_DEF (stmt, k);
678	      if (TREE_CODE (arg) == SSA_NAME)
679		mark_operand_necessary (arg);
680	    }
681
682	  if (aggressive && !degenerate_phi_p (stmt))
683	    {
684	      for (k = 0; k < gimple_phi_num_args (stmt); k++)
685		{
686		  basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
687		  if (arg_bb != ENTRY_BLOCK_PTR
688		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
689		    {
690		      SET_BIT (visited_control_parents, arg_bb->index);
691		      mark_control_dependent_edges_necessary (arg_bb, el);
692		    }
693		}
694	    }
695	}
696      else
697	{
698	  /* Propagate through the operands.  Examine all the USE, VUSE and
699	     VDEF operands in this statement.  Mark all the statements
700	     which feed this statement's uses as necessary.  */
701	  ssa_op_iter iter;
702	  tree use;
703
704	  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
705	    mark_operand_necessary (use);
706
707	  use = gimple_vuse (stmt);
708	  if (!use)
709	    continue;
710
711	  /* If we dropped to simple mode make all immediately
712	     reachable definitions necessary.  */
713	  if (chain_ovfl)
714	    {
715	      mark_all_reaching_defs_necessary (stmt);
716	      continue;
717	    }
718
719	  /* For statements that may load from memory (have a VUSE) we
720	     have to mark all reaching (may-)definitions as necessary.
721	     We partition this task into two cases:
722	      1) explicit loads based on decls that are not aliased
723	      2) implicit loads (like calls) and explicit loads not
724	         based on decls that are not aliased (like indirect
725		 references or loads from globals)
726	     For 1) we mark all reaching may-defs as necessary, stopping
727	     at dominating kills.  For 2) we want to mark all dominating
728	     references necessary, but non-aliased ones which we handle
729	     in 1).  By keeping a global visited bitmap for references
730	     we walk for 2) we avoid quadratic behavior for those.  */
731
732	  if (is_gimple_call (stmt))
733	    {
734	      tree callee = gimple_call_fndecl (stmt);
735	      unsigned i;
736
737	      /* Calls to functions that are merely acting as barriers
738		 or that only store to memory do not make any previous
739		 stores necessary.  */
740	      if (callee != NULL_TREE
741		  && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
742		  && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
743		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
744		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
745		continue;
746
747	      /* Calls implicitly load from memory, their arguments
748	         in addition may explicitly perform memory loads.  */
749	      mark_all_reaching_defs_necessary (stmt);
750	      for (i = 0; i < gimple_call_num_args (stmt); ++i)
751		{
752		  tree arg = gimple_call_arg (stmt, i);
753		  if (TREE_CODE (arg) == SSA_NAME
754		      || is_gimple_min_invariant (arg))
755		    continue;
756		  if (!ref_may_be_aliased (arg))
757		    mark_aliased_reaching_defs_necessary (stmt, arg);
758		}
759	    }
760	  else if (gimple_assign_single_p (stmt))
761	    {
762	      tree rhs;
763	      bool rhs_aliased = false;
764	      /* If this is a load mark things necessary.  */
765	      rhs = gimple_assign_rhs1 (stmt);
766	      if (TREE_CODE (rhs) != SSA_NAME
767		  && !is_gimple_min_invariant (rhs))
768		{
769		  if (!ref_may_be_aliased (rhs))
770		    mark_aliased_reaching_defs_necessary (stmt, rhs);
771		  else
772		    rhs_aliased = true;
773		}
774	      if (rhs_aliased)
775		mark_all_reaching_defs_necessary (stmt);
776	    }
777	  else if (gimple_code (stmt) == GIMPLE_RETURN)
778	    {
779	      tree rhs = gimple_return_retval (stmt);
780	      /* A return statement may perform a load.  */
781	      if (TREE_CODE (rhs) != SSA_NAME
782		  && !is_gimple_min_invariant (rhs))
783		{
784		  if (!ref_may_be_aliased (rhs))
785		    mark_aliased_reaching_defs_necessary (stmt, rhs);
786		  else
787		    mark_all_reaching_defs_necessary (stmt);
788		}
789	    }
790	  else if (gimple_code (stmt) == GIMPLE_ASM)
791	    {
792	      unsigned i;
793	      mark_all_reaching_defs_necessary (stmt);
794	      /* Inputs may perform loads.  */
795	      for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
796		{
797		  tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
798		  if (TREE_CODE (op) != SSA_NAME
799		      && !is_gimple_min_invariant (op)
800		      && !ref_may_be_aliased (op))
801		    mark_aliased_reaching_defs_necessary (stmt, op);
802		}
803	    }
804	  else
805	    gcc_unreachable ();
806
807	  /* If we over-used our alias oracle budget drop to simple
808	     mode.  The cost metric allows quadratic behavior
809	     (number of uses times number of may-defs queries) up to
810	     a constant maximal number of queries and after that falls back to
811	     super-linear complexity.  */
812	  if (/* Constant but quadratic for small functions.  */
813	      total_chain > 128 * 128
814	      /* Linear in the number of may-defs.  */
815	      && total_chain > 32 * longest_chain
816	      /* Linear in the number of uses.  */
817	      && total_chain > nr_walks * 32)
818	    {
819	      chain_ovfl = true;
820	      if (visited)
821		bitmap_clear (visited);
822	    }
823	}
824    }
825}
826
827/* Replace all uses of result of PHI by underlying variable and mark it
828   for renaming.  */
829
830void
831mark_virtual_phi_result_for_renaming (gimple phi)
832{
833  bool used = false;
834  imm_use_iterator iter;
835  use_operand_p use_p;
836  gimple stmt;
837  tree result_ssa, result_var;
838
839  if (dump_file && (dump_flags & TDF_DETAILS))
840    {
841      fprintf (dump_file, "Marking result for renaming : ");
842      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
843      fprintf (dump_file, "\n");
844    }
845
846  result_ssa = gimple_phi_result (phi);
847  result_var = SSA_NAME_VAR (result_ssa);
848  FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
849    {
850      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
851        SET_USE (use_p, result_var);
852      update_stmt (stmt);
853      used = true;
854    }
855  if (used)
856    mark_sym_for_renaming (result_var);
857}
858
859/* Remove dead PHI nodes from block BB.  */
860
861static bool
862remove_dead_phis (basic_block bb)
863{
864  bool something_changed = false;
865  gimple_seq phis;
866  gimple phi;
867  gimple_stmt_iterator gsi;
868  phis = phi_nodes (bb);
869
870  for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
871    {
872      stats.total_phis++;
873      phi = gsi_stmt (gsi);
874
875      /* We do not track necessity of virtual PHI nodes.  Instead do
876         very simple dead PHI removal here.  */
877      if (!is_gimple_reg (gimple_phi_result (phi)))
878	{
879	  /* Virtual PHI nodes with one or identical arguments
880	     can be removed.  */
881	  if (degenerate_phi_p (phi))
882	    {
883	      tree vdef = gimple_phi_result (phi);
884	      tree vuse = gimple_phi_arg_def (phi, 0);
885
886	      use_operand_p use_p;
887	      imm_use_iterator iter;
888	      gimple use_stmt;
889	      FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
890		FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
891		  SET_USE (use_p, vuse);
892	      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
893	          && TREE_CODE (vuse) == SSA_NAME)
894		SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
895	    }
896	  else
897	    gimple_set_plf (phi, STMT_NECESSARY, true);
898	}
899
900      if (!gimple_plf (phi, STMT_NECESSARY))
901	{
902	  something_changed = true;
903	  if (dump_file && (dump_flags & TDF_DETAILS))
904	    {
905	      fprintf (dump_file, "Deleting : ");
906	      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
907	      fprintf (dump_file, "\n");
908	    }
909
910	  remove_phi_node (&gsi, true);
911	  stats.removed_phis++;
912	  continue;
913	}
914
915      gsi_next (&gsi);
916    }
917  return something_changed;
918}
919
920/* Forward edge E to respective POST_DOM_BB and update PHIs.  */
921
922static edge
923forward_edge_to_pdom (edge e, basic_block post_dom_bb)
924{
925  gimple_stmt_iterator gsi;
926  edge e2 = NULL;
927  edge_iterator ei;
928
929  if (dump_file && (dump_flags & TDF_DETAILS))
930    fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
931	     e->dest->index, post_dom_bb->index);
932
933  e2 = redirect_edge_and_branch (e, post_dom_bb);
934  cfg_altered = true;
935
936  /* If edge was already around, no updating is neccesary.  */
937  if (e2 != e)
938    return e2;
939
940  if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
941    {
942      /* We are sure that for every live PHI we are seeing control dependent BB.
943         This means that we can pick any edge to duplicate PHI args from.  */
944      FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
945	if (e2 != e)
946	  break;
947      for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
948	{
949	  gimple phi = gsi_stmt (gsi);
950	  tree op;
951	  source_location locus;
952
953	  /* PHIs for virtuals have no control dependency relation on them.
954	     We are lost here and must force renaming of the symbol.  */
955	  if (!is_gimple_reg (gimple_phi_result (phi)))
956	    {
957	      mark_virtual_phi_result_for_renaming (phi);
958	      remove_phi_node (&gsi, true);
959	      continue;
960	    }
961
962	  /* Dead PHI do not imply control dependency.  */
963          if (!gimple_plf (phi, STMT_NECESSARY))
964	    {
965	      gsi_next (&gsi);
966	      continue;
967	    }
968
969	  op = gimple_phi_arg_def (phi, e2->dest_idx);
970	  locus = gimple_phi_arg_location (phi, e2->dest_idx);
971	  add_phi_arg (phi, op, e, locus);
972	  /* The resulting PHI if not dead can only be degenerate.  */
973	  gcc_assert (degenerate_phi_p (phi));
974	  gsi_next (&gsi);
975	}
976    }
977  return e;
978}
979
980/* Remove dead statement pointed to by iterator I.  Receives the basic block BB
981   containing I so that we don't have to look it up.  */
982
983static void
984remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
985{
986  gimple stmt = gsi_stmt (*i);
987
988  if (dump_file && (dump_flags & TDF_DETAILS))
989    {
990      fprintf (dump_file, "Deleting : ");
991      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
992      fprintf (dump_file, "\n");
993    }
994
995  stats.removed++;
996
997  /* If we have determined that a conditional branch statement contributes
998     nothing to the program, then we not only remove it, but we also change
999     the flow graph so that the current block will simply fall-thru to its
1000     immediate post-dominator.  The blocks we are circumventing will be
1001     removed by cleanup_tree_cfg if this change in the flow graph makes them
1002     unreachable.  */
1003  if (is_ctrl_stmt (stmt))
1004    {
1005      basic_block post_dom_bb;
1006      edge e, e2;
1007      edge_iterator ei;
1008
1009      post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
1010
1011      e = find_edge (bb, post_dom_bb);
1012
1013      /* If edge is already there, try to use it.  This avoids need to update
1014         PHI nodes.  Also watch for cases where post dominator does not exists
1015	 or is exit block.  These can happen for infinite loops as we create
1016	 fake edges in the dominator tree.  */
1017      if (e)
1018        ;
1019      else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
1020	e = EDGE_SUCC (bb, 0);
1021      else
1022        e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
1023      gcc_assert (e);
1024      e->probability = REG_BR_PROB_BASE;
1025      e->count = bb->count;
1026
1027      /* The edge is no longer associated with a conditional, so it does
1028	 not have TRUE/FALSE flags.  */
1029      e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1030
1031      /* The lone outgoing edge from BB will be a fallthru edge.  */
1032      e->flags |= EDGE_FALLTHRU;
1033
1034      /* Remove the remaining outgoing edges.  */
1035      for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
1036	if (e != e2)
1037	  {
1038	    cfg_altered = true;
1039            remove_edge (e2);
1040	  }
1041	else
1042	  ei_next (&ei);
1043    }
1044
1045  unlink_stmt_vdef (stmt);
1046  gsi_remove (i, true);
1047  release_defs (stmt);
1048}
1049
1050/* Eliminate unnecessary statements. Any instruction not marked as necessary
1051   contributes nothing to the program, and can be deleted.  */
1052
1053static bool
1054eliminate_unnecessary_stmts (void)
1055{
1056  bool something_changed = false;
1057  basic_block bb;
1058  gimple_stmt_iterator gsi, psi;
1059  gimple stmt;
1060  tree call;
1061  VEC (basic_block, heap) *h;
1062
1063  if (dump_file && (dump_flags & TDF_DETAILS))
1064    fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1065
1066  clear_special_calls ();
1067
1068  /* Walking basic blocks and statements in reverse order avoids
1069     releasing SSA names before any other DEFs that refer to them are
1070     released.  This helps avoid loss of debug information, as we get
1071     a chance to propagate all RHSs of removed SSAs into debug uses,
1072     rather than only the latest ones.  E.g., consider:
1073
1074     x_3 = y_1 + z_2;
1075     a_5 = x_3 - b_4;
1076     # DEBUG a => a_5
1077
1078     If we were to release x_3 before a_5, when we reached a_5 and
1079     tried to substitute it into the debug stmt, we'd see x_3 there,
1080     but x_3's DEF, type, etc would have already been disconnected.
1081     By going backwards, the debug stmt first changes to:
1082
1083     # DEBUG a => x_3 - b_4
1084
1085     and then to:
1086
1087     # DEBUG a => y_1 + z_2 - b_4
1088
1089     as desired.  */
1090  gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1091  h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
1092
1093  while (VEC_length (basic_block, h))
1094    {
1095      bb = VEC_pop (basic_block, h);
1096
1097      /* Remove dead statements.  */
1098      for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
1099	{
1100	  stmt = gsi_stmt (gsi);
1101
1102	  psi = gsi;
1103	  gsi_prev (&psi);
1104
1105	  stats.total++;
1106
1107	  /* If GSI is not necessary then remove it.  */
1108	  if (!gimple_plf (stmt, STMT_NECESSARY))
1109	    {
1110	      if (!is_gimple_debug (stmt))
1111		something_changed = true;
1112	      remove_dead_stmt (&gsi, bb);
1113	    }
1114	  else if (is_gimple_call (stmt))
1115	    {
1116	      call = gimple_call_fndecl (stmt);
1117	      if (call)
1118		{
1119		  tree name;
1120
1121		  /* When LHS of var = call (); is dead, simplify it into
1122		     call (); saving one operand.  */
1123		  name = gimple_call_lhs (stmt);
1124		  if (name && TREE_CODE (name) == SSA_NAME
1125		           && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1126		    {
1127		      something_changed = true;
1128		      if (dump_file && (dump_flags & TDF_DETAILS))
1129			{
1130			  fprintf (dump_file, "Deleting LHS of call: ");
1131			  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1132			  fprintf (dump_file, "\n");
1133			}
1134
1135		      gimple_call_set_lhs (stmt, NULL_TREE);
1136		      maybe_clean_or_replace_eh_stmt (stmt, stmt);
1137		      update_stmt (stmt);
1138		      release_ssa_name (name);
1139		    }
1140		  notice_special_calls (stmt);
1141		}
1142	    }
1143	}
1144    }
1145
1146  VEC_free (basic_block, heap, h);
1147
1148  /* Since we don't track liveness of virtual PHI nodes, it is possible that we
1149     rendered some PHI nodes unreachable while they are still in use.
1150     Mark them for renaming.  */
1151  if (cfg_altered)
1152    {
1153      basic_block prev_bb;
1154
1155      find_unreachable_blocks ();
1156
1157      /* Delete all unreachable basic blocks in reverse dominator order.  */
1158      for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
1159	{
1160	  prev_bb = bb->prev_bb;
1161
1162	  if (!TEST_BIT (bb_contains_live_stmts, bb->index)
1163	      || !(bb->flags & BB_REACHABLE))
1164	    {
1165	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1166		if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1167		  {
1168		    bool found = false;
1169		    imm_use_iterator iter;
1170
1171		    FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
1172		      {
1173			if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1174			  continue;
1175			if (gimple_code (stmt) == GIMPLE_PHI
1176			    || gimple_plf (stmt, STMT_NECESSARY))
1177			  {
1178			    found = true;
1179			    BREAK_FROM_IMM_USE_STMT (iter);
1180			  }
1181		      }
1182		    if (found)
1183		      mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
1184		  }
1185
1186	      if (!(bb->flags & BB_REACHABLE))
1187		{
1188		  /* Speed up the removal of blocks that don't
1189		     dominate others.  Walking backwards, this should
1190		     be the common case.  ??? Do we need to recompute
1191		     dominators because of cfg_altered?  */
1192		  if (!MAY_HAVE_DEBUG_STMTS
1193		      || !first_dom_son (CDI_DOMINATORS, bb))
1194		    delete_basic_block (bb);
1195		  else
1196		    {
1197		      h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1198
1199		      while (VEC_length (basic_block, h))
1200			{
1201			  bb = VEC_pop (basic_block, h);
1202			  prev_bb = bb->prev_bb;
1203			  /* Rearrangements to the CFG may have failed
1204			     to update the dominators tree, so that
1205			     formerly-dominated blocks are now
1206			     otherwise reachable.  */
1207			  if (!!(bb->flags & BB_REACHABLE))
1208			    continue;
1209			  delete_basic_block (bb);
1210			}
1211
1212		      VEC_free (basic_block, heap, h);
1213		    }
1214		}
1215	    }
1216	}
1217    }
1218  FOR_EACH_BB (bb)
1219    {
1220      /* Remove dead PHI nodes.  */
1221      something_changed |= remove_dead_phis (bb);
1222    }
1223
1224  return something_changed;
1225}
1226
1227
1228/* Print out removed statement statistics.  */
1229
1230static void
1231print_stats (void)
1232{
1233  float percg;
1234
1235  percg = ((float) stats.removed / (float) stats.total) * 100;
1236  fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1237	   stats.removed, stats.total, (int) percg);
1238
1239  if (stats.total_phis == 0)
1240    percg = 0;
1241  else
1242    percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1243
1244  fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1245	   stats.removed_phis, stats.total_phis, (int) percg);
1246}
1247
1248/* Initialization for this pass.  Set up the used data structures.  */
1249
1250static void
1251tree_dce_init (bool aggressive)
1252{
1253  memset ((void *) &stats, 0, sizeof (stats));
1254
1255  if (aggressive)
1256    {
1257      int i;
1258
1259      control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1260      for (i = 0; i < last_basic_block; ++i)
1261	control_dependence_map[i] = BITMAP_ALLOC (NULL);
1262
1263      last_stmt_necessary = sbitmap_alloc (last_basic_block);
1264      sbitmap_zero (last_stmt_necessary);
1265      bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
1266      sbitmap_zero (bb_contains_live_stmts);
1267    }
1268
1269  processed = sbitmap_alloc (num_ssa_names + 1);
1270  sbitmap_zero (processed);
1271
1272  worklist = VEC_alloc (gimple, heap, 64);
1273  cfg_altered = false;
1274}
1275
1276/* Cleanup after this pass.  */
1277
1278static void
1279tree_dce_done (bool aggressive)
1280{
1281  if (aggressive)
1282    {
1283      int i;
1284
1285      for (i = 0; i < last_basic_block; ++i)
1286	BITMAP_FREE (control_dependence_map[i]);
1287      free (control_dependence_map);
1288
1289      sbitmap_free (visited_control_parents);
1290      sbitmap_free (last_stmt_necessary);
1291      sbitmap_free (bb_contains_live_stmts);
1292      bb_contains_live_stmts = NULL;
1293    }
1294
1295  sbitmap_free (processed);
1296
1297  VEC_free (gimple, heap, worklist);
1298}
1299
1300/* Main routine to eliminate dead code.
1301
1302   AGGRESSIVE controls the aggressiveness of the algorithm.
1303   In conservative mode, we ignore control dependence and simply declare
1304   all but the most trivially dead branches necessary.  This mode is fast.
1305   In aggressive mode, control dependences are taken into account, which
1306   results in more dead code elimination, but at the cost of some time.
1307
1308   FIXME: Aggressive mode before PRE doesn't work currently because
1309	  the dominance info is not invalidated after DCE1.  This is
1310	  not an issue right now because we only run aggressive DCE
1311	  as the last tree SSA pass, but keep this in mind when you
1312	  start experimenting with pass ordering.  */
1313
1314static unsigned int
1315perform_tree_ssa_dce (bool aggressive)
1316{
1317  struct edge_list *el = NULL;
1318  bool something_changed = 0;
1319
1320  calculate_dominance_info (CDI_DOMINATORS);
1321
1322  /* Preheaders are needed for SCEV to work.
1323     Simple lateches and recorded exits improve chances that loop will
1324     proved to be finite in testcases such as in loop-15.c and loop-24.c  */
1325  if (aggressive)
1326    loop_optimizer_init (LOOPS_NORMAL
1327			 | LOOPS_HAVE_RECORDED_EXITS);
1328
1329  tree_dce_init (aggressive);
1330
1331  if (aggressive)
1332    {
1333      /* Compute control dependence.  */
1334      timevar_push (TV_CONTROL_DEPENDENCES);
1335      calculate_dominance_info (CDI_POST_DOMINATORS);
1336      el = create_edge_list ();
1337      find_all_control_dependences (el);
1338      timevar_pop (TV_CONTROL_DEPENDENCES);
1339
1340      visited_control_parents = sbitmap_alloc (last_basic_block);
1341      sbitmap_zero (visited_control_parents);
1342
1343      mark_dfs_back_edges ();
1344    }
1345
1346  find_obviously_necessary_stmts (el);
1347
1348  if (aggressive)
1349    loop_optimizer_finalize ();
1350
1351  longest_chain = 0;
1352  total_chain = 0;
1353  nr_walks = 0;
1354  chain_ovfl = false;
1355  visited = BITMAP_ALLOC (NULL);
1356  propagate_necessity (el);
1357  BITMAP_FREE (visited);
1358
1359  something_changed |= eliminate_unnecessary_stmts ();
1360  something_changed |= cfg_altered;
1361
1362  /* We do not update postdominators, so free them unconditionally.  */
1363  free_dominance_info (CDI_POST_DOMINATORS);
1364
1365  /* If we removed paths in the CFG, then we need to update
1366     dominators as well.  I haven't investigated the possibility
1367     of incrementally updating dominators.  */
1368  if (cfg_altered)
1369    free_dominance_info (CDI_DOMINATORS);
1370
1371  statistics_counter_event (cfun, "Statements deleted", stats.removed);
1372  statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
1373
1374  /* Debugging dumps.  */
1375  if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1376    print_stats ();
1377
1378  tree_dce_done (aggressive);
1379
1380  free_edge_list (el);
1381
1382  if (something_changed)
1383    return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1384	    | TODO_remove_unused_locals);
1385  else
1386    return 0;
1387}
1388
1389/* Pass entry points.  */
1390static unsigned int
1391tree_ssa_dce (void)
1392{
1393  return perform_tree_ssa_dce (/*aggressive=*/false);
1394}
1395
1396static unsigned int
1397tree_ssa_dce_loop (void)
1398{
1399  unsigned int todo;
1400  todo = perform_tree_ssa_dce (/*aggressive=*/false);
1401  if (todo)
1402    {
1403      free_numbers_of_iterations_estimates ();
1404      scev_reset ();
1405    }
1406  return todo;
1407}
1408
1409static unsigned int
1410tree_ssa_cd_dce (void)
1411{
1412  return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1413}
1414
1415static bool
1416gate_dce (void)
1417{
1418  return flag_tree_dce != 0;
1419}
1420
1421struct gimple_opt_pass pass_dce =
1422{
1423 {
1424  GIMPLE_PASS,
1425  "dce",				/* name */
1426  gate_dce,				/* gate */
1427  tree_ssa_dce,				/* execute */
1428  NULL,					/* sub */
1429  NULL,					/* next */
1430  0,					/* static_pass_number */
1431  TV_TREE_DCE,				/* tv_id */
1432  PROP_cfg | PROP_ssa,			/* properties_required */
1433  0,					/* properties_provided */
1434  0,					/* properties_destroyed */
1435  0,					/* todo_flags_start */
1436  TODO_dump_func | TODO_verify_ssa	/* todo_flags_finish */
1437 }
1438};
1439
1440struct gimple_opt_pass pass_dce_loop =
1441{
1442 {
1443  GIMPLE_PASS,
1444  "dceloop",				/* name */
1445  gate_dce,				/* gate */
1446  tree_ssa_dce_loop,			/* execute */
1447  NULL,					/* sub */
1448  NULL,					/* next */
1449  0,					/* static_pass_number */
1450  TV_TREE_DCE,				/* tv_id */
1451  PROP_cfg | PROP_ssa,			/* properties_required */
1452  0,					/* properties_provided */
1453  0,					/* properties_destroyed */
1454  0,					/* todo_flags_start */
1455  TODO_dump_func | TODO_verify_ssa	/* todo_flags_finish */
1456 }
1457};
1458
1459struct gimple_opt_pass pass_cd_dce =
1460{
1461 {
1462  GIMPLE_PASS,
1463  "cddce",				/* name */
1464  gate_dce,				/* gate */
1465  tree_ssa_cd_dce,			/* execute */
1466  NULL,					/* sub */
1467  NULL,					/* next */
1468  0,					/* static_pass_number */
1469  TV_TREE_CD_DCE,			/* tv_id */
1470  PROP_cfg | PROP_ssa,			/* properties_required */
1471  0,					/* properties_provided */
1472  0,					/* properties_destroyed */
1473  0,					/* todo_flags_start */
1474  TODO_dump_func | TODO_verify_ssa
1475  | TODO_verify_flow			/* todo_flags_finish */
1476 }
1477};
1478