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"
29 #include "langhooks.h"
30 #include "pointer-set.h"
31 #include "splay-tree.h"
33 #include "ipa-utils.h"
34 #include "ipa-reference.h"
38 #include "diagnostic.h"
39 #include "langhooks.h"
41 /* Debugging function for postorder and inorder code. NOTE is a string
42 that is printed before the nodes are printed. ORDER is an array of
43 cgraph_nodes that has COUNT useful nodes in it. */
46 ipa_print_order (FILE* out
,
48 struct cgraph_node
** order
,
52 fprintf (out
, "\n\n ordered call graph: %s\n", note
);
54 for (i
= count
- 1; i
>= 0; i
--)
55 dump_cgraph_node(dump_file
, order
[i
]);
62 struct cgraph_node
**stack
;
64 struct cgraph_node
**result
;
66 splay_tree nodes_marked_new
;
68 bool allow_overwritable
;
72 /* This is an implementation of Tarjan's strongly connected region
73 finder as reprinted in Aho Hopcraft and Ullman's The Design and
74 Analysis of Computer Programs (1975) pages 192-193. This version
75 has been customized for cgraph_nodes. The env parameter is because
76 it is recursive and there are no nested functions here. This
77 function should only be called from itself or
78 ipa_reduced_postorder. ENV is a stack env and would be
79 unnecessary if C had nested functions. V is the node to start
83 searchc (struct searchc_env
* env
, struct cgraph_node
*v
,
84 bool (*ignore_edge
) (struct cgraph_edge
*))
86 struct cgraph_edge
*edge
;
87 struct ipa_dfs_info
*v_info
= (struct ipa_dfs_info
*) v
->symbol
.aux
;
89 /* mark node as old */
90 v_info
->new_node
= false;
91 splay_tree_remove (env
->nodes_marked_new
, v
->uid
);
93 v_info
->dfn_number
= env
->count
;
94 v_info
->low_link
= env
->count
;
96 env
->stack
[(env
->stack_size
)++] = v
;
97 v_info
->on_stack
= true;
99 for (edge
= v
->callees
; edge
; edge
= edge
->next_callee
)
101 struct ipa_dfs_info
* w_info
;
102 enum availability avail
;
103 struct cgraph_node
*w
= cgraph_function_or_thunk_node (edge
->callee
, &avail
);
105 if (!w
|| (ignore_edge
&& ignore_edge (edge
)))
109 && (avail
> AVAIL_OVERWRITABLE
110 || (env
->allow_overwritable
&& avail
== AVAIL_OVERWRITABLE
)))
112 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
113 if (w_info
->new_node
)
115 searchc (env
, w
, ignore_edge
);
117 (v_info
->low_link
< w_info
->low_link
) ?
118 v_info
->low_link
: w_info
->low_link
;
121 if ((w_info
->dfn_number
< v_info
->dfn_number
)
122 && (w_info
->on_stack
))
124 (w_info
->dfn_number
< v_info
->low_link
) ?
125 w_info
->dfn_number
: v_info
->low_link
;
130 if (v_info
->low_link
== v_info
->dfn_number
)
132 struct cgraph_node
*last
= NULL
;
133 struct cgraph_node
*x
;
134 struct ipa_dfs_info
*x_info
;
136 x
= env
->stack
[--(env
->stack_size
)];
137 x_info
= (struct ipa_dfs_info
*) x
->symbol
.aux
;
138 x_info
->on_stack
= false;
139 x_info
->scc_no
= v_info
->dfn_number
;
143 x_info
->next_cycle
= last
;
147 env
->result
[env
->order_pos
++] = x
;
151 env
->result
[env
->order_pos
++] = v
;
155 /* Topsort the call graph by caller relation. Put the result in ORDER.
157 The REDUCE flag is true if you want the cycles reduced to single nodes.
158 You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
159 call graph nodes in a reduced node.
161 Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
162 IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
163 for the topological sort. */
166 ipa_reduced_postorder (struct cgraph_node
**order
,
167 bool reduce
, bool allow_overwritable
,
168 bool (*ignore_edge
) (struct cgraph_edge
*))
170 struct cgraph_node
*node
;
171 struct searchc_env env
;
172 splay_tree_node result
;
173 env
.stack
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
177 env
.nodes_marked_new
= splay_tree_new (splay_tree_compare_ints
, 0, 0);
180 env
.allow_overwritable
= allow_overwritable
;
182 FOR_EACH_DEFINED_FUNCTION (node
)
184 enum availability avail
= cgraph_function_body_availability (node
);
186 if (avail
> AVAIL_OVERWRITABLE
187 || (allow_overwritable
188 && (avail
== AVAIL_OVERWRITABLE
)))
190 /* Reuse the info if it is already there. */
191 struct ipa_dfs_info
*info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
193 info
= XCNEW (struct ipa_dfs_info
);
194 info
->new_node
= true;
195 info
->on_stack
= false;
196 info
->next_cycle
= NULL
;
197 node
->symbol
.aux
= info
;
199 splay_tree_insert (env
.nodes_marked_new
,
200 (splay_tree_key
)node
->uid
,
201 (splay_tree_value
)node
);
204 node
->symbol
.aux
= NULL
;
206 result
= splay_tree_min (env
.nodes_marked_new
);
209 node
= (struct cgraph_node
*)result
->value
;
210 searchc (&env
, node
, ignore_edge
);
211 result
= splay_tree_min (env
.nodes_marked_new
);
213 splay_tree_delete (env
.nodes_marked_new
);
216 return env
.order_pos
;
219 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
223 ipa_free_postorder_info (void)
225 struct cgraph_node
*node
;
226 FOR_EACH_DEFINED_FUNCTION (node
)
228 /* Get rid of the aux information. */
229 if (node
->symbol
.aux
)
231 free (node
->symbol
.aux
);
232 node
->symbol
.aux
= NULL
;
237 /* Get the set of nodes for the cycle in the reduced call graph starting
241 ipa_get_nodes_in_cycle (struct cgraph_node
*node
)
243 vec
<cgraph_node_ptr
> v
= vNULL
;
244 struct ipa_dfs_info
*node_dfs_info
;
248 node_dfs_info
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
249 node
= node_dfs_info
->next_cycle
;
254 struct postorder_stack
256 struct cgraph_node
*node
;
257 struct cgraph_edge
*edge
;
261 /* Fill array order with all nodes with output flag set in the reverse
262 topological order. Return the number of elements in the array.
263 FIXME: While walking, consider aliases, too. */
266 ipa_reverse_postorder (struct cgraph_node
**order
)
268 struct cgraph_node
*node
, *node2
;
271 struct cgraph_edge
*edge
;
275 struct postorder_stack
*stack
=
276 XCNEWVEC (struct postorder_stack
, cgraph_n_nodes
);
278 /* We have to deal with cycles nicely, so use a depth first traversal
279 output algorithm. Ignore the fact that some functions won't need
280 to be output and put them into order as well, so we get dependencies
281 right through inline functions. */
282 FOR_EACH_FUNCTION (node
)
283 node
->symbol
.aux
= NULL
;
284 for (pass
= 0; pass
< 2; pass
++)
285 FOR_EACH_FUNCTION (node
)
286 if (!node
->symbol
.aux
288 || (!node
->symbol
.address_taken
289 && !node
->global
.inlined_to
290 && !node
->alias
&& !node
->thunk
.thunk_p
291 && !cgraph_only_called_directly_p (node
))))
294 stack
[stack_size
].node
= node
;
295 stack
[stack_size
].edge
= node
->callers
;
296 stack
[stack_size
].ref
= 0;
297 node
->symbol
.aux
= (void *)(size_t)1;
298 while (stack_size
>= 0)
303 while (stack
[stack_size
].edge
&& !node2
)
305 edge
= stack
[stack_size
].edge
;
306 node2
= edge
->caller
;
307 stack
[stack_size
].edge
= edge
->next_caller
;
308 /* Break possible cycles involving always-inline
309 functions by ignoring edges from always-inline
310 functions to non-always-inline functions. */
311 if (DECL_DISREGARD_INLINE_LIMITS (edge
->caller
->symbol
.decl
)
312 && !DECL_DISREGARD_INLINE_LIMITS
313 (cgraph_function_node (edge
->callee
, NULL
)->symbol
.decl
))
316 for (;ipa_ref_list_referring_iterate (&stack
[stack_size
].node
->symbol
.ref_list
,
317 stack
[stack_size
].ref
,
319 stack
[stack_size
].ref
++)
321 if (ref
->use
== IPA_REF_ALIAS
)
322 node2
= ipa_ref_referring_node (ref
);
326 if (!node2
->symbol
.aux
)
328 stack
[++stack_size
].node
= node2
;
329 stack
[stack_size
].edge
= node2
->callers
;
330 stack
[stack_size
].ref
= 0;
331 node2
->symbol
.aux
= (void *)(size_t)1;
334 order
[order_pos
++] = stack
[stack_size
--].node
;
338 FOR_EACH_FUNCTION (node
)
339 node
->symbol
.aux
= NULL
;
345 /* Given a memory reference T, will return the variable at the bottom
346 of the access. Unlike get_base_address, this will recurse through
350 get_base_var (tree t
)
352 while (!SSA_VAR_P (t
)
353 && (!CONSTANT_CLASS_P (t
))
354 && TREE_CODE (t
) != LABEL_DECL
355 && TREE_CODE (t
) != FUNCTION_DECL
356 && TREE_CODE (t
) != CONST_DECL
357 && TREE_CODE (t
) != CONSTRUCTOR
)
359 t
= TREE_OPERAND (t
, 0);
365 /* Create a new cgraph node set. */
368 cgraph_node_set_new (void)
370 cgraph_node_set new_node_set
;
372 new_node_set
= XCNEW (struct cgraph_node_set_def
);
373 new_node_set
->map
= pointer_map_create ();
374 new_node_set
->nodes
.create (0);
379 /* Add cgraph_node NODE to cgraph_node_set SET. */
382 cgraph_node_set_add (cgraph_node_set set
, struct cgraph_node
*node
)
386 slot
= pointer_map_insert (set
->map
, node
);
390 int index
= (size_t) *slot
- 1;
391 gcc_checking_assert ((set
->nodes
[index
]
396 *slot
= (void *)(size_t) (set
->nodes
.length () + 1);
398 /* Insert into node vector. */
399 set
->nodes
.safe_push (node
);
403 /* Remove cgraph_node NODE from cgraph_node_set SET. */
406 cgraph_node_set_remove (cgraph_node_set set
, struct cgraph_node
*node
)
408 void **slot
, **last_slot
;
410 struct cgraph_node
*last_node
;
412 slot
= pointer_map_contains (set
->map
, node
);
413 if (slot
== NULL
|| !*slot
)
416 index
= (size_t) *slot
- 1;
417 gcc_checking_assert (set
->nodes
[index
]
420 /* Remove from vector. We do this by swapping node with the last element
422 last_node
= set
->nodes
.pop ();
423 if (last_node
!= node
)
425 last_slot
= pointer_map_contains (set
->map
, last_node
);
426 gcc_checking_assert (last_slot
&& *last_slot
);
427 *last_slot
= (void *)(size_t) (index
+ 1);
429 /* Move the last element to the original spot of NODE. */
430 set
->nodes
[index
] = last_node
;
433 /* Remove element from hash table. */
438 /* Find NODE in SET and return an iterator to it if found. A null iterator
439 is returned if NODE is not in SET. */
441 cgraph_node_set_iterator
442 cgraph_node_set_find (cgraph_node_set set
, struct cgraph_node
*node
)
445 cgraph_node_set_iterator csi
;
447 slot
= pointer_map_contains (set
->map
, node
);
448 if (slot
== NULL
|| !*slot
)
449 csi
.index
= (unsigned) ~0;
451 csi
.index
= (size_t)*slot
- 1;
458 /* Dump content of SET to file F. */
461 dump_cgraph_node_set (FILE *f
, cgraph_node_set set
)
463 cgraph_node_set_iterator iter
;
465 for (iter
= csi_start (set
); !csi_end_p (iter
); csi_next (&iter
))
467 struct cgraph_node
*node
= csi_node (iter
);
468 fprintf (f
, " %s/%i", cgraph_node_name (node
), node
->uid
);
474 /* Dump content of SET to stderr. */
477 debug_cgraph_node_set (cgraph_node_set set
)
479 dump_cgraph_node_set (stderr
, set
);
483 /* Free varpool node set. */
486 free_cgraph_node_set (cgraph_node_set set
)
488 set
->nodes
.release ();
489 pointer_map_destroy (set
->map
);
494 /* Create a new varpool node set. */
497 varpool_node_set_new (void)
499 varpool_node_set new_node_set
;
501 new_node_set
= XCNEW (struct varpool_node_set_def
);
502 new_node_set
->map
= pointer_map_create ();
503 new_node_set
->nodes
.create (0);
508 /* Add varpool_node NODE to varpool_node_set SET. */
511 varpool_node_set_add (varpool_node_set set
, struct varpool_node
*node
)
515 slot
= pointer_map_insert (set
->map
, node
);
519 int index
= (size_t) *slot
- 1;
520 gcc_checking_assert ((set
->nodes
[index
]
525 *slot
= (void *)(size_t) (set
->nodes
.length () + 1);
527 /* Insert into node vector. */
528 set
->nodes
.safe_push (node
);
532 /* Remove varpool_node NODE from varpool_node_set SET. */
535 varpool_node_set_remove (varpool_node_set set
, struct varpool_node
*node
)
537 void **slot
, **last_slot
;
539 struct varpool_node
*last_node
;
541 slot
= pointer_map_contains (set
->map
, node
);
542 if (slot
== NULL
|| !*slot
)
545 index
= (size_t) *slot
- 1;
546 gcc_checking_assert (set
->nodes
[index
]
549 /* Remove from vector. We do this by swapping node with the last element
551 last_node
= set
->nodes
.pop ();
552 if (last_node
!= node
)
554 last_slot
= pointer_map_contains (set
->map
, last_node
);
555 gcc_checking_assert (last_slot
&& *last_slot
);
556 *last_slot
= (void *)(size_t) (index
+ 1);
558 /* Move the last element to the original spot of NODE. */
559 set
->nodes
[index
] = last_node
;
562 /* Remove element from hash table. */
567 /* Find NODE in SET and return an iterator to it if found. A null iterator
568 is returned if NODE is not in SET. */
570 varpool_node_set_iterator
571 varpool_node_set_find (varpool_node_set set
, struct varpool_node
*node
)
574 varpool_node_set_iterator vsi
;
576 slot
= pointer_map_contains (set
->map
, node
);
577 if (slot
== NULL
|| !*slot
)
578 vsi
.index
= (unsigned) ~0;
580 vsi
.index
= (size_t)*slot
- 1;
587 /* Dump content of SET to file F. */
590 dump_varpool_node_set (FILE *f
, varpool_node_set set
)
592 varpool_node_set_iterator iter
;
594 for (iter
= vsi_start (set
); !vsi_end_p (iter
); vsi_next (&iter
))
596 struct varpool_node
*node
= vsi_node (iter
);
597 fprintf (f
, " %s", varpool_node_name (node
));
603 /* Free varpool node set. */
606 free_varpool_node_set (varpool_node_set set
)
608 set
->nodes
.release ();
609 pointer_map_destroy (set
->map
);
614 /* Dump content of SET to stderr. */
617 debug_varpool_node_set (varpool_node_set set
)
619 dump_varpool_node_set (stderr
, set
);