1 /* Basic IPA optimizations and utilities.
2 Copyright (C) 2003, 2004, 2005 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 it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 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 the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-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
30 int
cgraph_postorder(struct cgraph_node ** order)31 cgraph_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
96 bool
cgraph_remove_unreachable_nodes(bool before_inlining_p,FILE * file)97 cgraph_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