2 * Copyright (c) 1983 Regents of the University of California.
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.
19 #include "libiberty.h"
21 #include "call_graph.h"
32 * Return TRUE iff PARENT has an arc to covers the address
33 * range covered by CHILD.
36 DEFUN (arc_lookup, (parent, child), Sym * parent AND Sym * child)
40 if (!parent || !child)
42 printf ("[arc_lookup] parent == 0 || child == 0\n");
45 DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
46 parent->name, child->name));
47 for (arc = parent->cg.children; arc; arc = arc->next_child)
49 DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
50 arc->parent->name, arc->child->name));
51 if (child->addr >= arc->child->addr
52 && child->end_addr <= arc->child->end_addr)
62 * Add (or just increment) an arc:
65 DEFUN (arc_add, (parent, child, count),
66 Sym * parent AND Sym * child AND int count)
70 DBG (TALLYDEBUG, printf ("[arc_add] %d arcs from %s to %s\n",
71 count, parent->name, child->name));
72 arc = arc_lookup (parent, child);
76 * A hit: just increment the count.
78 DBG (TALLYDEBUG, printf ("[tally] hit %d += %d\n",
83 arc = (Arc *) xmalloc (sizeof (*arc));
88 /* prepend this child to the children of this parent: */
89 arc->next_child = parent->cg.children;
90 parent->cg.children = arc;
92 /* prepend this parent to the parents of this child: */
93 arc->next_parent = child->cg.parents;
94 child->cg.parents = arc;
99 DEFUN (cmp_topo, (lp, rp), const PTR lp AND const PTR rp)
101 const Sym *left = *(const Sym **) lp;
102 const Sym *right = *(const Sym **) rp;
104 return left->cg.top_order - right->cg.top_order;
109 DEFUN (propagate_time, (parent), Sym * parent)
113 double share, prop_share;
115 if (parent->cg.prop.fract == 0.0)
120 /* gather time from children of this parent: */
122 for (arc = parent->cg.children; arc; arc = arc->next_child)
125 if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
129 if (child->cg.cyc.head != child)
131 if (parent->cg.cyc.num == child->cg.cyc.num)
135 if (parent->cg.top_order <= child->cg.top_order)
137 fprintf (stderr, "[propagate] toporder botches\n");
139 child = child->cg.cyc.head;
143 if (parent->cg.top_order <= child->cg.top_order)
145 fprintf (stderr, "[propagate] toporder botches\n");
149 if (child->ncalls == 0)
154 /* distribute time for this arc: */
155 arc->time = child->hist.time * (((double) arc->count)
156 / ((double) child->ncalls));
157 arc->child_time = child->cg.child_time
158 * (((double) arc->count) / ((double) child->ncalls));
159 share = arc->time + arc->child_time;
160 parent->cg.child_time += share;
162 /* (1 - cg.prop.fract) gets lost along the way: */
163 prop_share = parent->cg.prop.fract * share;
165 /* fix things for printing: */
166 parent->cg.prop.child += prop_share;
167 arc->time *= parent->cg.prop.fract;
168 arc->child_time *= parent->cg.prop.fract;
170 /* add this share to the parent's cycle header, if any: */
171 if (parent->cg.cyc.head != parent)
173 parent->cg.cyc.head->cg.child_time += share;
174 parent->cg.cyc.head->cg.prop.child += prop_share;
177 printf ("[prop_time] child \t");
179 printf (" with %f %f %d/%d\n", child->hist.time,
180 child->cg.child_time, arc->count, child->ncalls);
181 printf ("[prop_time] parent\t");
183 printf ("\n[prop_time] share %f\n", share));
185 } /* propagate_time */
189 * Compute the time of a cycle as the sum of the times of all
193 DEFUN_VOID (cycle_time)
197 for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
199 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
201 if (member->cg.prop.fract == 0.0)
204 * All members have the same propfraction except those
205 * that were excluded with -E.
209 cyc->hist.time += member->hist.time;
211 cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
217 DEFUN_VOID (cycle_link)
219 Sym *sym, *cyc, *member;
223 /* count the number of cycles, and initialize the cycle lists: */
226 for (sym = symtab.base; sym < symtab.limit; ++sym)
228 /* this is how you find unattached cycles: */
229 if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
236 * cycle_header is indexed by cycle number: i.e. it is origin 1,
239 cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
242 * Now link cycles to true cycle-heads, number them, accumulate
243 * the data for the cycle.
247 for (sym = symtab.base; sym < symtab.limit; ++sym)
249 if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
256 cyc->cg.print_flag = TRUE; /* should this be printed? */
257 cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
258 cyc->cg.cyc.num = num; /* internal number of cycle on */
259 cyc->cg.cyc.head = cyc; /* pointer to head of cycle */
260 cyc->cg.cyc.next = sym; /* pointer to next member of cycle */
261 DBG (CYCLEDEBUG, printf ("[cycle_link] ");
263 printf (" is the head of cycle %d\n", num));
265 /* link members to cycle header: */
266 for (member = sym; member; member = member->cg.cyc.next)
268 member->cg.cyc.num = num;
269 member->cg.cyc.head = cyc;
273 * Count calls from outside the cycle and those among cycle
276 for (member = sym; member; member = member->cg.cyc.next)
278 for (arc = member->cg.parents; arc; arc = arc->next_parent)
280 if (arc->parent == member)
284 if (arc->parent->cg.cyc.num == num)
286 cyc->cg.self_calls += arc->count;
290 cyc->ncalls += arc->count;
299 * Check if any parent of this child (or outside parents of this
300 * cycle) have their print flags on and set the print flag of the
301 * child (cycle) appropriately. Similarly, deal with propagation
302 * fractions from parents.
305 DEFUN (inherit_flags, (child), Sym * child)
307 Sym *head, *parent, *member;
310 head = child->cg.cyc.head;
313 /* just a regular child, check its parents: */
314 child->cg.print_flag = FALSE;
315 child->cg.prop.fract = 0.0;
316 for (arc = child->cg.parents; arc; arc = arc->next_parent)
318 parent = arc->parent;
323 child->cg.print_flag |= parent->cg.print_flag;
325 * If the child was never actually called (e.g., this arc
326 * is static (and all others are, too)) no time propagates
331 child->cg.prop.fract += parent->cg.prop.fract
332 * (((double) arc->count) / ((double) child->ncalls));
339 * Its a member of a cycle, look at all parents from outside
342 head->cg.print_flag = FALSE;
343 head->cg.prop.fract = 0.0;
344 for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
346 for (arc = member->cg.parents; arc; arc = arc->next_parent)
348 if (arc->parent->cg.cyc.head == head)
352 parent = arc->parent;
353 head->cg.print_flag |= parent->cg.print_flag;
355 * If the cycle was never actually called (e.g. this
356 * arc is static (and all others are, too)) no time
357 * propagates along this arc.
361 head->cg.prop.fract += parent->cg.prop.fract
362 * (((double) arc->count) / ((double) head->ncalls));
366 for (member = head; member; member = member->cg.cyc.next)
368 member->cg.print_flag = head->cg.print_flag;
369 member->cg.prop.fract = head->cg.prop.fract;
372 } /* inherit_flags */
376 * In one top-to-bottom pass over the topologically sorted symbols
378 * cg.print_flag as the union of parents' print_flags
379 * propfraction as the sum of fractional parents' propfractions
380 * and while we're here, sum time for functions.
383 DEFUN (propagate_flags, (symbols), Sym ** symbols)
386 Sym *old_head, *child;
389 for (index = symtab.len - 1; index >= 0; --index)
391 child = symbols[index];
393 * If we haven't done this function or cycle, inherit things
394 * from parent. This way, we are linear in the number of arcs
395 * since we do all members of a cycle (and the cycle itself)
396 * as we hit the first member of the cycle.
398 if (child->cg.cyc.head != old_head)
400 old_head = child->cg.cyc.head;
401 inherit_flags (child);
404 printf ("[prop_flags] ");
406 printf ("inherits print-flag %d and prop-fract %f\n",
407 child->cg.print_flag, child->cg.prop.fract));
408 if (!child->cg.print_flag)
411 * Printflag is off. It gets turned on by being in the
412 * INCL_GRAPH table, or there being an empty INCL_GRAPH
413 * table and not being in the EXCL_GRAPH table.
415 if (sym_lookup (&syms[INCL_GRAPH], child->addr)
416 || (syms[INCL_GRAPH].len == 0
417 && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
419 child->cg.print_flag = TRUE;
425 * This function has printing parents: maybe someone wants
426 * to shut it up by putting it in the EXCL_GRAPH table.
427 * (But favor INCL_GRAPH over EXCL_GRAPH.)
429 if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
430 && sym_lookup (&syms[EXCL_GRAPH], child->addr))
432 child->cg.print_flag = FALSE;
435 if (child->cg.prop.fract == 0.0)
438 * No parents to pass time to. Collect time from children
439 * if its in the INCL_TIME table, or there is an empty
440 * INCL_TIME table and its not in the EXCL_TIME table.
442 if (sym_lookup (&syms[INCL_TIME], child->addr)
443 || (syms[INCL_TIME].len == 0
444 && !sym_lookup (&syms[EXCL_TIME], child->addr)))
446 child->cg.prop.fract = 1.0;
452 * It has parents to pass time to, but maybe someone wants
453 * to shut it up by puttting it in the EXCL_TIME table.
454 * (But favor being in INCL_TIME tabe over being in
457 if (!sym_lookup (&syms[INCL_TIME], child->addr)
458 && sym_lookup (&syms[EXCL_TIME], child->addr))
460 child->cg.prop.fract = 0.0;
463 child->cg.prop.self = child->hist.time * child->cg.prop.fract;
464 print_time += child->cg.prop.self;
466 printf ("[prop_flags] ");
468 printf (" ends up with printflag %d and prop-fract %f\n",
469 child->cg.print_flag, child->cg.prop.fract);
470 printf ("[prop_flags] time %f propself %f print_time %f\n",
471 child->hist.time, child->cg.prop.self, print_time));
473 } /* propagate_flags */
477 * Compare by decreasing propagated time. If times are equal, but one
478 * is a cycle header, say that's first (e.g. less, i.e. -1). If one's
479 * name doesn't have an underscore and the other does, say that one is
480 * first. All else being equal, compare by names.
483 DEFUN (cmp_total, (lp, rp), const PTR lp AND const PTR rp)
485 const Sym *left = *(const Sym **) lp;
486 const Sym *right = *(const Sym **) rp;
489 diff = (left->cg.prop.self + left->cg.prop.child)
490 - (right->cg.prop.self + right->cg.prop.child);
499 if (!left->name && left->cg.cyc.num != 0)
503 if (!right->name && right->cg.cyc.num != 0)
515 if (left->name[0] != '_' && right->name[0] == '_')
519 if (left->name[0] == '_' && right->name[0] != '_')
523 if (left->ncalls > right->ncalls)
527 if (left->ncalls < right->ncalls)
531 return strcmp (left->name, right->name);
536 * Topologically sort the graph (collapsing cycles), and propagates
537 * time bottom up and flags top down.
540 DEFUN_VOID (cg_assemble)
542 Sym *parent, **time_sorted_syms, **top_sorted_syms;
545 extern void find_call PARAMS ((Sym * parent,
546 bfd_vma p_lowpc, bfd_vma p_highpc));
548 * initialize various things:
549 * zero out child times.
550 * count self-recursive calls.
551 * indicate that nothing is on cycles.
553 for (parent = symtab.base; parent < symtab.limit; parent++)
555 parent->cg.child_time = 0.0;
556 arc = arc_lookup (parent, parent);
557 if (arc && parent == arc->child)
559 parent->ncalls -= arc->count;
560 parent->cg.self_calls = arc->count;
564 parent->cg.self_calls = 0;
566 parent->cg.prop.fract = 0.0;
567 parent->cg.prop.self = 0.0;
568 parent->cg.prop.child = 0.0;
569 parent->cg.print_flag = FALSE;
570 parent->cg.top_order = DFN_NAN;
571 parent->cg.cyc.num = 0;
572 parent->cg.cyc.head = parent;
573 parent->cg.cyc.next = 0;
574 if (ignore_direct_calls)
576 find_call (parent, parent->addr, (parent + 1)->addr);
580 * Topologically order things. If any node is unnumbered, number
581 * it and any of its descendents.
583 for (parent = symtab.base; parent < symtab.limit; parent++)
585 if (parent->cg.top_order == DFN_NAN)
591 /* link together nodes on the same cycle: */
594 /* sort the symbol table in reverse topological order: */
595 top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
596 for (index = 0; index < symtab.len; ++index)
598 top_sorted_syms[index] = &symtab.base[index];
600 qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
602 printf ("[cg_assemble] topological sort listing\n");
603 for (index = 0; index < symtab.len; ++index)
605 printf ("[cg_assemble] ");
606 printf ("%d:", top_sorted_syms[index]->cg.top_order);
607 print_name (top_sorted_syms[index]);
612 * Starting from the topological top, propagate print flags to
613 * children. also, calculate propagation fractions. this happens
614 * before time propagation since time propagation uses the
617 propagate_flags (top_sorted_syms);
620 * Starting from the topological bottom, propogate children times
624 for (index = 0; index < symtab.len; ++index)
626 propagate_time (top_sorted_syms[index]);
629 free (top_sorted_syms);
632 * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
633 * function names and cycle headers.
635 time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
636 for (index = 0; index < symtab.len; index++)
638 time_sorted_syms[index] = &symtab.base[index];
640 for (index = 1; index <= num_cycles; index++)
642 time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
644 qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
646 for (index = 0; index < symtab.len + num_cycles; index++)
648 time_sorted_syms[index]->cg.index = index + 1;
650 return time_sorted_syms;
653 /*** end of cg_arcs.c ***/