1 /* Utilities for ipa analysis.
2 Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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
9 Software Foundation; either version 3, or (at your option) any later
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
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.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"
32 #include "ggc.h"
33 #include "ipa-utils.h"
34 #include "ipa-reference.h"
35 #include "gimple.h"
36 #include "cgraph.h"
37 #include "output.h"
38 #include "flags.h"
39 #include "timevar.h"
40 #include "diagnostic.h"
41 #include "langhooks.h"
42
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. */
46
47 void
ipa_print_order(FILE * out,const char * note,struct cgraph_node ** order,int count)48 ipa_print_order (FILE* out,
49 const char * note,
50 struct cgraph_node** order,
51 int count)
52 {
53 int i;
54 fprintf (out, "\n\n ordered call graph: %s\n", note);
55
56 for (i = count - 1; i >= 0; i--)
57 dump_cgraph_node(dump_file, order[i]);
58 fprintf (out, "\n");
59 fflush(out);
60 }
61
62
63 struct searchc_env {
64 struct cgraph_node **stack;
65 int stack_size;
66 struct cgraph_node **result;
67 int order_pos;
68 splay_tree nodes_marked_new;
69 bool reduce;
70 bool allow_overwritable;
71 int count;
72 };
73
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
82 searching from. */
83
84 static void
searchc(struct searchc_env * env,struct cgraph_node * v,bool (* ignore_edge)(struct cgraph_edge *))85 searchc (struct searchc_env* env, struct cgraph_node *v,
86 bool (*ignore_edge) (struct cgraph_edge *))
87 {
88 struct cgraph_edge *edge;
89 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
90
91 /* mark node as old */
92 v_info->new_node = false;
93 splay_tree_remove (env->nodes_marked_new, v->uid);
94
95 v_info->dfn_number = env->count;
96 v_info->low_link = env->count;
97 env->count++;
98 env->stack[(env->stack_size)++] = v;
99 v_info->on_stack = true;
100
101 for (edge = v->callees; edge; edge = edge->next_callee)
102 {
103 struct ipa_dfs_info * w_info;
104 enum availability avail;
105 struct cgraph_node *w = cgraph_function_or_thunk_node (edge->callee, &avail);
106
107 if (!w || (ignore_edge && ignore_edge (edge)))
108 continue;
109
110 if (w->aux
111 && (avail > AVAIL_OVERWRITABLE
112 || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE)))
113 {
114 w_info = (struct ipa_dfs_info *) w->aux;
115 if (w_info->new_node)
116 {
117 searchc (env, w, ignore_edge);
118 v_info->low_link =
119 (v_info->low_link < w_info->low_link) ?
120 v_info->low_link : w_info->low_link;
121 }
122 else
123 if ((w_info->dfn_number < v_info->dfn_number)
124 && (w_info->on_stack))
125 v_info->low_link =
126 (w_info->dfn_number < v_info->low_link) ?
127 w_info->dfn_number : v_info->low_link;
128 }
129 }
130
131
132 if (v_info->low_link == v_info->dfn_number)
133 {
134 struct cgraph_node *last = NULL;
135 struct cgraph_node *x;
136 struct ipa_dfs_info *x_info;
137 do {
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;
142
143 if (env->reduce)
144 {
145 x_info->next_cycle = last;
146 last = x;
147 }
148 else
149 env->result[env->order_pos++] = x;
150 }
151 while (v != x);
152 if (env->reduce)
153 env->result[env->order_pos++] = v;
154 }
155 }
156
157 /* Topsort the call graph by caller relation. Put the result in ORDER.
158
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. */
163
164 int
ipa_reduced_postorder(struct cgraph_node ** order,bool reduce,bool allow_overwritable,bool (* ignore_edge)(struct cgraph_edge *))165 ipa_reduced_postorder (struct cgraph_node **order,
166 bool reduce, bool allow_overwritable,
167 bool (*ignore_edge) (struct cgraph_edge *))
168 {
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);
173 env.stack_size = 0;
174 env.result = order;
175 env.order_pos = 0;
176 env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
177 env.count = 1;
178 env.reduce = reduce;
179 env.allow_overwritable = allow_overwritable;
180
181 for (node = cgraph_nodes; node; node = node->next)
182 {
183 enum availability avail = cgraph_function_body_availability (node);
184
185 if (avail > AVAIL_OVERWRITABLE
186 || (allow_overwritable
187 && (avail == AVAIL_OVERWRITABLE)))
188 {
189 /* Reuse the info if it is already there. */
190 struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
191 if (!info)
192 info = XCNEW (struct ipa_dfs_info);
193 info->new_node = true;
194 info->on_stack = false;
195 info->next_cycle = NULL;
196 node->aux = info;
197
198 splay_tree_insert (env.nodes_marked_new,
199 (splay_tree_key)node->uid,
200 (splay_tree_value)node);
201 }
202 else
203 node->aux = NULL;
204 }
205 result = splay_tree_min (env.nodes_marked_new);
206 while (result)
207 {
208 node = (struct cgraph_node *)result->value;
209 searchc (&env, node, ignore_edge);
210 result = splay_tree_min (env.nodes_marked_new);
211 }
212 splay_tree_delete (env.nodes_marked_new);
213 free (env.stack);
214
215 return env.order_pos;
216 }
217
218 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
219 graph nodes. */
220
221 void
ipa_free_postorder_info(void)222 ipa_free_postorder_info (void)
223 {
224 struct cgraph_node *node;
225 for (node = cgraph_nodes; node; node = node->next)
226 {
227 /* Get rid of the aux information. */
228 if (node->aux)
229 {
230 free (node->aux);
231 node->aux = NULL;
232 }
233 }
234 }
235
236 struct postorder_stack
237 {
238 struct cgraph_node *node;
239 struct cgraph_edge *edge;
240 int ref;
241 };
242
243 /* Fill array order with all nodes with output flag set in the reverse
244 topological order. Return the number of elements in the array.
245 FIXME: While walking, consider aliases, too. */
246
247 int
ipa_reverse_postorder(struct cgraph_node ** order)248 ipa_reverse_postorder (struct cgraph_node **order)
249 {
250 struct cgraph_node *node, *node2;
251 int stack_size = 0;
252 int order_pos = 0;
253 struct cgraph_edge *edge;
254 int pass;
255 struct ipa_ref *ref;
256
257 struct postorder_stack *stack =
258 XCNEWVEC (struct postorder_stack, cgraph_n_nodes);
259
260 /* We have to deal with cycles nicely, so use a depth first traversal
261 output algorithm. Ignore the fact that some functions won't need
262 to be output and put them into order as well, so we get dependencies
263 right through inline functions. */
264 for (node = cgraph_nodes; node; node = node->next)
265 node->aux = NULL;
266 for (pass = 0; pass < 2; pass++)
267 for (node = cgraph_nodes; node; node = node->next)
268 if (!node->aux
269 && (pass
270 || (!node->address_taken
271 && !node->global.inlined_to
272 && !node->alias && !node->thunk.thunk_p
273 && !cgraph_only_called_directly_p (node))))
274 {
275 stack_size = 0;
276 stack[stack_size].node = node;
277 stack[stack_size].edge = node->callers;
278 stack[stack_size].ref = 0;
279 node->aux = (void *)(size_t)1;
280 while (stack_size >= 0)
281 {
282 while (true)
283 {
284 node2 = NULL;
285 while (stack[stack_size].edge && !node2)
286 {
287 edge = stack[stack_size].edge;
288 node2 = edge->caller;
289 stack[stack_size].edge = edge->next_caller;
290 /* Break possible cycles involving always-inline
291 functions by ignoring edges from always-inline
292 functions to non-always-inline functions. */
293 if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
294 && !DECL_DISREGARD_INLINE_LIMITS
295 (cgraph_function_node (edge->callee, NULL)->decl))
296 node2 = NULL;
297 }
298 for (;ipa_ref_list_refering_iterate (&stack[stack_size].node->ref_list,
299 stack[stack_size].ref,
300 ref) && !node2;
301 stack[stack_size].ref++)
302 {
303 if (ref->use == IPA_REF_ALIAS)
304 node2 = ipa_ref_refering_node (ref);
305 }
306 if (!node2)
307 break;
308 if (!node2->aux)
309 {
310 stack[++stack_size].node = node2;
311 stack[stack_size].edge = node2->callers;
312 stack[stack_size].ref = 0;
313 node2->aux = (void *)(size_t)1;
314 }
315 }
316 order[order_pos++] = stack[stack_size--].node;
317 }
318 }
319 free (stack);
320 for (node = cgraph_nodes; node; node = node->next)
321 node->aux = NULL;
322 return order_pos;
323 }
324
325
326
327 /* Given a memory reference T, will return the variable at the bottom
328 of the access. Unlike get_base_address, this will recurse thru
329 INDIRECT_REFS. */
330
331 tree
get_base_var(tree t)332 get_base_var (tree t)
333 {
334 while (!SSA_VAR_P (t)
335 && (!CONSTANT_CLASS_P (t))
336 && TREE_CODE (t) != LABEL_DECL
337 && TREE_CODE (t) != FUNCTION_DECL
338 && TREE_CODE (t) != CONST_DECL
339 && TREE_CODE (t) != CONSTRUCTOR)
340 {
341 t = TREE_OPERAND (t, 0);
342 }
343 return t;
344 }
345
346
347 /* Create a new cgraph node set. */
348
349 cgraph_node_set
cgraph_node_set_new(void)350 cgraph_node_set_new (void)
351 {
352 cgraph_node_set new_node_set;
353
354 new_node_set = XCNEW (struct cgraph_node_set_def);
355 new_node_set->map = pointer_map_create ();
356 new_node_set->nodes = NULL;
357 return new_node_set;
358 }
359
360
361 /* Add cgraph_node NODE to cgraph_node_set SET. */
362
363 void
cgraph_node_set_add(cgraph_node_set set,struct cgraph_node * node)364 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
365 {
366 void **slot;
367
368 slot = pointer_map_insert (set->map, node);
369
370 if (*slot)
371 {
372 int index = (size_t) *slot - 1;
373 gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
374 == node));
375 return;
376 }
377
378 *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
379
380 /* Insert into node vector. */
381 VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
382 }
383
384
385 /* Remove cgraph_node NODE from cgraph_node_set SET. */
386
387 void
cgraph_node_set_remove(cgraph_node_set set,struct cgraph_node * node)388 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
389 {
390 void **slot, **last_slot;
391 int index;
392 struct cgraph_node *last_node;
393
394 slot = pointer_map_contains (set->map, node);
395 if (slot == NULL || !*slot)
396 return;
397
398 index = (size_t) *slot - 1;
399 gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
400 == node);
401
402 /* Remove from vector. We do this by swapping node with the last element
403 of the vector. */
404 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
405 if (last_node != node)
406 {
407 last_slot = pointer_map_contains (set->map, last_node);
408 gcc_checking_assert (last_slot && *last_slot);
409 *last_slot = (void *)(size_t) (index + 1);
410
411 /* Move the last element to the original spot of NODE. */
412 VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
413 }
414
415 /* Remove element from hash table. */
416 *slot = NULL;
417 }
418
419
420 /* Find NODE in SET and return an iterator to it if found. A null iterator
421 is returned if NODE is not in SET. */
422
423 cgraph_node_set_iterator
cgraph_node_set_find(cgraph_node_set set,struct cgraph_node * node)424 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
425 {
426 void **slot;
427 cgraph_node_set_iterator csi;
428
429 slot = pointer_map_contains (set->map, node);
430 if (slot == NULL || !*slot)
431 csi.index = (unsigned) ~0;
432 else
433 csi.index = (size_t)*slot - 1;
434 csi.set = set;
435
436 return csi;
437 }
438
439
440 /* Dump content of SET to file F. */
441
442 void
dump_cgraph_node_set(FILE * f,cgraph_node_set set)443 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
444 {
445 cgraph_node_set_iterator iter;
446
447 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
448 {
449 struct cgraph_node *node = csi_node (iter);
450 fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
451 }
452 fprintf (f, "\n");
453 }
454
455
456 /* Dump content of SET to stderr. */
457
458 DEBUG_FUNCTION void
debug_cgraph_node_set(cgraph_node_set set)459 debug_cgraph_node_set (cgraph_node_set set)
460 {
461 dump_cgraph_node_set (stderr, set);
462 }
463
464
465 /* Free varpool node set. */
466
467 void
free_cgraph_node_set(cgraph_node_set set)468 free_cgraph_node_set (cgraph_node_set set)
469 {
470 VEC_free (cgraph_node_ptr, heap, set->nodes);
471 pointer_map_destroy (set->map);
472 free (set);
473 }
474
475
476 /* Create a new varpool node set. */
477
478 varpool_node_set
varpool_node_set_new(void)479 varpool_node_set_new (void)
480 {
481 varpool_node_set new_node_set;
482
483 new_node_set = XCNEW (struct varpool_node_set_def);
484 new_node_set->map = pointer_map_create ();
485 new_node_set->nodes = NULL;
486 return new_node_set;
487 }
488
489
490 /* Add varpool_node NODE to varpool_node_set SET. */
491
492 void
varpool_node_set_add(varpool_node_set set,struct varpool_node * node)493 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
494 {
495 void **slot;
496
497 slot = pointer_map_insert (set->map, node);
498
499 if (*slot)
500 {
501 int index = (size_t) *slot - 1;
502 gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
503 == node));
504 return;
505 }
506
507 *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
508
509 /* Insert into node vector. */
510 VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
511 }
512
513
514 /* Remove varpool_node NODE from varpool_node_set SET. */
515
516 void
varpool_node_set_remove(varpool_node_set set,struct varpool_node * node)517 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
518 {
519 void **slot, **last_slot;
520 int index;
521 struct varpool_node *last_node;
522
523 slot = pointer_map_contains (set->map, node);
524 if (slot == NULL || !*slot)
525 return;
526
527 index = (size_t) *slot - 1;
528 gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
529 == node);
530
531 /* Remove from vector. We do this by swapping node with the last element
532 of the vector. */
533 last_node = VEC_pop (varpool_node_ptr, set->nodes);
534 if (last_node != node)
535 {
536 last_slot = pointer_map_contains (set->map, last_node);
537 gcc_checking_assert (last_slot && *last_slot);
538 *last_slot = (void *)(size_t) (index + 1);
539
540 /* Move the last element to the original spot of NODE. */
541 VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
542 }
543
544 /* Remove element from hash table. */
545 *slot = NULL;
546 }
547
548
549 /* Find NODE in SET and return an iterator to it if found. A null iterator
550 is returned if NODE is not in SET. */
551
552 varpool_node_set_iterator
varpool_node_set_find(varpool_node_set set,struct varpool_node * node)553 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
554 {
555 void **slot;
556 varpool_node_set_iterator vsi;
557
558 slot = pointer_map_contains (set->map, node);
559 if (slot == NULL || !*slot)
560 vsi.index = (unsigned) ~0;
561 else
562 vsi.index = (size_t)*slot - 1;
563 vsi.set = set;
564
565 return vsi;
566 }
567
568
569 /* Dump content of SET to file F. */
570
571 void
dump_varpool_node_set(FILE * f,varpool_node_set set)572 dump_varpool_node_set (FILE *f, varpool_node_set set)
573 {
574 varpool_node_set_iterator iter;
575
576 for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
577 {
578 struct varpool_node *node = vsi_node (iter);
579 fprintf (f, " %s", varpool_node_name (node));
580 }
581 fprintf (f, "\n");
582 }
583
584
585 /* Free varpool node set. */
586
587 void
free_varpool_node_set(varpool_node_set set)588 free_varpool_node_set (varpool_node_set set)
589 {
590 VEC_free (varpool_node_ptr, heap, set->nodes);
591 pointer_map_destroy (set->map);
592 free (set);
593 }
594
595
596 /* Dump content of SET to stderr. */
597
598 DEBUG_FUNCTION void
debug_varpool_node_set(varpool_node_set set)599 debug_varpool_node_set (varpool_node_set set)
600 {
601 dump_varpool_node_set (stderr, set);
602 }
603