1 /* Utilities for ipa analysis.
2 Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
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
9 Software Foundation; either version 3, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "tree-flow.h"
27 #include "tree-inline.h"
28 #include "tree-pass.h"
29 #include "langhooks.h"
30 #include "pointer-set.h"
31 #include "splay-tree.h"
33 #include "ipa-utils.h"
34 #include "ipa-reference.h"
40 #include "diagnostic.h"
41 #include "langhooks.h"
43 /* Debugging function for postorder and inorder code. NOTE is a string
44 that is printed before the nodes are printed. ORDER is an array of
45 cgraph_nodes that has COUNT useful nodes in it. */
48 ipa_print_order (FILE* out,
50 struct cgraph_node** order,
54 fprintf (out, "\n\n ordered call graph: %s\n", note);
56 for (i = count - 1; i >= 0; i--)
57 dump_cgraph_node(dump_file, order[i]);
64 struct cgraph_node **stack;
66 struct cgraph_node **result;
68 splay_tree nodes_marked_new;
70 bool allow_overwritable;
74 /* This is an implementation of Tarjan's strongly connected region
75 finder as reprinted in Aho Hopcraft and Ullman's The Design and
76 Analysis of Computer Programs (1975) pages 192-193. This version
77 has been customized for cgraph_nodes. The env parameter is because
78 it is recursive and there are no nested functions here. This
79 function should only be called from itself or
80 ipa_reduced_postorder. ENV is a stack env and would be
81 unnecessary if C had nested functions. V is the node to start
85 searchc (struct searchc_env* env, struct cgraph_node *v,
86 bool (*ignore_edge) (struct cgraph_edge *))
88 struct cgraph_edge *edge;
89 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
91 /* mark node as old */
92 v_info->new_node = false;
93 splay_tree_remove (env->nodes_marked_new, v->uid);
95 v_info->dfn_number = env->count;
96 v_info->low_link = env->count;
98 env->stack[(env->stack_size)++] = v;
99 v_info->on_stack = true;
101 for (edge = v->callees; edge; edge = edge->next_callee)
103 struct ipa_dfs_info * w_info;
104 enum availability avail;
105 struct cgraph_node *w = cgraph_function_or_thunk_node (edge->callee, &avail);
107 if (!w || (ignore_edge && ignore_edge (edge)))
111 && (avail > AVAIL_OVERWRITABLE
112 || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE)))
114 w_info = (struct ipa_dfs_info *) w->aux;
115 if (w_info->new_node)
117 searchc (env, w, ignore_edge);
119 (v_info->low_link < w_info->low_link) ?
120 v_info->low_link : w_info->low_link;
123 if ((w_info->dfn_number < v_info->dfn_number)
124 && (w_info->on_stack))
126 (w_info->dfn_number < v_info->low_link) ?
127 w_info->dfn_number : v_info->low_link;
132 if (v_info->low_link == v_info->dfn_number)
134 struct cgraph_node *last = NULL;
135 struct cgraph_node *x;
136 struct ipa_dfs_info *x_info;
138 x = env->stack[--(env->stack_size)];
139 x_info = (struct ipa_dfs_info *) x->aux;
140 x_info->on_stack = false;
141 x_info->scc_no = v_info->dfn_number;
145 x_info->next_cycle = last;
149 env->result[env->order_pos++] = x;
153 env->result[env->order_pos++] = v;
157 /* Topsort the call graph by caller relation. Put the result in ORDER.
159 The REDUCE flag is true if you want the cycles reduced to single nodes. Set
160 ALLOW_OVERWRITABLE if nodes with such availability should be included.
161 IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
162 for the topological sort. */
165 ipa_reduced_postorder (struct cgraph_node **order,
166 bool reduce, bool allow_overwritable,
167 bool (*ignore_edge) (struct cgraph_edge *))
169 struct cgraph_node *node;
170 struct searchc_env env;
171 splay_tree_node result;
172 env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
176 env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
179 env.allow_overwritable = allow_overwritable;
181 for (node = cgraph_nodes; node; node = node->next)
183 enum availability avail = cgraph_function_body_availability (node);
185 if (avail > AVAIL_OVERWRITABLE
186 || (allow_overwritable
187 && (avail == AVAIL_OVERWRITABLE)))
189 /* Reuse the info if it is already there. */
190 struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
192 info = XCNEW (struct ipa_dfs_info);
193 info->new_node = true;
194 info->on_stack = false;
195 info->next_cycle = NULL;
198 splay_tree_insert (env.nodes_marked_new,
199 (splay_tree_key)node->uid,
200 (splay_tree_value)node);
205 result = splay_tree_min (env.nodes_marked_new);
208 node = (struct cgraph_node *)result->value;
209 searchc (&env, node, ignore_edge);
210 result = splay_tree_min (env.nodes_marked_new);
212 splay_tree_delete (env.nodes_marked_new);
215 return env.order_pos;
218 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
222 ipa_free_postorder_info (void)
224 struct cgraph_node *node;
225 for (node = cgraph_nodes; node; node = node->next)
227 /* Get rid of the aux information. */
236 /* Fill array order with all nodes with output flag set in the reverse
237 topological order. Return the number of elements in the array. */
240 ipa_reverse_postorder (struct cgraph_node **order)
242 struct cgraph_node *node, *node2;
245 struct cgraph_edge *edge, last;
248 struct cgraph_node **stack =
249 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
251 /* We have to deal with cycles nicely, so use a depth first traversal
252 output algorithm. Ignore the fact that some functions won't need
253 to be output and put them into order as well, so we get dependencies
254 right through inline functions. */
255 for (node = cgraph_nodes; node; node = node->next)
257 for (pass = 0; pass < 2; pass++)
258 for (node = cgraph_nodes; node; node = node->next)
261 || (!node->address_taken
262 && !node->global.inlined_to
263 && !cgraph_only_called_directly_p (node))))
269 node->aux = node->callers;
272 while (node2->aux != &last)
274 edge = (struct cgraph_edge *) node2->aux;
275 if (edge->next_caller)
276 node2->aux = edge->next_caller;
279 /* Break possible cycles involving always-inline
280 functions by ignoring edges from always-inline
281 functions to non-always-inline functions. */
282 if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
283 && !DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl))
285 if (!edge->caller->aux)
287 if (!edge->caller->callers)
288 edge->caller->aux = &last;
290 edge->caller->aux = edge->caller->callers;
291 stack[stack_size++] = node2;
292 node2 = edge->caller;
296 if (node2->aux == &last)
298 order[order_pos++] = node2;
300 node2 = stack[--stack_size];
307 for (node = cgraph_nodes; node; node = node->next)
314 /* Given a memory reference T, will return the variable at the bottom
315 of the access. Unlike get_base_address, this will recurse thru
319 get_base_var (tree t)
321 while (!SSA_VAR_P (t)
322 && (!CONSTANT_CLASS_P (t))
323 && TREE_CODE (t) != LABEL_DECL
324 && TREE_CODE (t) != FUNCTION_DECL
325 && TREE_CODE (t) != CONST_DECL
326 && TREE_CODE (t) != CONSTRUCTOR)
328 t = TREE_OPERAND (t, 0);
334 /* Create a new cgraph node set. */
337 cgraph_node_set_new (void)
339 cgraph_node_set new_node_set;
341 new_node_set = XCNEW (struct cgraph_node_set_def);
342 new_node_set->map = pointer_map_create ();
343 new_node_set->nodes = NULL;
348 /* Add cgraph_node NODE to cgraph_node_set SET. */
351 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
355 slot = pointer_map_insert (set->map, node);
359 int index = (size_t) *slot - 1;
360 gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
365 *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
367 /* Insert into node vector. */
368 VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
372 /* Remove cgraph_node NODE from cgraph_node_set SET. */
375 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
377 void **slot, **last_slot;
379 struct cgraph_node *last_node;
381 slot = pointer_map_contains (set->map, node);
382 if (slot == NULL || !*slot)
385 index = (size_t) *slot - 1;
386 gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
389 /* Remove from vector. We do this by swapping node with the last element
391 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
392 if (last_node != node)
394 last_slot = pointer_map_contains (set->map, last_node);
395 gcc_checking_assert (last_slot && *last_slot);
396 *last_slot = (void *)(size_t) (index + 1);
398 /* Move the last element to the original spot of NODE. */
399 VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
402 /* Remove element from hash table. */
407 /* Find NODE in SET and return an iterator to it if found. A null iterator
408 is returned if NODE is not in SET. */
410 cgraph_node_set_iterator
411 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
414 cgraph_node_set_iterator csi;
416 slot = pointer_map_contains (set->map, node);
417 if (slot == NULL || !*slot)
418 csi.index = (unsigned) ~0;
420 csi.index = (size_t)*slot - 1;
427 /* Dump content of SET to file F. */
430 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
432 cgraph_node_set_iterator iter;
434 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
436 struct cgraph_node *node = csi_node (iter);
437 fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
443 /* Dump content of SET to stderr. */
446 debug_cgraph_node_set (cgraph_node_set set)
448 dump_cgraph_node_set (stderr, set);
452 /* Free varpool node set. */
455 free_cgraph_node_set (cgraph_node_set set)
457 VEC_free (cgraph_node_ptr, heap, set->nodes);
458 pointer_map_destroy (set->map);
463 /* Create a new varpool node set. */
466 varpool_node_set_new (void)
468 varpool_node_set new_node_set;
470 new_node_set = XCNEW (struct varpool_node_set_def);
471 new_node_set->map = pointer_map_create ();
472 new_node_set->nodes = NULL;
477 /* Add varpool_node NODE to varpool_node_set SET. */
480 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
484 slot = pointer_map_insert (set->map, node);
488 int index = (size_t) *slot - 1;
489 gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
494 *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
496 /* Insert into node vector. */
497 VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
501 /* Remove varpool_node NODE from varpool_node_set SET. */
504 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
506 void **slot, **last_slot;
508 struct varpool_node *last_node;
510 slot = pointer_map_contains (set->map, node);
511 if (slot == NULL || !*slot)
514 index = (size_t) *slot - 1;
515 gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
518 /* Remove from vector. We do this by swapping node with the last element
520 last_node = VEC_pop (varpool_node_ptr, set->nodes);
521 if (last_node != node)
523 last_slot = pointer_map_contains (set->map, last_node);
524 gcc_checking_assert (last_slot && *last_slot);
525 *last_slot = (void *)(size_t) (index + 1);
527 /* Move the last element to the original spot of NODE. */
528 VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
531 /* Remove element from hash table. */
536 /* Find NODE in SET and return an iterator to it if found. A null iterator
537 is returned if NODE is not in SET. */
539 varpool_node_set_iterator
540 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
543 varpool_node_set_iterator vsi;
545 slot = pointer_map_contains (set->map, node);
546 if (slot == NULL || !*slot)
547 vsi.index = (unsigned) ~0;
549 vsi.index = (size_t)*slot - 1;
556 /* Dump content of SET to file F. */
559 dump_varpool_node_set (FILE *f, varpool_node_set set)
561 varpool_node_set_iterator iter;
563 for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
565 struct varpool_node *node = vsi_node (iter);
566 fprintf (f, " %s", varpool_node_name (node));
572 /* Free varpool node set. */
575 free_varpool_node_set (varpool_node_set set)
577 VEC_free (varpool_node_ptr, heap, set->nodes);
578 pointer_map_destroy (set->map);
583 /* Dump content of SET to stderr. */
586 debug_varpool_node_set (varpool_node_set set)
588 dump_varpool_node_set (stderr, set);