]>
Commit | Line | Data |
---|---|---|
ca31b95f | 1 | /* Basic IPA optimizations and utilities. |
fa10beec RW |
2 | Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, |
3 | Inc. | |
ca31b95f JH |
4 | |
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
ca31b95f JH |
10 | version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
ca31b95f JH |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "cgraph.h" | |
f4b3ca72 JH |
26 | #include "tree-pass.h" |
27 | #include "timevar.h" | |
9187e02d | 28 | #include "gimple.h" |
fed5ae11 | 29 | #include "ggc.h" |
ca31b95f JH |
30 | |
31 | /* Fill array order with all nodes with output flag set in the reverse | |
32 | topological order. */ | |
33 | ||
34 | int | |
35 | cgraph_postorder (struct cgraph_node **order) | |
36 | { | |
37 | struct cgraph_node *node, *node2; | |
38 | int stack_size = 0; | |
39 | int order_pos = 0; | |
40 | struct cgraph_edge *edge, last; | |
39ff5a96 | 41 | int pass; |
ca31b95f JH |
42 | |
43 | struct cgraph_node **stack = | |
5ed6ace5 | 44 | XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); |
ca31b95f JH |
45 | |
46 | /* We have to deal with cycles nicely, so use a depth first traversal | |
47 | output algorithm. Ignore the fact that some functions won't need | |
48 | to be output and put them into order as well, so we get dependencies | |
fa10beec | 49 | right through inline functions. */ |
ca31b95f JH |
50 | for (node = cgraph_nodes; node; node = node->next) |
51 | node->aux = NULL; | |
39ff5a96 JH |
52 | for (pass = 0; pass < 2; pass++) |
53 | for (node = cgraph_nodes; node; node = node->next) | |
54 | if (!node->aux | |
b20996ff JH |
55 | && (pass |
56 | || (!cgraph_only_called_directly_p (node) | |
57 | && !node->address_taken))) | |
39ff5a96 JH |
58 | { |
59 | node2 = node; | |
60 | if (!node->callers) | |
61 | node->aux = &last; | |
62 | else | |
63 | node->aux = node->callers; | |
64 | while (node2) | |
65 | { | |
66 | while (node2->aux != &last) | |
67 | { | |
68 | edge = (struct cgraph_edge *) node2->aux; | |
69 | if (edge->next_caller) | |
70 | node2->aux = edge->next_caller; | |
71 | else | |
72 | node2->aux = &last; | |
73 | if (!edge->caller->aux) | |
74 | { | |
75 | if (!edge->caller->callers) | |
76 | edge->caller->aux = &last; | |
77 | else | |
78 | edge->caller->aux = edge->caller->callers; | |
79 | stack[stack_size++] = node2; | |
80 | node2 = edge->caller; | |
81 | break; | |
82 | } | |
83 | } | |
84 | if (node2->aux == &last) | |
85 | { | |
86 | order[order_pos++] = node2; | |
87 | if (stack_size) | |
88 | node2 = stack[--stack_size]; | |
89 | else | |
90 | node2 = NULL; | |
91 | } | |
92 | } | |
93 | } | |
ca31b95f | 94 | free (stack); |
d63db217 JH |
95 | for (node = cgraph_nodes; node; node = node->next) |
96 | node->aux = NULL; | |
ca31b95f JH |
97 | return order_pos; |
98 | } | |
99 | ||
d563610d JH |
100 | /* Look for all functions inlined to NODE and update their inlined_to pointers |
101 | to INLINED_TO. */ | |
102 | ||
103 | static void | |
104 | update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to) | |
105 | { | |
106 | struct cgraph_edge *e; | |
107 | for (e = node->callees; e; e = e->next_callee) | |
108 | if (e->callee->global.inlined_to) | |
109 | { | |
110 | e->callee->global.inlined_to = inlined_to; | |
111 | update_inlined_to_pointer (e->callee, inlined_to); | |
112 | } | |
113 | } | |
114 | ||
ca31b95f JH |
115 | /* Perform reachability analysis and reclaim all unreachable nodes. |
116 | If BEFORE_INLINING_P is true this function is called before inlining | |
b8698a0f | 117 | decisions has been made. If BEFORE_INLINING_P is false this function also |
ca31b95f JH |
118 | removes unneeded bodies of extern inline functions. */ |
119 | ||
120 | bool | |
10d22567 | 121 | cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) |
ca31b95f | 122 | { |
c5274326 | 123 | struct cgraph_node *first = (struct cgraph_node *) (void *) 1; |
0e3776db | 124 | struct cgraph_node *processed = (struct cgraph_node *) (void *) 2; |
96fc428c | 125 | struct cgraph_node *node, *next; |
ca31b95f | 126 | bool changed = false; |
ca31b95f JH |
127 | |
128 | #ifdef ENABLE_CHECKING | |
129 | verify_cgraph (); | |
130 | #endif | |
10d22567 ZD |
131 | if (file) |
132 | fprintf (file, "\nReclaiming functions:"); | |
ca31b95f JH |
133 | #ifdef ENABLE_CHECKING |
134 | for (node = cgraph_nodes; node; node = node->next) | |
135 | gcc_assert (!node->aux); | |
136 | #endif | |
137 | for (node = cgraph_nodes; node; node = node->next) | |
b20996ff | 138 | if (!cgraph_can_remove_if_no_direct_calls_p (node) |
b8698a0f | 139 | && ((!DECL_EXTERNAL (node->decl)) |
ca31b95f JH |
140 | || !node->analyzed |
141 | || before_inlining_p)) | |
142 | { | |
b20996ff | 143 | gcc_assert (!node->global.inlined_to); |
ca31b95f JH |
144 | node->aux = first; |
145 | first = node; | |
0e3776db | 146 | node->reachable = true; |
ca31b95f JH |
147 | } |
148 | else | |
0e3776db JH |
149 | { |
150 | gcc_assert (!node->aux); | |
151 | node->reachable = false; | |
152 | } | |
ca31b95f JH |
153 | |
154 | /* Perform reachability analysis. As a special case do not consider | |
155 | extern inline functions not inlined as live because we won't output | |
156 | them at all. */ | |
157 | while (first != (void *) 1) | |
158 | { | |
159 | struct cgraph_edge *e; | |
160 | node = first; | |
c5274326 | 161 | first = (struct cgraph_node *) first->aux; |
0e3776db | 162 | node->aux = processed; |
ca31b95f | 163 | |
0e3776db JH |
164 | if (node->reachable) |
165 | for (e = node->callees; e; e = e->next_callee) | |
166 | if (!e->callee->reachable | |
167 | && node->analyzed | |
168 | && (!e->inline_failed || !e->callee->analyzed | |
169 | || (!DECL_EXTERNAL (e->callee->decl)) | |
170 | || before_inlining_p)) | |
171 | { | |
172 | bool prev_reachable = e->callee->reachable; | |
173 | e->callee->reachable |= node->reachable; | |
174 | if (!e->callee->aux | |
175 | || (e->callee->aux == processed | |
176 | && prev_reachable != e->callee->reachable)) | |
177 | { | |
178 | e->callee->aux = first; | |
179 | first = e->callee; | |
180 | } | |
181 | } | |
9187e02d JH |
182 | while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl)) |
183 | { | |
184 | node = node->clone_of; | |
185 | node->aux = first; | |
186 | first = node; | |
187 | } | |
ca31b95f JH |
188 | } |
189 | ||
190 | /* Remove unreachable nodes. Extern inline functions need special care; | |
191 | Unreachable extern inline functions shall be removed. | |
192 | Reachable extern inline functions we never inlined shall get their bodies | |
193 | eliminated. | |
194 | Reachable extern inline functions we sometimes inlined will be turned into | |
195 | unanalyzed nodes so they look like for true extern functions to the rest | |
196 | of code. Body of such functions is released via remove_node once the | |
197 | inline clones are eliminated. */ | |
96fc428c | 198 | for (node = cgraph_nodes; node; node = next) |
ca31b95f | 199 | { |
96fc428c | 200 | next = node->next; |
0e3776db JH |
201 | if (node->aux && !node->reachable) |
202 | { | |
203 | cgraph_node_remove_callees (node); | |
204 | node->analyzed = false; | |
205 | node->local.inlinable = false; | |
206 | } | |
ca31b95f JH |
207 | if (!node->aux) |
208 | { | |
ca31b95f | 209 | node->global.inlined_to = NULL; |
10d22567 ZD |
210 | if (file) |
211 | fprintf (file, " %s", cgraph_node_name (node)); | |
0e3776db | 212 | if (!node->analyzed || !DECL_EXTERNAL (node->decl) || before_inlining_p) |
ca31b95f JH |
213 | cgraph_remove_node (node); |
214 | else | |
215 | { | |
216 | struct cgraph_edge *e; | |
217 | ||
9187e02d | 218 | /* See if there is reachable caller. */ |
ca31b95f JH |
219 | for (e = node->callers; e; e = e->next_caller) |
220 | if (e->caller->aux) | |
221 | break; | |
9187e02d JH |
222 | |
223 | /* If so, we need to keep node in the callgraph. */ | |
ca31b95f JH |
224 | if (e || node->needed) |
225 | { | |
226 | struct cgraph_node *clone; | |
227 | ||
9187e02d JH |
228 | /* If there are still clones, we must keep body around. |
229 | Otherwise we can just remove the body but keep the clone. */ | |
230 | for (clone = node->clones; clone; | |
231 | clone = clone->next_sibling_clone) | |
ca31b95f JH |
232 | if (clone->aux) |
233 | break; | |
234 | if (!clone) | |
235 | { | |
3a40c18a | 236 | cgraph_release_function_body (node); |
9187e02d | 237 | cgraph_node_remove_callees (node); |
ca31b95f | 238 | node->analyzed = false; |
9187e02d | 239 | node->local.inlinable = false; |
ca31b95f | 240 | } |
0e3776db JH |
241 | if (node->prev_sibling_clone) |
242 | node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone; | |
243 | else if (node->clone_of) | |
244 | node->clone_of->clones = node->next_sibling_clone; | |
245 | if (node->next_sibling_clone) | |
246 | node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone; | |
ca31b95f JH |
247 | } |
248 | else | |
249 | cgraph_remove_node (node); | |
250 | } | |
ca31b95f JH |
251 | changed = true; |
252 | } | |
253 | } | |
254 | for (node = cgraph_nodes; node; node = node->next) | |
9187e02d JH |
255 | { |
256 | /* Inline clones might be kept around so their materializing allows further | |
257 | cloning. If the function the clone is inlined into is removed, we need | |
258 | to turn it into normal cone. */ | |
259 | if (node->global.inlined_to | |
260 | && !node->callers) | |
261 | { | |
262 | gcc_assert (node->clones); | |
d563610d JH |
263 | node->global.inlined_to = NULL; |
264 | update_inlined_to_pointer (node, node); | |
9187e02d JH |
265 | } |
266 | node->aux = NULL; | |
267 | } | |
873aa8f5 JH |
268 | #ifdef ENABLE_CHECKING |
269 | verify_cgraph (); | |
270 | #endif | |
4537ec0c DN |
271 | |
272 | /* Reclaim alias pairs for functions that have disappeared from the | |
273 | call graph. */ | |
274 | remove_unreachable_alias_pairs (); | |
275 | ||
ca31b95f JH |
276 | return changed; |
277 | } | |
f4b3ca72 | 278 | |
b20996ff JH |
279 | static bool |
280 | cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program) | |
281 | { | |
b820a2f9 JH |
282 | if (!node->local.finalized) |
283 | return false; | |
b20996ff JH |
284 | if (!DECL_COMDAT (node->decl) |
285 | && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl))) | |
286 | return false; | |
287 | if (!whole_program) | |
288 | return true; | |
289 | /* COMDAT functions must be shared only if they have address taken, | |
290 | otherwise we can produce our own private implementation with | |
291 | -fwhole-program. */ | |
292 | if (DECL_COMDAT (node->decl) && (node->address_taken || !node->analyzed)) | |
293 | return true; | |
294 | if (MAIN_NAME_P (DECL_NAME (node->decl))) | |
295 | return true; | |
296 | if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl))) | |
297 | return true; | |
298 | return false; | |
299 | } | |
300 | ||
f4b3ca72 JH |
301 | /* Mark visibility of all functions. |
302 | ||
303 | A local function is one whose calls can occur only in the current | |
304 | compilation unit and all its calls are explicit, so we can change | |
305 | its calling convention. We simply mark all static functions whose | |
306 | address is not taken as local. | |
307 | ||
308 | We also change the TREE_PUBLIC flag of all declarations that are public | |
309 | in language point of view but we want to overwrite this default | |
310 | via visibilities for the backend point of view. */ | |
311 | ||
4e260309 | 312 | static unsigned int |
b20996ff | 313 | function_and_variable_visibility (bool whole_program) |
f4b3ca72 JH |
314 | { |
315 | struct cgraph_node *node; | |
316 | struct varpool_node *vnode; | |
317 | ||
318 | for (node = cgraph_nodes; node; node = node->next) | |
319 | { | |
589520b6 JH |
320 | /* C++ FE on lack of COMDAT support create local COMDAT functions |
321 | (that ought to be shared but can not due to object format | |
322 | limitations). It is neccesary to keep the flag to make rest of C++ FE | |
323 | happy. Clear the flag here to avoid confusion in middle-end. */ | |
324 | if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl)) | |
325 | DECL_COMDAT (node->decl) = 0; | |
a8289259 JH |
326 | gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl)) |
327 | || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)); | |
b20996ff JH |
328 | if (cgraph_externally_visible_p (node, whole_program)) |
329 | { | |
330 | gcc_assert (!node->global.inlined_to); | |
331 | node->local.externally_visible = true; | |
332 | } | |
333 | else | |
334 | node->local.externally_visible = false; | |
f4b3ca72 JH |
335 | if (!node->local.externally_visible && node->analyzed |
336 | && !DECL_EXTERNAL (node->decl)) | |
337 | { | |
b20996ff | 338 | gcc_assert (whole_program || !TREE_PUBLIC (node->decl)); |
f4b3ca72 | 339 | TREE_PUBLIC (node->decl) = 0; |
b20996ff JH |
340 | DECL_COMDAT (node->decl) = 0; |
341 | DECL_WEAK (node->decl) = 0; | |
f4b3ca72 | 342 | } |
b20996ff | 343 | node->local.local = (cgraph_only_called_directly_p (node) |
f4b3ca72 JH |
344 | && node->analyzed |
345 | && !DECL_EXTERNAL (node->decl) | |
346 | && !node->local.externally_visible); | |
347 | } | |
348 | for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed) | |
349 | { | |
b820a2f9 JH |
350 | if (!vnode->finalized) |
351 | continue; | |
c8f59bc8 JH |
352 | gcc_assert ((!DECL_WEAK (vnode->decl) && !DECL_COMMON (vnode->decl)) |
353 | || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl)); | |
f4b3ca72 | 354 | if (vnode->needed |
b20996ff JH |
355 | && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)) |
356 | && (!whole_program | |
62a0a52e JH |
357 | /* We can privatize comdat readonly variables whose address is not taken, |
358 | but doing so is not going to bring us optimization oppurtunities until | |
359 | we start reordering datastructures. */ | |
360 | || DECL_COMDAT (vnode->decl) | |
361 | || DECL_WEAK (vnode->decl) | |
b20996ff JH |
362 | || lookup_attribute ("externally_visible", |
363 | DECL_ATTRIBUTES (vnode->decl)))) | |
364 | vnode->externally_visible = true; | |
365 | else | |
366 | vnode->externally_visible = false; | |
f4b3ca72 JH |
367 | if (!vnode->externally_visible) |
368 | { | |
b20996ff | 369 | gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl)); |
f4b3ca72 | 370 | TREE_PUBLIC (vnode->decl) = 0; |
c8f59bc8 | 371 | DECL_COMMON (vnode->decl) = 0; |
f4b3ca72 JH |
372 | } |
373 | gcc_assert (TREE_STATIC (vnode->decl)); | |
374 | } | |
375 | ||
376 | if (dump_file) | |
377 | { | |
378 | fprintf (dump_file, "\nMarking local functions:"); | |
379 | for (node = cgraph_nodes; node; node = node->next) | |
380 | if (node->local.local) | |
381 | fprintf (dump_file, " %s", cgraph_node_name (node)); | |
382 | fprintf (dump_file, "\n\n"); | |
383 | fprintf (dump_file, "\nMarking externally visible functions:"); | |
384 | for (node = cgraph_nodes; node; node = node->next) | |
385 | if (node->local.externally_visible) | |
386 | fprintf (dump_file, " %s", cgraph_node_name (node)); | |
387 | fprintf (dump_file, "\n\n"); | |
a8289259 JH |
388 | fprintf (dump_file, "\nMarking externally visible variables:"); |
389 | for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed) | |
390 | if (vnode->externally_visible) | |
391 | fprintf (dump_file, " %s", varpool_node_name (vnode)); | |
392 | fprintf (dump_file, "\n\n"); | |
f4b3ca72 JH |
393 | } |
394 | cgraph_function_flags_ready = true; | |
4e260309 | 395 | return 0; |
f4b3ca72 JH |
396 | } |
397 | ||
b20996ff JH |
398 | /* Local function pass handling visibilities. This happens before LTO streaming |
399 | so in particular -fwhole-program should be ignored at this level. */ | |
400 | ||
401 | static unsigned int | |
402 | local_function_and_variable_visibility (void) | |
403 | { | |
404 | return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr); | |
405 | } | |
406 | ||
b8698a0f | 407 | struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility = |
f4b3ca72 | 408 | { |
8ddbbcae JH |
409 | { |
410 | SIMPLE_IPA_PASS, | |
f4b3ca72 JH |
411 | "visibility", /* name */ |
412 | NULL, /* gate */ | |
b20996ff | 413 | local_function_and_variable_visibility,/* execute */ |
f4b3ca72 JH |
414 | NULL, /* sub */ |
415 | NULL, /* next */ | |
416 | 0, /* static_pass_number */ | |
417 | TV_CGRAPHOPT, /* tv_id */ | |
418 | 0, /* properties_required */ | |
419 | 0, /* properties_provided */ | |
420 | 0, /* properties_destroyed */ | |
421 | 0, /* todo_flags_start */ | |
8ddbbcae JH |
422 | TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */ |
423 | } | |
f4b3ca72 | 424 | }; |
fed5ae11 | 425 | |
b20996ff JH |
426 | /* Do not re-run on ltrans stage. */ |
427 | ||
428 | static bool | |
429 | gate_whole_program_function_and_variable_visibility (void) | |
430 | { | |
431 | return !flag_ltrans; | |
432 | } | |
433 | ||
434 | /* Bring functionss local at LTO time whith -fwhole-program. */ | |
435 | ||
436 | static unsigned int | |
437 | whole_program_function_and_variable_visibility (void) | |
438 | { | |
439 | struct cgraph_node *node; | |
440 | struct varpool_node *vnode; | |
441 | ||
442 | function_and_variable_visibility (flag_whole_program); | |
443 | ||
444 | for (node = cgraph_nodes; node; node = node->next) | |
62a0a52e JH |
445 | if ((node->local.externally_visible && !DECL_COMDAT (node->decl)) |
446 | && node->local.finalized) | |
b20996ff JH |
447 | cgraph_mark_needed_node (node); |
448 | for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed) | |
62a0a52e | 449 | if (vnode->externally_visible && !DECL_COMDAT (vnode->decl)) |
b20996ff | 450 | varpool_mark_needed_node (vnode); |
a8289259 JH |
451 | if (dump_file) |
452 | { | |
453 | fprintf (dump_file, "\nNeeded variables:"); | |
454 | for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed) | |
455 | if (vnode->needed) | |
456 | fprintf (dump_file, " %s", varpool_node_name (vnode)); | |
457 | fprintf (dump_file, "\n\n"); | |
458 | } | |
b20996ff JH |
459 | return 0; |
460 | } | |
461 | ||
462 | struct ipa_opt_pass_d pass_ipa_whole_program_visibility = | |
463 | { | |
464 | { | |
465 | IPA_PASS, | |
466 | "whole-program", /* name */ | |
467 | gate_whole_program_function_and_variable_visibility,/* gate */ | |
468 | whole_program_function_and_variable_visibility,/* execute */ | |
469 | NULL, /* sub */ | |
470 | NULL, /* next */ | |
471 | 0, /* static_pass_number */ | |
472 | TV_CGRAPHOPT, /* tv_id */ | |
473 | 0, /* properties_required */ | |
474 | 0, /* properties_provided */ | |
475 | 0, /* properties_destroyed */ | |
476 | 0, /* todo_flags_start */ | |
477 | TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */ | |
478 | }, | |
479 | NULL, /* generate_summary */ | |
480 | NULL, /* write_summary */ | |
481 | NULL, /* read_summary */ | |
482 | NULL, /* function_read_summary */ | |
2c5721d9 | 483 | NULL, /* stmt_fixup */ |
b20996ff JH |
484 | 0, /* TODOs */ |
485 | NULL, /* function_transform */ | |
486 | NULL, /* variable_transform */ | |
487 | }; | |
fed5ae11 DK |
488 | |
489 | /* Hash a cgraph node set element. */ | |
490 | ||
491 | static hashval_t | |
492 | hash_cgraph_node_set_element (const void *p) | |
493 | { | |
494 | const_cgraph_node_set_element element = (const_cgraph_node_set_element) p; | |
495 | return htab_hash_pointer (element->node); | |
496 | } | |
497 | ||
498 | /* Compare two cgraph node set elements. */ | |
499 | ||
500 | static int | |
501 | eq_cgraph_node_set_element (const void *p1, const void *p2) | |
502 | { | |
503 | const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1; | |
504 | const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2; | |
505 | ||
506 | return e1->node == e2->node; | |
507 | } | |
508 | ||
509 | /* Create a new cgraph node set. */ | |
510 | ||
511 | cgraph_node_set | |
512 | cgraph_node_set_new (void) | |
513 | { | |
514 | cgraph_node_set new_node_set; | |
515 | ||
516 | new_node_set = GGC_NEW (struct cgraph_node_set_def); | |
517 | new_node_set->hashtab = htab_create_ggc (10, | |
518 | hash_cgraph_node_set_element, | |
519 | eq_cgraph_node_set_element, | |
520 | NULL); | |
521 | new_node_set->nodes = NULL; | |
522 | return new_node_set; | |
523 | } | |
524 | ||
525 | /* Add cgraph_node NODE to cgraph_node_set SET. */ | |
526 | ||
527 | void | |
528 | cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node) | |
529 | { | |
530 | void **slot; | |
531 | cgraph_node_set_element element; | |
532 | struct cgraph_node_set_element_def dummy; | |
533 | ||
534 | dummy.node = node; | |
535 | slot = htab_find_slot (set->hashtab, &dummy, INSERT); | |
536 | ||
537 | if (*slot != HTAB_EMPTY_ENTRY) | |
538 | { | |
539 | element = (cgraph_node_set_element) *slot; | |
540 | gcc_assert (node == element->node | |
541 | && (VEC_index (cgraph_node_ptr, set->nodes, element->index) | |
542 | == node)); | |
543 | return; | |
544 | } | |
545 | ||
546 | /* Insert node into hash table. */ | |
547 | element = | |
548 | (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def); | |
549 | element->node = node; | |
550 | element->index = VEC_length (cgraph_node_ptr, set->nodes); | |
551 | *slot = element; | |
552 | ||
553 | /* Insert into node vector. */ | |
554 | VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node); | |
555 | } | |
556 | ||
557 | /* Remove cgraph_node NODE from cgraph_node_set SET. */ | |
558 | ||
559 | void | |
560 | cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node) | |
561 | { | |
562 | void **slot, **last_slot; | |
563 | cgraph_node_set_element element, last_element; | |
564 | struct cgraph_node *last_node; | |
565 | struct cgraph_node_set_element_def dummy; | |
566 | ||
567 | dummy.node = node; | |
568 | slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); | |
569 | if (slot == NULL) | |
570 | return; | |
571 | ||
572 | element = (cgraph_node_set_element) *slot; | |
573 | gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index) | |
574 | == node); | |
575 | ||
576 | /* Remove from vector. We do this by swapping node with the last element | |
577 | of the vector. */ | |
578 | last_node = VEC_pop (cgraph_node_ptr, set->nodes); | |
579 | if (last_node != node) | |
580 | { | |
581 | dummy.node = last_node; | |
582 | last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); | |
583 | last_element = (cgraph_node_set_element) *last_slot; | |
584 | gcc_assert (last_element); | |
585 | ||
586 | /* Move the last element to the original spot of NODE. */ | |
587 | last_element->index = element->index; | |
588 | VEC_replace (cgraph_node_ptr, set->nodes, last_element->index, | |
589 | last_node); | |
590 | } | |
b8698a0f | 591 | |
fed5ae11 DK |
592 | /* Remove element from hash table. */ |
593 | htab_clear_slot (set->hashtab, slot); | |
594 | ggc_free (element); | |
595 | } | |
596 | ||
597 | /* Find NODE in SET and return an iterator to it if found. A null iterator | |
598 | is returned if NODE is not in SET. */ | |
599 | ||
600 | cgraph_node_set_iterator | |
601 | cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node) | |
602 | { | |
603 | void **slot; | |
604 | struct cgraph_node_set_element_def dummy; | |
605 | cgraph_node_set_element element; | |
606 | cgraph_node_set_iterator csi; | |
607 | ||
608 | dummy.node = node; | |
609 | slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT); | |
610 | if (slot == NULL) | |
611 | csi.index = (unsigned) ~0; | |
612 | else | |
613 | { | |
614 | element = (cgraph_node_set_element) *slot; | |
615 | gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index) | |
616 | == node); | |
617 | csi.index = element->index; | |
618 | } | |
619 | csi.set = set; | |
620 | ||
621 | return csi; | |
622 | } | |
623 | ||
624 | /* Dump content of SET to file F. */ | |
625 | ||
626 | void | |
627 | dump_cgraph_node_set (FILE *f, cgraph_node_set set) | |
628 | { | |
629 | cgraph_node_set_iterator iter; | |
630 | ||
631 | for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter)) | |
632 | { | |
633 | struct cgraph_node *node = csi_node (iter); | |
634 | dump_cgraph_node (f, node); | |
635 | } | |
636 | } | |
637 | ||
638 | /* Dump content of SET to stderr. */ | |
639 | ||
640 | void | |
641 | debug_cgraph_node_set (cgraph_node_set set) | |
642 | { | |
643 | dump_cgraph_node_set (stderr, set); | |
644 | } | |
645 |