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 PTR, const PTR);
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 PTR, const PTR);
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 *
arc_lookup(Sym * parent,Sym * child)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
arc_add(Sym * parent,Sym * child,unsigned long count)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
cmp_topo(const PTR lp,const PTR rp)154 cmp_topo (const PTR lp, const PTR 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
propagate_time(Sym * parent)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
cycle_time(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
cycle_link(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
inherit_flags(Sym * child)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
propagate_flags(Sym ** symbols)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
cmp_total(const PTR lp,const PTR rp)538 cmp_total (const PTR lp, const PTR 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 **
cg_assemble(void)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 }
688