]> git.ipfire.org Git - thirdparty/binutils-gdb.git/blob - gprof/cg_arcs.c
* config/sh/tm-sh.h (BELIEVE_PCC_PROMOTION): Define, so that
[thirdparty/binutils-gdb.git] / gprof / cg_arcs.c
1 /*
2 * Copyright (c) 1983 Regents of the University of California.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms are permitted
6 * provided that: (1) source distributions retain this entire copyright
7 * notice and comment, and (2) distributions including binaries display
8 * the following acknowledgement: ``This product includes software
9 * developed by the University of California, Berkeley and its contributors''
10 * in the documentation or other materials provided with the distribution
11 * and in all advertising materials mentioning features or use of this
12 * software. Neither the name of the University nor the names of its
13 * contributors may be used to endorse or promote products derived
14 * from this software without specific prior written permission.
15 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18 */
19 #include "libiberty.h"
20 #include "gprof.h"
21 #include "call_graph.h"
22 #include "cg_arcs.h"
23 #include "cg_dfn.h"
24 #include "cg_print.h"
25 #include "utils.h"
26 #include "sym_ids.h"
27
28 Sym *cycle_header;
29 unsigned int num_cycles;
30 Arc **arcs;
31 unsigned int numarcs;
32
33 /*
34 * Return TRUE iff PARENT has an arc to covers the address
35 * range covered by CHILD.
36 */
37 Arc *
38 DEFUN (arc_lookup, (parent, child), Sym * parent AND Sym * child)
39 {
40 Arc *arc;
41
42 if (!parent || !child)
43 {
44 printf ("[arc_lookup] parent == 0 || child == 0\n");
45 return 0;
46 }
47 DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
48 parent->name, child->name));
49 for (arc = parent->cg.children; arc; arc = arc->next_child)
50 {
51 DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
52 arc->parent->name, arc->child->name));
53 if (child->addr >= arc->child->addr
54 && child->end_addr <= arc->child->end_addr)
55 {
56 return arc;
57 }
58 }
59 return 0;
60 }
61
62
63 /*
64 * Add (or just increment) an arc:
65 */
66 void
67 DEFUN (arc_add, (parent, child, count),
68 Sym * parent AND Sym * child AND unsigned long count)
69 {
70 static unsigned int maxarcs = 0;
71 Arc *arc, **newarcs;
72
73 DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
74 count, parent->name, child->name));
75 arc = arc_lookup (parent, child);
76 if (arc)
77 {
78 /*
79 * A hit: just increment the count.
80 */
81 DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
82 arc->count, count));
83 arc->count += count;
84 return;
85 }
86 arc = (Arc *) xmalloc (sizeof (*arc));
87 memset (arc, 0, sizeof (*arc));
88 arc->parent = parent;
89 arc->child = child;
90 arc->count = count;
91
92 /* If this isn't an arc for a recursive call to parent, then add it
93 to the array of arcs. */
94 if (parent != child)
95 {
96 /* If we've exhausted space in our current array, get a new one
97 and copy the contents. We might want to throttle the doubling
98 factor one day. */
99 if (numarcs == maxarcs)
100 {
101 /* Determine how much space we want to allocate. */
102 if (maxarcs == 0)
103 maxarcs = 1;
104 maxarcs *= 2;
105
106 /* Allocate the new array. */
107 newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);
108
109 /* Copy the old array's contents into the new array. */
110 memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
111
112 /* Free up the old array. */
113 free (arcs);
114
115 /* And make the new array be the current array. */
116 arcs = newarcs;
117 }
118
119 /* Place this arc in the arc array. */
120 arcs[numarcs++] = arc;
121 }
122
123 /* prepend this child to the children of this parent: */
124 arc->next_child = parent->cg.children;
125 parent->cg.children = arc;
126
127 /* prepend this parent to the parents of this child: */
128 arc->next_parent = child->cg.parents;
129 child->cg.parents = arc;
130 }
131
132
133 static int
134 DEFUN (cmp_topo, (lp, rp), const PTR lp AND const PTR rp)
135 {
136 const Sym *left = *(const Sym **) lp;
137 const Sym *right = *(const Sym **) rp;
138
139 return left->cg.top_order - right->cg.top_order;
140 }
141
142
143 static void
144 DEFUN (propagate_time, (parent), Sym * parent)
145 {
146 Arc *arc;
147 Sym *child;
148 double share, prop_share;
149
150 if (parent->cg.prop.fract == 0.0)
151 {
152 return;
153 }
154
155 /* gather time from children of this parent: */
156
157 for (arc = parent->cg.children; arc; arc = arc->next_child)
158 {
159 child = arc->child;
160 if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
161 {
162 continue;
163 }
164 if (child->cg.cyc.head != child)
165 {
166 if (parent->cg.cyc.num == child->cg.cyc.num)
167 {
168 continue;
169 }
170 if (parent->cg.top_order <= child->cg.top_order)
171 {
172 fprintf (stderr, "[propagate] toporder botches\n");
173 }
174 child = child->cg.cyc.head;
175 }
176 else
177 {
178 if (parent->cg.top_order <= child->cg.top_order)
179 {
180 fprintf (stderr, "[propagate] toporder botches\n");
181 continue;
182 }
183 }
184 if (child->ncalls == 0)
185 {
186 continue;
187 }
188
189 /* distribute time for this arc: */
190 arc->time = child->hist.time * (((double) arc->count)
191 / ((double) child->ncalls));
192 arc->child_time = child->cg.child_time
193 * (((double) arc->count) / ((double) child->ncalls));
194 share = arc->time + arc->child_time;
195 parent->cg.child_time += share;
196
197 /* (1 - cg.prop.fract) gets lost along the way: */
198 prop_share = parent->cg.prop.fract * share;
199
200 /* fix things for printing: */
201 parent->cg.prop.child += prop_share;
202 arc->time *= parent->cg.prop.fract;
203 arc->child_time *= parent->cg.prop.fract;
204
205 /* add this share to the parent's cycle header, if any: */
206 if (parent->cg.cyc.head != parent)
207 {
208 parent->cg.cyc.head->cg.child_time += share;
209 parent->cg.cyc.head->cg.prop.child += prop_share;
210 }
211 DBG (PROPDEBUG,
212 printf ("[prop_time] child \t");
213 print_name (child);
214 printf (" with %f %f %lu/%lu\n", child->hist.time,
215 child->cg.child_time, arc->count, child->ncalls);
216 printf ("[prop_time] parent\t");
217 print_name (parent);
218 printf ("\n[prop_time] share %f\n", share));
219 }
220 }
221
222
223 /*
224 * Compute the time of a cycle as the sum of the times of all
225 * its members.
226 */
227 static void
228 DEFUN_VOID (cycle_time)
229 {
230 Sym *member, *cyc;
231
232 for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
233 {
234 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
235 {
236 if (member->cg.prop.fract == 0.0)
237 {
238 /*
239 * All members have the same propfraction except those
240 * that were excluded with -E.
241 */
242 continue;
243 }
244 cyc->hist.time += member->hist.time;
245 }
246 cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
247 }
248 }
249
250
251 static void
252 DEFUN_VOID (cycle_link)
253 {
254 Sym *sym, *cyc, *member;
255 Arc *arc;
256 int num;
257
258 /* count the number of cycles, and initialize the cycle lists: */
259
260 num_cycles = 0;
261 for (sym = symtab.base; sym < symtab.limit; ++sym)
262 {
263 /* this is how you find unattached cycles: */
264 if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
265 {
266 ++num_cycles;
267 }
268 }
269
270 /*
271 * cycle_header is indexed by cycle number: i.e. it is origin 1,
272 * not origin 0.
273 */
274 cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
275
276 /*
277 * Now link cycles to true cycle-heads, number them, accumulate
278 * the data for the cycle.
279 */
280 num = 0;
281 cyc = cycle_header;
282 for (sym = symtab.base; sym < symtab.limit; ++sym)
283 {
284 if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
285 {
286 continue;
287 }
288 ++num;
289 ++cyc;
290 sym_init (cyc);
291 cyc->cg.print_flag = TRUE; /* should this be printed? */
292 cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
293 cyc->cg.cyc.num = num; /* internal number of cycle on */
294 cyc->cg.cyc.head = cyc; /* pointer to head of cycle */
295 cyc->cg.cyc.next = sym; /* pointer to next member of cycle */
296 DBG (CYCLEDEBUG, printf ("[cycle_link] ");
297 print_name (sym);
298 printf (" is the head of cycle %d\n", num));
299
300 /* link members to cycle header: */
301 for (member = sym; member; member = member->cg.cyc.next)
302 {
303 member->cg.cyc.num = num;
304 member->cg.cyc.head = cyc;
305 }
306
307 /*
308 * Count calls from outside the cycle and those among cycle
309 * members:
310 */
311 for (member = sym; member; member = member->cg.cyc.next)
312 {
313 for (arc = member->cg.parents; arc; arc = arc->next_parent)
314 {
315 if (arc->parent == member)
316 {
317 continue;
318 }
319 if (arc->parent->cg.cyc.num == num)
320 {
321 cyc->cg.self_calls += arc->count;
322 }
323 else
324 {
325 cyc->ncalls += arc->count;
326 }
327 }
328 }
329 }
330 }
331
332
333 /*
334 * Check if any parent of this child (or outside parents of this
335 * cycle) have their print flags on and set the print flag of the
336 * child (cycle) appropriately. Similarly, deal with propagation
337 * fractions from parents.
338 */
339 static void
340 DEFUN (inherit_flags, (child), Sym * child)
341 {
342 Sym *head, *parent, *member;
343 Arc *arc;
344
345 head = child->cg.cyc.head;
346 if (child == head)
347 {
348 /* just a regular child, check its parents: */
349 child->cg.print_flag = FALSE;
350 child->cg.prop.fract = 0.0;
351 for (arc = child->cg.parents; arc; arc = arc->next_parent)
352 {
353 parent = arc->parent;
354 if (child == parent)
355 {
356 continue;
357 }
358 child->cg.print_flag |= parent->cg.print_flag;
359 /*
360 * If the child was never actually called (e.g., this arc
361 * is static (and all others are, too)) no time propagates
362 * along this arc.
363 */
364 if (child->ncalls != 0)
365 {
366 child->cg.prop.fract += parent->cg.prop.fract
367 * (((double) arc->count) / ((double) child->ncalls));
368 }
369 }
370 }
371 else
372 {
373 /*
374 * Its a member of a cycle, look at all parents from outside
375 * the cycle.
376 */
377 head->cg.print_flag = FALSE;
378 head->cg.prop.fract = 0.0;
379 for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
380 {
381 for (arc = member->cg.parents; arc; arc = arc->next_parent)
382 {
383 if (arc->parent->cg.cyc.head == head)
384 {
385 continue;
386 }
387 parent = arc->parent;
388 head->cg.print_flag |= parent->cg.print_flag;
389 /*
390 * If the cycle was never actually called (e.g. this
391 * arc is static (and all others are, too)) no time
392 * propagates along this arc.
393 */
394 if (head->ncalls != 0)
395 {
396 head->cg.prop.fract += parent->cg.prop.fract
397 * (((double) arc->count) / ((double) head->ncalls));
398 }
399 }
400 }
401 for (member = head; member; member = member->cg.cyc.next)
402 {
403 member->cg.print_flag = head->cg.print_flag;
404 member->cg.prop.fract = head->cg.prop.fract;
405 }
406 }
407 }
408
409
410 /*
411 * In one top-to-bottom pass over the topologically sorted symbols
412 * propagate:
413 * cg.print_flag as the union of parents' print_flags
414 * propfraction as the sum of fractional parents' propfractions
415 * and while we're here, sum time for functions.
416 */
417 static void
418 DEFUN (propagate_flags, (symbols), Sym ** symbols)
419 {
420 int index;
421 Sym *old_head, *child;
422
423 old_head = 0;
424 for (index = symtab.len - 1; index >= 0; --index)
425 {
426 child = symbols[index];
427 /*
428 * If we haven't done this function or cycle, inherit things
429 * from parent. This way, we are linear in the number of arcs
430 * since we do all members of a cycle (and the cycle itself)
431 * as we hit the first member of the cycle.
432 */
433 if (child->cg.cyc.head != old_head)
434 {
435 old_head = child->cg.cyc.head;
436 inherit_flags (child);
437 }
438 DBG (PROPDEBUG,
439 printf ("[prop_flags] ");
440 print_name (child);
441 printf ("inherits print-flag %d and prop-fract %f\n",
442 child->cg.print_flag, child->cg.prop.fract));
443 if (!child->cg.print_flag)
444 {
445 /*
446 * Printflag is off. It gets turned on by being in the
447 * INCL_GRAPH table, or there being an empty INCL_GRAPH
448 * table and not being in the EXCL_GRAPH table.
449 */
450 if (sym_lookup (&syms[INCL_GRAPH], child->addr)
451 || (syms[INCL_GRAPH].len == 0
452 && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
453 {
454 child->cg.print_flag = TRUE;
455 }
456 }
457 else
458 {
459 /*
460 * This function has printing parents: maybe someone wants
461 * to shut it up by putting it in the EXCL_GRAPH table.
462 * (But favor INCL_GRAPH over EXCL_GRAPH.)
463 */
464 if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
465 && sym_lookup (&syms[EXCL_GRAPH], child->addr))
466 {
467 child->cg.print_flag = FALSE;
468 }
469 }
470 if (child->cg.prop.fract == 0.0)
471 {
472 /*
473 * No parents to pass time to. Collect time from children
474 * if its in the INCL_TIME table, or there is an empty
475 * INCL_TIME table and its not in the EXCL_TIME table.
476 */
477 if (sym_lookup (&syms[INCL_TIME], child->addr)
478 || (syms[INCL_TIME].len == 0
479 && !sym_lookup (&syms[EXCL_TIME], child->addr)))
480 {
481 child->cg.prop.fract = 1.0;
482 }
483 }
484 else
485 {
486 /*
487 * It has parents to pass time to, but maybe someone wants
488 * to shut it up by puttting it in the EXCL_TIME table.
489 * (But favor being in INCL_TIME tabe over being in
490 * EXCL_TIME table.)
491 */
492 if (!sym_lookup (&syms[INCL_TIME], child->addr)
493 && sym_lookup (&syms[EXCL_TIME], child->addr))
494 {
495 child->cg.prop.fract = 0.0;
496 }
497 }
498 child->cg.prop.self = child->hist.time * child->cg.prop.fract;
499 print_time += child->cg.prop.self;
500 DBG (PROPDEBUG,
501 printf ("[prop_flags] ");
502 print_name (child);
503 printf (" ends up with printflag %d and prop-fract %f\n",
504 child->cg.print_flag, child->cg.prop.fract);
505 printf ("[prop_flags] time %f propself %f print_time %f\n",
506 child->hist.time, child->cg.prop.self, print_time));
507 }
508 }
509
510
511 /*
512 * Compare by decreasing propagated time. If times are equal, but one
513 * is a cycle header, say that's first (e.g. less, i.e. -1). If one's
514 * name doesn't have an underscore and the other does, say that one is
515 * first. All else being equal, compare by names.
516 */
517 static int
518 DEFUN (cmp_total, (lp, rp), const PTR lp AND const PTR rp)
519 {
520 const Sym *left = *(const Sym **) lp;
521 const Sym *right = *(const Sym **) rp;
522 double diff;
523
524 diff = (left->cg.prop.self + left->cg.prop.child)
525 - (right->cg.prop.self + right->cg.prop.child);
526 if (diff < 0.0)
527 {
528 return 1;
529 }
530 if (diff > 0.0)
531 {
532 return -1;
533 }
534 if (!left->name && left->cg.cyc.num != 0)
535 {
536 return -1;
537 }
538 if (!right->name && right->cg.cyc.num != 0)
539 {
540 return 1;
541 }
542 if (!left->name)
543 {
544 return -1;
545 }
546 if (!right->name)
547 {
548 return 1;
549 }
550 if (left->name[0] != '_' && right->name[0] == '_')
551 {
552 return -1;
553 }
554 if (left->name[0] == '_' && right->name[0] != '_')
555 {
556 return 1;
557 }
558 if (left->ncalls > right->ncalls)
559 {
560 return -1;
561 }
562 if (left->ncalls < right->ncalls)
563 {
564 return 1;
565 }
566 return strcmp (left->name, right->name);
567 }
568
569
570 /*
571 * Topologically sort the graph (collapsing cycles), and propagates
572 * time bottom up and flags top down.
573 */
574 Sym **
575 DEFUN_VOID (cg_assemble)
576 {
577 Sym *parent, **time_sorted_syms, **top_sorted_syms;
578 unsigned int index;
579 Arc *arc;
580
581 /*
582 * initialize various things:
583 * zero out child times.
584 * count self-recursive calls.
585 * indicate that nothing is on cycles.
586 */
587 for (parent = symtab.base; parent < symtab.limit; parent++)
588 {
589 parent->cg.child_time = 0.0;
590 arc = arc_lookup (parent, parent);
591 if (arc && parent == arc->child)
592 {
593 parent->ncalls -= arc->count;
594 parent->cg.self_calls = arc->count;
595 }
596 else
597 {
598 parent->cg.self_calls = 0;
599 }
600 parent->cg.prop.fract = 0.0;
601 parent->cg.prop.self = 0.0;
602 parent->cg.prop.child = 0.0;
603 parent->cg.print_flag = FALSE;
604 parent->cg.top_order = DFN_NAN;
605 parent->cg.cyc.num = 0;
606 parent->cg.cyc.head = parent;
607 parent->cg.cyc.next = 0;
608 if (ignore_direct_calls)
609 {
610 find_call (parent, parent->addr, (parent + 1)->addr);
611 }
612 }
613 /*
614 * Topologically order things. If any node is unnumbered, number
615 * it and any of its descendents.
616 */
617 for (parent = symtab.base; parent < symtab.limit; parent++)
618 {
619 if (parent->cg.top_order == DFN_NAN)
620 {
621 cg_dfn (parent);
622 }
623 }
624
625 /* link together nodes on the same cycle: */
626 cycle_link ();
627
628 /* sort the symbol table in reverse topological order: */
629 top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
630 for (index = 0; index < symtab.len; ++index)
631 {
632 top_sorted_syms[index] = &symtab.base[index];
633 }
634 qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
635 DBG (DFNDEBUG,
636 printf ("[cg_assemble] topological sort listing\n");
637 for (index = 0; index < symtab.len; ++index)
638 {
639 printf ("[cg_assemble] ");
640 printf ("%d:", top_sorted_syms[index]->cg.top_order);
641 print_name (top_sorted_syms[index]);
642 printf ("\n");
643 }
644 );
645 /*
646 * Starting from the topological top, propagate print flags to
647 * children. also, calculate propagation fractions. this happens
648 * before time propagation since time propagation uses the
649 * fractions.
650 */
651 propagate_flags (top_sorted_syms);
652
653 /*
654 * Starting from the topological bottom, propogate children times
655 * up to parents.
656 */
657 cycle_time ();
658 for (index = 0; index < symtab.len; ++index)
659 {
660 propagate_time (top_sorted_syms[index]);
661 }
662
663 free (top_sorted_syms);
664
665 /*
666 * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
667 * function names and cycle headers.
668 */
669 time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
670 for (index = 0; index < symtab.len; index++)
671 {
672 time_sorted_syms[index] = &symtab.base[index];
673 }
674 for (index = 1; index <= num_cycles; index++)
675 {
676 time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
677 }
678 qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
679 cmp_total);
680 for (index = 0; index < symtab.len + num_cycles; index++)
681 {
682 time_sorted_syms[index]->cg.index = index + 1;
683 }
684 return time_sorted_syms;
685 }