This commit was generated by cvs2svn to track changes on a CVS vendor
[platform/upstream/binutils.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 }