]>
Commit | Line | Data |
---|---|---|
ca31b95f JH |
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 | |
366ccddb KC |
18 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
19 | 02110-1301, USA. */ | |
ca31b95f JH |
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 | |
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 = | |
5ed6ace5 | 39 | XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); |
ca31b95f JH |
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); | |
d63db217 JH |
86 | for (node = cgraph_nodes; node; node = node->next) |
87 | node->aux = NULL; | |
ca31b95f JH |
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 | |
10d22567 | 97 | cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) |
ca31b95f JH |
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 | |
10d22567 ZD |
107 | if (file) |
108 | fprintf (file, "\nReclaiming functions:"); | |
ca31b95f JH |
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; | |
10d22567 ZD |
166 | if (file) |
167 | fprintf (file, " %s", cgraph_node_name (node)); | |
ca31b95f JH |
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; | |
10d22567 ZD |
206 | if (file) |
207 | fprintf (file, "\nReclaimed %i insns", insns); | |
ca31b95f JH |
208 | return changed; |
209 | } |