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
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
30 #include "libiberty.h"
31 #include "search_list.h"
34 #include "call_graph.h"
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
);
50 unsigned int num_cycles
;
55 * Return TRUE iff PARENT has an arc to covers the address
56 * range covered by CHILD.
59 arc_lookup (Sym
*parent
, Sym
*child
)
63 if (!parent
|| !child
)
65 printf ("[arc_lookup] parent == 0 || child == 0\n");
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
)
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
)
85 * Add (or just increment) an arc:
88 arc_add (Sym
*parent
, Sym
*child
, unsigned long count
)
90 static unsigned int maxarcs
= 0;
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
);
99 * A hit: just increment the count.
101 DBG (TALLYDEBUG
, printf ("[tally] hit %lu += %lu\n",
106 arc
= (Arc
*) xmalloc (sizeof (*arc
));
107 memset (arc
, 0, sizeof (*arc
));
108 arc
->parent
= parent
;
112 /* If this isn't an arc for a recursive call to parent, then add it
113 to the array of arcs. */
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
119 if (numarcs
== maxarcs
)
121 /* Determine how much space we want to allocate. */
126 /* Allocate the new array. */
127 newarcs
= (Arc
**)xmalloc(sizeof (Arc
*) * maxarcs
);
129 /* Copy the old array's contents into the new array. */
130 memcpy (newarcs
, arcs
, numarcs
* sizeof (Arc
*));
132 /* Free up the old array. */
135 /* And make the new array be the current array. */
139 /* Place this arc in the arc array. */
140 arcs
[numarcs
++] = arc
;
143 /* prepend this child to the children of this parent: */
144 arc
->next_child
= parent
->cg
.children
;
145 parent
->cg
.children
= arc
;
147 /* prepend this parent to the parents of this child: */
148 arc
->next_parent
= child
->cg
.parents
;
149 child
->cg
.parents
= arc
;
154 cmp_topo (const PTR lp
, const PTR rp
)
156 const Sym
*left
= *(const Sym
**) lp
;
157 const Sym
*right
= *(const Sym
**) rp
;
159 return left
->cg
.top_order
- right
->cg
.top_order
;
164 propagate_time (Sym
*parent
)
168 double share
, prop_share
;
170 if (parent
->cg
.prop
.fract
== 0.0)
175 /* gather time from children of this parent: */
177 for (arc
= parent
->cg
.children
; arc
; arc
= arc
->next_child
)
180 if (arc
->count
== 0 || child
== parent
|| child
->cg
.prop
.fract
== 0)
184 if (child
->cg
.cyc
.head
!= child
)
186 if (parent
->cg
.cyc
.num
== child
->cg
.cyc
.num
)
190 if (parent
->cg
.top_order
<= child
->cg
.top_order
)
192 fprintf (stderr
, "[propagate] toporder botches\n");
194 child
= child
->cg
.cyc
.head
;
198 if (parent
->cg
.top_order
<= child
->cg
.top_order
)
200 fprintf (stderr
, "[propagate] toporder botches\n");
204 if (child
->ncalls
== 0)
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
;
217 /* (1 - cg.prop.fract) gets lost along the way: */
218 prop_share
= parent
->cg
.prop
.fract
* share
;
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
;
225 /* add this share to the parent's cycle header, if any: */
226 if (parent
->cg
.cyc
.head
!= parent
)
228 parent
->cg
.cyc
.head
->cg
.child_time
+= share
;
229 parent
->cg
.cyc
.head
->cg
.prop
.child
+= prop_share
;
232 printf ("[prop_time] child \t");
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");
238 printf ("\n[prop_time] share %f\n", share
));
244 * Compute the time of a cycle as the sum of the times of all
252 for (cyc
= &cycle_header
[1]; cyc
<= &cycle_header
[num_cycles
]; ++cyc
)
254 for (member
= cyc
->cg
.cyc
.next
; member
; member
= member
->cg
.cyc
.next
)
256 if (member
->cg
.prop
.fract
== 0.0)
259 * All members have the same propfraction except those
260 * that were excluded with -E.
264 cyc
->hist
.time
+= member
->hist
.time
;
266 cyc
->cg
.prop
.self
= cyc
->cg
.prop
.fract
* cyc
->hist
.time
;
274 Sym
*sym
, *cyc
, *member
;
278 /* count the number of cycles, and initialize the cycle lists: */
281 for (sym
= symtab
.base
; sym
< symtab
.limit
; ++sym
)
283 /* this is how you find unattached cycles: */
284 if (sym
->cg
.cyc
.head
== sym
&& sym
->cg
.cyc
.next
)
291 * cycle_header is indexed by cycle number: i.e. it is origin 1,
294 cycle_header
= (Sym
*) xmalloc ((num_cycles
+ 1) * sizeof (Sym
));
297 * Now link cycles to true cycle-heads, number them, accumulate
298 * the data for the cycle.
302 for (sym
= symtab
.base
; sym
< symtab
.limit
; ++sym
)
304 if (!(sym
->cg
.cyc
.head
== sym
&& sym
->cg
.cyc
.next
!= 0))
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] ");
318 printf (" is the head of cycle %d\n", num
));
320 /* link members to cycle header: */
321 for (member
= sym
; member
; member
= member
->cg
.cyc
.next
)
323 member
->cg
.cyc
.num
= num
;
324 member
->cg
.cyc
.head
= cyc
;
328 * Count calls from outside the cycle and those among cycle
331 for (member
= sym
; member
; member
= member
->cg
.cyc
.next
)
333 for (arc
= member
->cg
.parents
; arc
; arc
= arc
->next_parent
)
335 if (arc
->parent
== member
)
339 if (arc
->parent
->cg
.cyc
.num
== num
)
341 cyc
->cg
.self_calls
+= arc
->count
;
345 cyc
->ncalls
+= arc
->count
;
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.
360 inherit_flags (Sym
*child
)
362 Sym
*head
, *parent
, *member
;
365 head
= child
->cg
.cyc
.head
;
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
)
373 parent
= arc
->parent
;
378 child
->cg
.print_flag
|= parent
->cg
.print_flag
;
380 * If the child was never actually called (e.g., this arc
381 * is static (and all others are, too)) no time propagates
384 if (child
->ncalls
!= 0)
386 child
->cg
.prop
.fract
+= parent
->cg
.prop
.fract
387 * (((double) arc
->count
) / ((double) child
->ncalls
));
394 * Its a member of a cycle, look at all parents from outside
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
)
401 for (arc
= member
->cg
.parents
; arc
; arc
= arc
->next_parent
)
403 if (arc
->parent
->cg
.cyc
.head
== head
)
407 parent
= arc
->parent
;
408 head
->cg
.print_flag
|= parent
->cg
.print_flag
;
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.
414 if (head
->ncalls
!= 0)
416 head
->cg
.prop
.fract
+= parent
->cg
.prop
.fract
417 * (((double) arc
->count
) / ((double) head
->ncalls
));
421 for (member
= head
; member
; member
= member
->cg
.cyc
.next
)
423 member
->cg
.print_flag
= head
->cg
.print_flag
;
424 member
->cg
.prop
.fract
= head
->cg
.prop
.fract
;
431 * In one top-to-bottom pass over the topologically sorted symbols
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.
438 propagate_flags (Sym
**symbols
)
441 Sym
*old_head
, *child
;
444 for (sym_index
= symtab
.len
- 1; sym_index
>= 0; --sym_index
)
446 child
= symbols
[sym_index
];
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.
453 if (child
->cg
.cyc
.head
!= old_head
)
455 old_head
= child
->cg
.cyc
.head
;
456 inherit_flags (child
);
459 printf ("[prop_flags] ");
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
)
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.
470 if (sym_lookup (&syms
[INCL_GRAPH
], child
->addr
)
471 || (syms
[INCL_GRAPH
].len
== 0
472 && !sym_lookup (&syms
[EXCL_GRAPH
], child
->addr
)))
474 child
->cg
.print_flag
= TRUE
;
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.)
484 if (!sym_lookup (&syms
[INCL_GRAPH
], child
->addr
)
485 && sym_lookup (&syms
[EXCL_GRAPH
], child
->addr
))
487 child
->cg
.print_flag
= FALSE
;
490 if (child
->cg
.prop
.fract
== 0.0)
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.
497 if (sym_lookup (&syms
[INCL_TIME
], child
->addr
)
498 || (syms
[INCL_TIME
].len
== 0
499 && !sym_lookup (&syms
[EXCL_TIME
], child
->addr
)))
501 child
->cg
.prop
.fract
= 1.0;
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
512 if (!sym_lookup (&syms
[INCL_TIME
], child
->addr
)
513 && sym_lookup (&syms
[EXCL_TIME
], child
->addr
))
515 child
->cg
.prop
.fract
= 0.0;
518 child
->cg
.prop
.self
= child
->hist
.time
* child
->cg
.prop
.fract
;
519 print_time
+= child
->cg
.prop
.self
;
521 printf ("[prop_flags] ");
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
));
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.
538 cmp_total (const PTR lp
, const PTR rp
)
540 const Sym
*left
= *(const Sym
**) lp
;
541 const Sym
*right
= *(const Sym
**) rp
;
544 diff
= (left
->cg
.prop
.self
+ left
->cg
.prop
.child
)
545 - (right
->cg
.prop
.self
+ right
->cg
.prop
.child
);
554 if (!left
->name
&& left
->cg
.cyc
.num
!= 0)
558 if (!right
->name
&& right
->cg
.cyc
.num
!= 0)
570 if (left
->name
[0] != '_' && right
->name
[0] == '_')
574 if (left
->name
[0] == '_' && right
->name
[0] != '_')
578 if (left
->ncalls
> right
->ncalls
)
582 if (left
->ncalls
< right
->ncalls
)
586 return strcmp (left
->name
, right
->name
);
590 /* Topologically sort the graph (collapsing cycles), and propagates
591 time bottom up and flags top down. */
596 Sym
*parent
, **time_sorted_syms
, **top_sorted_syms
;
597 unsigned int sym_index
;
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
++)
606 parent
->cg
.child_time
= 0.0;
607 arc
= arc_lookup (parent
, parent
);
608 if (arc
&& parent
== arc
->child
)
610 parent
->ncalls
-= arc
->count
;
611 parent
->cg
.self_calls
= arc
->count
;
615 parent
->cg
.self_calls
= 0;
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
);
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
++)
633 if (parent
->cg
.top_order
== DFN_NAN
)
637 /* Link together nodes on the same cycle. */
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
];
645 qsort (top_sorted_syms
, symtab
.len
, sizeof (Sym
*), cmp_topo
);
647 printf ("[cg_assemble] topological sort listing\n");
648 for (sym_index
= 0; sym_index
< symtab
.len
; ++sym_index
)
650 printf ("[cg_assemble] ");
651 printf ("%d:", top_sorted_syms
[sym_index
]->cg
.top_order
);
652 print_name (top_sorted_syms
[sym_index
]);
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
661 propagate_flags (top_sorted_syms
);
663 /* Starting from the topological bottom, propogate children times
666 for (sym_index
= 0; sym_index
< symtab
.len
; ++sym_index
)
667 propagate_time (top_sorted_syms
[sym_index
]);
669 free (top_sorted_syms
);
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
];
677 for (sym_index
= 1; sym_index
<= num_cycles
; sym_index
++)
678 time_sorted_syms
[symtab
.len
+ sym_index
- 1] = &cycle_header
[sym_index
];
680 qsort (time_sorted_syms
, symtab
.len
+ num_cycles
, sizeof (Sym
*),
683 for (sym_index
= 0; sym_index
< symtab
.len
+ num_cycles
; sym_index
++)
684 time_sorted_syms
[sym_index
]->cg
.index
= sym_index
+ 1;
686 return time_sorted_syms
;
This page took 0.043545 seconds and 4 git commands to generate.