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    XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
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 *file)
98{
99  struct cgraph_node *first = (void *) 1;
100  struct cgraph_node *node, *next;
101  bool changed = false;
102  int insns = 0;
103
104#ifdef ENABLE_CHECKING
105  verify_cgraph ();
106#endif
107  if (file)
108    fprintf (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 = next)
155    {
156      next = node->next;
157      if (!node->aux)
158	{
159	  int local_insns;
160	  tree decl = node->decl;
161
162          node->global.inlined_to = NULL;
163	  if (DECL_STRUCT_FUNCTION (decl))
164	    local_insns = node->local.self_insns;
165	  else
166	    local_insns = 0;
167	  if (file)
168	    fprintf (file, " %s", cgraph_node_name (node));
169	  if (!node->analyzed || !DECL_EXTERNAL (node->decl)
170	      || before_inlining_p)
171	    cgraph_remove_node (node);
172	  else
173	    {
174	      struct cgraph_edge *e;
175
176	      for (e = node->callers; e; e = e->next_caller)
177		if (e->caller->aux)
178		  break;
179	      if (e || node->needed)
180		{
181		  struct cgraph_node *clone;
182
183		  for (clone = node->next_clone; clone;
184		       clone = clone->next_clone)
185		    if (clone->aux)
186		      break;
187		  if (!clone)
188		    {
189		      DECL_SAVED_TREE (node->decl) = NULL;
190		      DECL_STRUCT_FUNCTION (node->decl) = NULL;
191		      DECL_INITIAL (node->decl) = error_mark_node;
192		      node->analyzed = false;
193		    }
194		  cgraph_node_remove_callees (node);
195		  node->analyzed = false;
196		}
197	      else
198		cgraph_remove_node (node);
199	    }
200	  if (!DECL_SAVED_TREE (decl))
201	    insns += local_insns;
202	  changed = true;
203	}
204    }
205  for (node = cgraph_nodes; node; node = node->next)
206    node->aux = NULL;
207  if (file)
208    fprintf (file, "\nReclaimed %i insns", insns);
209  return changed;
210}
211