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