* readelf.c (struct Frame_Chunk): Add cfa_exp.
[binutils.git] / gprof / cg_arcs.c
blobcea21cf50538a4a6fce252c6be7478fc3361b4d4
1 /*
2 * Copyright (c) 1983, 1993, 2001
3 * The Regents of the University of California. All rights reserved.
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.
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.
29 #include "libiberty.h"
30 #include "gprof.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"
41 static int cmp_topo PARAMS ((const PTR, const PTR));
42 static void propagate_time PARAMS ((Sym *));
43 static void cycle_time PARAMS ((void));
44 static void cycle_link PARAMS ((void));
45 static void inherit_flags PARAMS ((Sym *));
46 static void propagate_flags PARAMS ((Sym **));
47 static int cmp_total PARAMS ((const PTR, const PTR));
49 Sym *cycle_header;
50 unsigned int num_cycles;
51 Arc **arcs;
52 unsigned int numarcs;
55 * Return TRUE iff PARENT has an arc to covers the address
56 * range covered by CHILD.
58 Arc *
59 arc_lookup (parent, child)
60 Sym *parent;
61 Sym *child;
63 Arc *arc;
65 if (!parent || !child)
67 printf ("[arc_lookup] parent == 0 || child == 0\n");
68 return 0;
70 DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
71 parent->name, child->name));
72 for (arc = parent->cg.children; arc; arc = arc->next_child)
74 DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
75 arc->parent->name, arc->child->name));
76 if (child->addr >= arc->child->addr
77 && child->end_addr <= arc->child->end_addr)
79 return arc;
82 return 0;
87 * Add (or just increment) an arc:
89 void
90 arc_add (parent, child, count)
91 Sym *parent;
92 Sym *child;
93 unsigned long count;
95 static unsigned int maxarcs = 0;
96 Arc *arc, **newarcs;
98 DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
99 count, parent->name, child->name));
100 arc = arc_lookup (parent, child);
101 if (arc)
104 * A hit: just increment the count.
106 DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
107 arc->count, count));
108 arc->count += count;
109 return;
111 arc = (Arc *) xmalloc (sizeof (*arc));
112 memset (arc, 0, sizeof (*arc));
113 arc->parent = parent;
114 arc->child = child;
115 arc->count = count;
117 /* If this isn't an arc for a recursive call to parent, then add it
118 to the array of arcs. */
119 if (parent != child)
121 /* If we've exhausted space in our current array, get a new one
122 and copy the contents. We might want to throttle the doubling
123 factor one day. */
124 if (numarcs == maxarcs)
126 /* Determine how much space we want to allocate. */
127 if (maxarcs == 0)
128 maxarcs = 1;
129 maxarcs *= 2;
131 /* Allocate the new array. */
132 newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);
134 /* Copy the old array's contents into the new array. */
135 memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
137 /* Free up the old array. */
138 free (arcs);
140 /* And make the new array be the current array. */
141 arcs = newarcs;
144 /* Place this arc in the arc array. */
145 arcs[numarcs++] = arc;
148 /* prepend this child to the children of this parent: */
149 arc->next_child = parent->cg.children;
150 parent->cg.children = arc;
152 /* prepend this parent to the parents of this child: */
153 arc->next_parent = child->cg.parents;
154 child->cg.parents = arc;
158 static int
159 cmp_topo (lp, rp)
160 const PTR lp;
161 const PTR rp;
163 const Sym *left = *(const Sym **) lp;
164 const Sym *right = *(const Sym **) rp;
166 return left->cg.top_order - right->cg.top_order;
170 static void
171 propagate_time (parent)
172 Sym *parent;
174 Arc *arc;
175 Sym *child;
176 double share, prop_share;
178 if (parent->cg.prop.fract == 0.0)
180 return;
183 /* gather time from children of this parent: */
185 for (arc = parent->cg.children; arc; arc = arc->next_child)
187 child = arc->child;
188 if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
190 continue;
192 if (child->cg.cyc.head != child)
194 if (parent->cg.cyc.num == child->cg.cyc.num)
196 continue;
198 if (parent->cg.top_order <= child->cg.top_order)
200 fprintf (stderr, "[propagate] toporder botches\n");
202 child = child->cg.cyc.head;
204 else
206 if (parent->cg.top_order <= child->cg.top_order)
208 fprintf (stderr, "[propagate] toporder botches\n");
209 continue;
212 if (child->ncalls == 0)
214 continue;
217 /* distribute time for this arc: */
218 arc->time = child->hist.time * (((double) arc->count)
219 / ((double) child->ncalls));
220 arc->child_time = child->cg.child_time
221 * (((double) arc->count) / ((double) child->ncalls));
222 share = arc->time + arc->child_time;
223 parent->cg.child_time += share;
225 /* (1 - cg.prop.fract) gets lost along the way: */
226 prop_share = parent->cg.prop.fract * share;
228 /* fix things for printing: */
229 parent->cg.prop.child += prop_share;
230 arc->time *= parent->cg.prop.fract;
231 arc->child_time *= parent->cg.prop.fract;
233 /* add this share to the parent's cycle header, if any: */
234 if (parent->cg.cyc.head != parent)
236 parent->cg.cyc.head->cg.child_time += share;
237 parent->cg.cyc.head->cg.prop.child += prop_share;
239 DBG (PROPDEBUG,
240 printf ("[prop_time] child \t");
241 print_name (child);
242 printf (" with %f %f %lu/%lu\n", child->hist.time,
243 child->cg.child_time, arc->count, child->ncalls);
244 printf ("[prop_time] parent\t");
245 print_name (parent);
246 printf ("\n[prop_time] share %f\n", share));
252 * Compute the time of a cycle as the sum of the times of all
253 * its members.
255 static void
256 cycle_time ()
258 Sym *member, *cyc;
260 for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
262 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
264 if (member->cg.prop.fract == 0.0)
267 * All members have the same propfraction except those
268 * that were excluded with -E.
270 continue;
272 cyc->hist.time += member->hist.time;
274 cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
279 static void
280 cycle_link ()
282 Sym *sym, *cyc, *member;
283 Arc *arc;
284 int num;
286 /* count the number of cycles, and initialize the cycle lists: */
288 num_cycles = 0;
289 for (sym = symtab.base; sym < symtab.limit; ++sym)
291 /* this is how you find unattached cycles: */
292 if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
294 ++num_cycles;
299 * cycle_header is indexed by cycle number: i.e. it is origin 1,
300 * not origin 0.
302 cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
305 * Now link cycles to true cycle-heads, number them, accumulate
306 * the data for the cycle.
308 num = 0;
309 cyc = cycle_header;
310 for (sym = symtab.base; sym < symtab.limit; ++sym)
312 if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
314 continue;
316 ++num;
317 ++cyc;
318 sym_init (cyc);
319 cyc->cg.print_flag = TRUE; /* should this be printed? */
320 cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
321 cyc->cg.cyc.num = num; /* internal number of cycle on */
322 cyc->cg.cyc.head = cyc; /* pointer to head of cycle */
323 cyc->cg.cyc.next = sym; /* pointer to next member of cycle */
324 DBG (CYCLEDEBUG, printf ("[cycle_link] ");
325 print_name (sym);
326 printf (" is the head of cycle %d\n", num));
328 /* link members to cycle header: */
329 for (member = sym; member; member = member->cg.cyc.next)
331 member->cg.cyc.num = num;
332 member->cg.cyc.head = cyc;
336 * Count calls from outside the cycle and those among cycle
337 * members:
339 for (member = sym; member; member = member->cg.cyc.next)
341 for (arc = member->cg.parents; arc; arc = arc->next_parent)
343 if (arc->parent == member)
345 continue;
347 if (arc->parent->cg.cyc.num == num)
349 cyc->cg.self_calls += arc->count;
351 else
353 cyc->ncalls += arc->count;
362 * Check if any parent of this child (or outside parents of this
363 * cycle) have their print flags on and set the print flag of the
364 * child (cycle) appropriately. Similarly, deal with propagation
365 * fractions from parents.
367 static void
368 inherit_flags (child)
369 Sym *child;
371 Sym *head, *parent, *member;
372 Arc *arc;
374 head = child->cg.cyc.head;
375 if (child == head)
377 /* just a regular child, check its parents: */
378 child->cg.print_flag = FALSE;
379 child->cg.prop.fract = 0.0;
380 for (arc = child->cg.parents; arc; arc = arc->next_parent)
382 parent = arc->parent;
383 if (child == parent)
385 continue;
387 child->cg.print_flag |= parent->cg.print_flag;
389 * If the child was never actually called (e.g., this arc
390 * is static (and all others are, too)) no time propagates
391 * along this arc.
393 if (child->ncalls != 0)
395 child->cg.prop.fract += parent->cg.prop.fract
396 * (((double) arc->count) / ((double) child->ncalls));
400 else
403 * Its a member of a cycle, look at all parents from outside
404 * the cycle.
406 head->cg.print_flag = FALSE;
407 head->cg.prop.fract = 0.0;
408 for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
410 for (arc = member->cg.parents; arc; arc = arc->next_parent)
412 if (arc->parent->cg.cyc.head == head)
414 continue;
416 parent = arc->parent;
417 head->cg.print_flag |= parent->cg.print_flag;
419 * If the cycle was never actually called (e.g. this
420 * arc is static (and all others are, too)) no time
421 * propagates along this arc.
423 if (head->ncalls != 0)
425 head->cg.prop.fract += parent->cg.prop.fract
426 * (((double) arc->count) / ((double) head->ncalls));
430 for (member = head; member; member = member->cg.cyc.next)
432 member->cg.print_flag = head->cg.print_flag;
433 member->cg.prop.fract = head->cg.prop.fract;
440 * In one top-to-bottom pass over the topologically sorted symbols
441 * propagate:
442 * cg.print_flag as the union of parents' print_flags
443 * propfraction as the sum of fractional parents' propfractions
444 * and while we're here, sum time for functions.
446 static void
447 propagate_flags (symbols)
448 Sym **symbols;
450 int index;
451 Sym *old_head, *child;
453 old_head = 0;
454 for (index = symtab.len - 1; index >= 0; --index)
456 child = symbols[index];
458 * If we haven't done this function or cycle, inherit things
459 * from parent. This way, we are linear in the number of arcs
460 * since we do all members of a cycle (and the cycle itself)
461 * as we hit the first member of the cycle.
463 if (child->cg.cyc.head != old_head)
465 old_head = child->cg.cyc.head;
466 inherit_flags (child);
468 DBG (PROPDEBUG,
469 printf ("[prop_flags] ");
470 print_name (child);
471 printf ("inherits print-flag %d and prop-fract %f\n",
472 child->cg.print_flag, child->cg.prop.fract));
473 if (!child->cg.print_flag)
476 * Printflag is off. It gets turned on by being in the
477 * INCL_GRAPH table, or there being an empty INCL_GRAPH
478 * table and not being in the EXCL_GRAPH table.
480 if (sym_lookup (&syms[INCL_GRAPH], child->addr)
481 || (syms[INCL_GRAPH].len == 0
482 && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
484 child->cg.print_flag = TRUE;
487 else
490 * This function has printing parents: maybe someone wants
491 * to shut it up by putting it in the EXCL_GRAPH table.
492 * (But favor INCL_GRAPH over EXCL_GRAPH.)
494 if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
495 && sym_lookup (&syms[EXCL_GRAPH], child->addr))
497 child->cg.print_flag = FALSE;
500 if (child->cg.prop.fract == 0.0)
503 * No parents to pass time to. Collect time from children
504 * if its in the INCL_TIME table, or there is an empty
505 * INCL_TIME table and its not in the EXCL_TIME table.
507 if (sym_lookup (&syms[INCL_TIME], child->addr)
508 || (syms[INCL_TIME].len == 0
509 && !sym_lookup (&syms[EXCL_TIME], child->addr)))
511 child->cg.prop.fract = 1.0;
514 else
517 * It has parents to pass time to, but maybe someone wants
518 * to shut it up by puttting it in the EXCL_TIME table.
519 * (But favor being in INCL_TIME tabe over being in
520 * EXCL_TIME table.)
522 if (!sym_lookup (&syms[INCL_TIME], child->addr)
523 && sym_lookup (&syms[EXCL_TIME], child->addr))
525 child->cg.prop.fract = 0.0;
528 child->cg.prop.self = child->hist.time * child->cg.prop.fract;
529 print_time += child->cg.prop.self;
530 DBG (PROPDEBUG,
531 printf ("[prop_flags] ");
532 print_name (child);
533 printf (" ends up with printflag %d and prop-fract %f\n",
534 child->cg.print_flag, child->cg.prop.fract);
535 printf ("[prop_flags] time %f propself %f print_time %f\n",
536 child->hist.time, child->cg.prop.self, print_time));
542 * Compare by decreasing propagated time. If times are equal, but one
543 * is a cycle header, say that's first (e.g. less, i.e. -1). If one's
544 * name doesn't have an underscore and the other does, say that one is
545 * first. All else being equal, compare by names.
547 static int
548 cmp_total (lp, rp)
549 const PTR lp;
550 const PTR rp;
552 const Sym *left = *(const Sym **) lp;
553 const Sym *right = *(const Sym **) rp;
554 double diff;
556 diff = (left->cg.prop.self + left->cg.prop.child)
557 - (right->cg.prop.self + right->cg.prop.child);
558 if (diff < 0.0)
560 return 1;
562 if (diff > 0.0)
564 return -1;
566 if (!left->name && left->cg.cyc.num != 0)
568 return -1;
570 if (!right->name && right->cg.cyc.num != 0)
572 return 1;
574 if (!left->name)
576 return -1;
578 if (!right->name)
580 return 1;
582 if (left->name[0] != '_' && right->name[0] == '_')
584 return -1;
586 if (left->name[0] == '_' && right->name[0] != '_')
588 return 1;
590 if (left->ncalls > right->ncalls)
592 return -1;
594 if (left->ncalls < right->ncalls)
596 return 1;
598 return strcmp (left->name, right->name);
603 * Topologically sort the graph (collapsing cycles), and propagates
604 * time bottom up and flags top down.
606 Sym **
607 cg_assemble ()
609 Sym *parent, **time_sorted_syms, **top_sorted_syms;
610 unsigned int index;
611 Arc *arc;
614 * initialize various things:
615 * zero out child times.
616 * count self-recursive calls.
617 * indicate that nothing is on cycles.
619 for (parent = symtab.base; parent < symtab.limit; parent++)
621 parent->cg.child_time = 0.0;
622 arc = arc_lookup (parent, parent);
623 if (arc && parent == arc->child)
625 parent->ncalls -= arc->count;
626 parent->cg.self_calls = arc->count;
628 else
630 parent->cg.self_calls = 0;
632 parent->cg.prop.fract = 0.0;
633 parent->cg.prop.self = 0.0;
634 parent->cg.prop.child = 0.0;
635 parent->cg.print_flag = FALSE;
636 parent->cg.top_order = DFN_NAN;
637 parent->cg.cyc.num = 0;
638 parent->cg.cyc.head = parent;
639 parent->cg.cyc.next = 0;
640 if (ignore_direct_calls)
642 find_call (parent, parent->addr, (parent + 1)->addr);
646 * Topologically order things. If any node is unnumbered, number
647 * it and any of its descendents.
649 for (parent = symtab.base; parent < symtab.limit; parent++)
651 if (parent->cg.top_order == DFN_NAN)
653 cg_dfn (parent);
657 /* link together nodes on the same cycle: */
658 cycle_link ();
660 /* sort the symbol table in reverse topological order: */
661 top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
662 for (index = 0; index < symtab.len; ++index)
664 top_sorted_syms[index] = &symtab.base[index];
666 qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
667 DBG (DFNDEBUG,
668 printf ("[cg_assemble] topological sort listing\n");
669 for (index = 0; index < symtab.len; ++index)
671 printf ("[cg_assemble] ");
672 printf ("%d:", top_sorted_syms[index]->cg.top_order);
673 print_name (top_sorted_syms[index]);
674 printf ("\n");
678 * Starting from the topological top, propagate print flags to
679 * children. also, calculate propagation fractions. this happens
680 * before time propagation since time propagation uses the
681 * fractions.
683 propagate_flags (top_sorted_syms);
686 * Starting from the topological bottom, propogate children times
687 * up to parents.
689 cycle_time ();
690 for (index = 0; index < symtab.len; ++index)
692 propagate_time (top_sorted_syms[index]);
695 free (top_sorted_syms);
698 * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
699 * function names and cycle headers.
701 time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
702 for (index = 0; index < symtab.len; index++)
704 time_sorted_syms[index] = &symtab.base[index];
706 for (index = 1; index <= num_cycles; index++)
708 time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
710 qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
711 cmp_total);
712 for (index = 0; index < symtab.len + num_cycles; index++)
714 time_sorted_syms[index]->cg.index = index + 1;
716 return time_sorted_syms;