1/* Basic IPA optimizations and utilities.
2   Copyright (C) 2003, 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 it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 2, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for 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 the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "cgraph.h"
26
27/* Fill array order with all nodes with output flag set in the reverse
28   topological order.  */
29
30int
31cgraph_postorder (struct cgraph_node **order)
32{
33  struct cgraph_node *node, *node2;
34  int stack_size = 0;
35  int order_pos = 0;
36  struct cgraph_edge *edge, last;
37
38  struct cgraph_node **stack =
39    xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
40
41  /* We have to deal with cycles nicely, so use a depth first traversal
42     output algorithm.  Ignore the fact that some functions won't need
43     to be output and put them into order as well, so we get dependencies
44     right through intline functions.  */
45  for (node = cgraph_nodes; node; node = node->next)
46    node->aux = NULL;
47  for (node = cgraph_nodes; node; node = node->next)
48    if (!node->aux)
49      {
50	node2 = node;
51	if (!node->callers)
52	  node->aux = &last;
53	else
54	  node->aux = node->callers;
55	while (node2)
56	  {
57	    while (node2->aux != &last)
58	      {
59		edge = node2->aux;
60		if (edge->next_caller)
61		  node2->aux = edge->next_caller;
62		else
63		  node2->aux = &last;
64		if (!edge->caller->aux)
65		  {
66		    if (!edge->caller->callers)
67		      edge->caller->aux = &last;
68		    else
69		      edge->caller->aux = edge->caller->callers;
70		    stack[stack_size++] = node2;
71		    node2 = edge->caller;
72		    break;
73		  }
74	      }
75	    if (node2->aux == &last)
76	      {
77		order[order_pos++] = node2;
78		if (stack_size)
79		  node2 = stack[--stack_size];
80		else
81		  node2 = NULL;
82	      }
83	  }
84      }
85  free (stack);
86  for (node = cgraph_nodes; node; node = node->next)
87    node->aux = NULL;
88  return order_pos;
89}
90
91/* Perform reachability analysis and reclaim all unreachable nodes.
92   If BEFORE_INLINING_P is true this function is called before inlining
93   decisions has been made.  If BEFORE_INLINING_P is false this function also
94   removes unneeded bodies of extern inline functions.  */
95
96bool
97cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *dump_file)
98{
99  struct cgraph_node *first = (void *) 1;
100  struct cgraph_node *node;
101  bool changed = false;
102  int insns = 0;
103
104#ifdef ENABLE_CHECKING
105  verify_cgraph ();
106#endif
107  if (dump_file)
108    fprintf (dump_file, "\nReclaiming functions:");
109#ifdef ENABLE_CHECKING
110  for (node = cgraph_nodes; node; node = node->next)
111    gcc_assert (!node->aux);
112#endif
113  for (node = cgraph_nodes; node; node = node->next)
114    if (node->needed && !node->global.inlined_to
115	&& ((!DECL_EXTERNAL (node->decl))
116            || !node->analyzed
117            || before_inlining_p))
118      {
119	node->aux = first;
120	first = node;
121      }
122    else
123      gcc_assert (!node->aux);
124
125  /* Perform reachability analysis.  As a special case do not consider
126     extern inline functions not inlined as live because we won't output
127     them at all.  */
128  while (first != (void *) 1)
129    {
130      struct cgraph_edge *e;
131      node = first;
132      first = first->aux;
133
134      for (e = node->callees; e; e = e->next_callee)
135	if (!e->callee->aux
136	    && node->analyzed
137	    && (!e->inline_failed || !e->callee->analyzed
138		|| (!DECL_EXTERNAL (e->callee->decl))
139                || before_inlining_p))
140	  {
141	    e->callee->aux = first;
142	    first = e->callee;
143	  }
144    }
145
146  /* Remove unreachable nodes.  Extern inline functions need special care;
147     Unreachable extern inline functions shall be removed.
148     Reachable extern inline functions we never inlined shall get their bodies
149     eliminated.
150     Reachable extern inline functions we sometimes inlined will be turned into
151     unanalyzed nodes so they look like for true extern functions to the rest
152     of code.  Body of such functions is released via remove_node once the
153     inline clones are eliminated.  */
154  for (node = cgraph_nodes; node; node = node->next)
155    {
156      if (!node->aux)
157	{
158	  int local_insns;
159	  tree decl = node->decl;
160
161          node->global.inlined_to = NULL;
162	  if (DECL_STRUCT_FUNCTION (decl))
163	    local_insns = node->local.self_insns;
164	  else
165	    local_insns = 0;
166	  if (dump_file)
167	    fprintf (dump_file, " %s", cgraph_node_name (node));
168	  if (!node->analyzed || !DECL_EXTERNAL (node->decl)
169	      || before_inlining_p)
170	    cgraph_remove_node (node);
171	  else
172	    {
173	      struct cgraph_edge *e;
174
175	      for (e = node->callers; e; e = e->next_caller)
176		if (e->caller->aux)
177		  break;
178	      if (e || node->needed)
179		{
180		  struct cgraph_node *clone;
181
182		  for (clone = node->next_clone; clone;
183		       clone = clone->next_clone)
184		    if (clone->aux)
185		      break;
186		  if (!clone)
187		    {
188		      DECL_SAVED_TREE (node->decl) = NULL;
189		      DECL_STRUCT_FUNCTION (node->decl) = NULL;
190		      DECL_INITIAL (node->decl) = error_mark_node;
191		      node->analyzed = false;
192		    }
193		  cgraph_node_remove_callees (node);
194		  node->analyzed = false;
195		}
196	      else
197		cgraph_remove_node (node);
198	    }
199	  if (!DECL_SAVED_TREE (decl))
200	    insns += local_insns;
201	  changed = true;
202	}
203    }
204  for (node = cgraph_nodes; node; node = node->next)
205    node->aux = NULL;
206  if (dump_file)
207    fprintf (dump_file, "\nReclaimed %i insns", insns);
208  return changed;
209}
210