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"
29 unsigned int num_cycles
;
34 * Return TRUE iff PARENT has an arc to covers the address
35 * range covered by CHILD.
38 DEFUN (arc_lookup
, (parent
, child
), Sym
* parent AND Sym
* child
)
42 if (!parent
|| !child
)
44 printf ("[arc_lookup] parent == 0 || child == 0\n");
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
)
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
)
64 * Add (or just increment) an arc:
67 DEFUN (arc_add
, (parent
, child
, count
),
68 Sym
* parent AND Sym
* child AND
unsigned long count
)
70 static unsigned int maxarcs
= 0;
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
);
79 * A hit: just increment the count.
81 DBG (TALLYDEBUG
, printf ("[tally] hit %lu += %lu\n",
86 arc
= (Arc
*) xmalloc (sizeof (*arc
));
87 memset (arc
, 0, sizeof (*arc
));
92 /* If this isn't an arc for a recursive call to parent, then add it
93 to the array of arcs. */
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
99 if (numarcs
== maxarcs
)
101 /* Determine how much space we want to allocate. */
106 /* Allocate the new array. */
107 newarcs
= (Arc
**)xmalloc(sizeof (Arc
*) * maxarcs
);
109 /* Copy the old array's contents into the new array. */
110 memcpy (newarcs
, arcs
, numarcs
* sizeof (Arc
*));
112 /* Free up the old array. */
115 /* And make the new array be the current array. */
119 /* Place this arc in the arc array. */
120 arcs
[numarcs
++] = arc
;
123 /* prepend this child to the children of this parent: */
124 arc
->next_child
= parent
->cg
.children
;
125 parent
->cg
.children
= arc
;
127 /* prepend this parent to the parents of this child: */
128 arc
->next_parent
= child
->cg
.parents
;
129 child
->cg
.parents
= arc
;
134 DEFUN (cmp_topo
, (lp
, rp
), const PTR lp AND
const PTR rp
)
136 const Sym
*left
= *(const Sym
**) lp
;
137 const Sym
*right
= *(const Sym
**) rp
;
139 return left
->cg
.top_order
- right
->cg
.top_order
;
144 DEFUN (propagate_time
, (parent
), Sym
* parent
)
148 double share
, prop_share
;
150 if (parent
->cg
.prop
.fract
== 0.0)
155 /* gather time from children of this parent: */
157 for (arc
= parent
->cg
.children
; arc
; arc
= arc
->next_child
)
160 if (arc
->count
== 0 || child
== parent
|| child
->cg
.prop
.fract
== 0)
164 if (child
->cg
.cyc
.head
!= child
)
166 if (parent
->cg
.cyc
.num
== child
->cg
.cyc
.num
)
170 if (parent
->cg
.top_order
<= child
->cg
.top_order
)
172 fprintf (stderr
, "[propagate] toporder botches\n");
174 child
= child
->cg
.cyc
.head
;
178 if (parent
->cg
.top_order
<= child
->cg
.top_order
)
180 fprintf (stderr
, "[propagate] toporder botches\n");
184 if (child
->ncalls
== 0)
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
;
197 /* (1 - cg.prop.fract) gets lost along the way: */
198 prop_share
= parent
->cg
.prop
.fract
* share
;
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
;
205 /* add this share to the parent's cycle header, if any: */
206 if (parent
->cg
.cyc
.head
!= parent
)
208 parent
->cg
.cyc
.head
->cg
.child_time
+= share
;
209 parent
->cg
.cyc
.head
->cg
.prop
.child
+= prop_share
;
212 printf ("[prop_time] child \t");
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");
218 printf ("\n[prop_time] share %f\n", share
));
224 * Compute the time of a cycle as the sum of the times of all
228 DEFUN_VOID (cycle_time
)
232 for (cyc
= &cycle_header
[1]; cyc
<= &cycle_header
[num_cycles
]; ++cyc
)
234 for (member
= cyc
->cg
.cyc
.next
; member
; member
= member
->cg
.cyc
.next
)
236 if (member
->cg
.prop
.fract
== 0.0)
239 * All members have the same propfraction except those
240 * that were excluded with -E.
244 cyc
->hist
.time
+= member
->hist
.time
;
246 cyc
->cg
.prop
.self
= cyc
->cg
.prop
.fract
* cyc
->hist
.time
;
252 DEFUN_VOID (cycle_link
)
254 Sym
*sym
, *cyc
, *member
;
258 /* count the number of cycles, and initialize the cycle lists: */
261 for (sym
= symtab
.base
; sym
< symtab
.limit
; ++sym
)
263 /* this is how you find unattached cycles: */
264 if (sym
->cg
.cyc
.head
== sym
&& sym
->cg
.cyc
.next
)
271 * cycle_header is indexed by cycle number: i.e. it is origin 1,
274 cycle_header
= (Sym
*) xmalloc ((num_cycles
+ 1) * sizeof (Sym
));
277 * Now link cycles to true cycle-heads, number them, accumulate
278 * the data for the cycle.
282 for (sym
= symtab
.base
; sym
< symtab
.limit
; ++sym
)
284 if (!(sym
->cg
.cyc
.head
== sym
&& sym
->cg
.cyc
.next
!= 0))
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] ");
298 printf (" is the head of cycle %d\n", num
));
300 /* link members to cycle header: */
301 for (member
= sym
; member
; member
= member
->cg
.cyc
.next
)
303 member
->cg
.cyc
.num
= num
;
304 member
->cg
.cyc
.head
= cyc
;
308 * Count calls from outside the cycle and those among cycle
311 for (member
= sym
; member
; member
= member
->cg
.cyc
.next
)
313 for (arc
= member
->cg
.parents
; arc
; arc
= arc
->next_parent
)
315 if (arc
->parent
== member
)
319 if (arc
->parent
->cg
.cyc
.num
== num
)
321 cyc
->cg
.self_calls
+= arc
->count
;
325 cyc
->ncalls
+= arc
->count
;
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.
340 DEFUN (inherit_flags
, (child
), Sym
* child
)
342 Sym
*head
, *parent
, *member
;
345 head
= child
->cg
.cyc
.head
;
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
)
353 parent
= arc
->parent
;
358 child
->cg
.print_flag
|= parent
->cg
.print_flag
;
360 * If the child was never actually called (e.g., this arc
361 * is static (and all others are, too)) no time propagates
364 if (child
->ncalls
!= 0)
366 child
->cg
.prop
.fract
+= parent
->cg
.prop
.fract
367 * (((double) arc
->count
) / ((double) child
->ncalls
));
374 * Its a member of a cycle, look at all parents from outside
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
)
381 for (arc
= member
->cg
.parents
; arc
; arc
= arc
->next_parent
)
383 if (arc
->parent
->cg
.cyc
.head
== head
)
387 parent
= arc
->parent
;
388 head
->cg
.print_flag
|= parent
->cg
.print_flag
;
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.
394 if (head
->ncalls
!= 0)
396 head
->cg
.prop
.fract
+= parent
->cg
.prop
.fract
397 * (((double) arc
->count
) / ((double) head
->ncalls
));
401 for (member
= head
; member
; member
= member
->cg
.cyc
.next
)
403 member
->cg
.print_flag
= head
->cg
.print_flag
;
404 member
->cg
.prop
.fract
= head
->cg
.prop
.fract
;
411 * In one top-to-bottom pass over the topologically sorted symbols
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.
418 DEFUN (propagate_flags
, (symbols
), Sym
** symbols
)
421 Sym
*old_head
, *child
;
424 for (index
= symtab
.len
- 1; index
>= 0; --index
)
426 child
= symbols
[index
];
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.
433 if (child
->cg
.cyc
.head
!= old_head
)
435 old_head
= child
->cg
.cyc
.head
;
436 inherit_flags (child
);
439 printf ("[prop_flags] ");
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
)
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.
450 if (sym_lookup (&syms
[INCL_GRAPH
], child
->addr
)
451 || (syms
[INCL_GRAPH
].len
== 0
452 && !sym_lookup (&syms
[EXCL_GRAPH
], child
->addr
)))
454 child
->cg
.print_flag
= TRUE
;
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.)
464 if (!sym_lookup (&syms
[INCL_GRAPH
], child
->addr
)
465 && sym_lookup (&syms
[EXCL_GRAPH
], child
->addr
))
467 child
->cg
.print_flag
= FALSE
;
470 if (child
->cg
.prop
.fract
== 0.0)
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.
477 if (sym_lookup (&syms
[INCL_TIME
], child
->addr
)
478 || (syms
[INCL_TIME
].len
== 0
479 && !sym_lookup (&syms
[EXCL_TIME
], child
->addr
)))
481 child
->cg
.prop
.fract
= 1.0;
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
492 if (!sym_lookup (&syms
[INCL_TIME
], child
->addr
)
493 && sym_lookup (&syms
[EXCL_TIME
], child
->addr
))
495 child
->cg
.prop
.fract
= 0.0;
498 child
->cg
.prop
.self
= child
->hist
.time
* child
->cg
.prop
.fract
;
499 print_time
+= child
->cg
.prop
.self
;
501 printf ("[prop_flags] ");
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
));
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.
518 DEFUN (cmp_total
, (lp
, rp
), const PTR lp AND
const PTR rp
)
520 const Sym
*left
= *(const Sym
**) lp
;
521 const Sym
*right
= *(const Sym
**) rp
;
524 diff
= (left
->cg
.prop
.self
+ left
->cg
.prop
.child
)
525 - (right
->cg
.prop
.self
+ right
->cg
.prop
.child
);
534 if (!left
->name
&& left
->cg
.cyc
.num
!= 0)
538 if (!right
->name
&& right
->cg
.cyc
.num
!= 0)
550 if (left
->name
[0] != '_' && right
->name
[0] == '_')
554 if (left
->name
[0] == '_' && right
->name
[0] != '_')
558 if (left
->ncalls
> right
->ncalls
)
562 if (left
->ncalls
< right
->ncalls
)
566 return strcmp (left
->name
, right
->name
);
571 * Topologically sort the graph (collapsing cycles), and propagates
572 * time bottom up and flags top down.
575 DEFUN_VOID (cg_assemble
)
577 Sym
*parent
, **time_sorted_syms
, **top_sorted_syms
;
582 * initialize various things:
583 * zero out child times.
584 * count self-recursive calls.
585 * indicate that nothing is on cycles.
587 for (parent
= symtab
.base
; parent
< symtab
.limit
; parent
++)
589 parent
->cg
.child_time
= 0.0;
590 arc
= arc_lookup (parent
, parent
);
591 if (arc
&& parent
== arc
->child
)
593 parent
->ncalls
-= arc
->count
;
594 parent
->cg
.self_calls
= arc
->count
;
598 parent
->cg
.self_calls
= 0;
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
)
610 find_call (parent
, parent
->addr
, (parent
+ 1)->addr
);
614 * Topologically order things. If any node is unnumbered, number
615 * it and any of its descendents.
617 for (parent
= symtab
.base
; parent
< symtab
.limit
; parent
++)
619 if (parent
->cg
.top_order
== DFN_NAN
)
625 /* link together nodes on the same cycle: */
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
)
632 top_sorted_syms
[index
] = &symtab
.base
[index
];
634 qsort (top_sorted_syms
, symtab
.len
, sizeof (Sym
*), cmp_topo
);
636 printf ("[cg_assemble] topological sort listing\n");
637 for (index
= 0; index
< symtab
.len
; ++index
)
639 printf ("[cg_assemble] ");
640 printf ("%d:", top_sorted_syms
[index
]->cg
.top_order
);
641 print_name (top_sorted_syms
[index
]);
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
651 propagate_flags (top_sorted_syms
);
654 * Starting from the topological bottom, propogate children times
658 for (index
= 0; index
< symtab
.len
; ++index
)
660 propagate_time (top_sorted_syms
[index
]);
663 free (top_sorted_syms
);
666 * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
667 * function names and cycle headers.
669 time_sorted_syms
= (Sym
**) xmalloc ((symtab
.len
+ num_cycles
) * sizeof (Sym
*));
670 for (index
= 0; index
< symtab
.len
; index
++)
672 time_sorted_syms
[index
] = &symtab
.base
[index
];
674 for (index
= 1; index
<= num_cycles
; index
++)
676 time_sorted_syms
[symtab
.len
+ index
- 1] = &cycle_header
[index
];
678 qsort (time_sorted_syms
, symtab
.len
+ num_cycles
, sizeof (Sym
*),
680 for (index
= 0; index
< symtab
.len
+ num_cycles
; index
++)
682 time_sorted_syms
[index
]->cg
.index
= index
+ 1;
684 return time_sorted_syms
;
This page took 0.043418 seconds and 4 git commands to generate.