Commit | Line | Data |
---|---|---|
5489fcc3 KR |
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 | int num_cycles; | |
30 | ||
31 | /* | |
32 | * Return TRUE iff PARENT has an arc to covers the address | |
33 | * range covered by CHILD. | |
34 | */ | |
12516a37 KR |
35 | Arc * |
36 | DEFUN (arc_lookup, (parent, child), Sym * parent AND Sym * child) | |
5489fcc3 | 37 | { |
12516a37 KR |
38 | Arc *arc; |
39 | ||
40 | if (!parent || !child) | |
41 | { | |
42 | printf ("[arc_lookup] parent == 0 || child == 0\n"); | |
43 | return 0; | |
03c35bcb | 44 | } |
12516a37 | 45 | DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n", |
5489fcc3 | 46 | parent->name, child->name)); |
12516a37 KR |
47 | for (arc = parent->cg.children; arc; arc = arc->next_child) |
48 | { | |
49 | DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n", | |
5489fcc3 | 50 | arc->parent->name, arc->child->name)); |
12516a37 KR |
51 | if (child->addr >= arc->child->addr |
52 | && child->end_addr <= arc->child->end_addr) | |
5489fcc3 | 53 | { |
12516a37 | 54 | return arc; |
03c35bcb KR |
55 | } |
56 | } | |
12516a37 | 57 | return 0; |
03c35bcb | 58 | } |
5489fcc3 KR |
59 | |
60 | ||
61 | /* | |
62 | * Add (or just increment) an arc: | |
63 | */ | |
64 | void | |
12516a37 KR |
65 | DEFUN (arc_add, (parent, child, count), |
66 | Sym * parent AND Sym * child AND int count) | |
5489fcc3 | 67 | { |
12516a37 | 68 | Arc *arc; |
5489fcc3 | 69 | |
12516a37 | 70 | DBG (TALLYDEBUG, printf ("[arc_add] %d arcs from %s to %s\n", |
5489fcc3 | 71 | count, parent->name, child->name)); |
12516a37 KR |
72 | arc = arc_lookup (parent, child); |
73 | if (arc) | |
74 | { | |
75 | /* | |
76 | * A hit: just increment the count. | |
77 | */ | |
78 | DBG (TALLYDEBUG, printf ("[tally] hit %d += %d\n", | |
5489fcc3 | 79 | arc->count, count)); |
12516a37 KR |
80 | arc->count += count; |
81 | return; | |
03c35bcb | 82 | } |
12516a37 KR |
83 | arc = (Arc *) xmalloc (sizeof (*arc)); |
84 | arc->parent = parent; | |
85 | arc->child = child; | |
86 | arc->count = count; | |
5489fcc3 | 87 | |
12516a37 KR |
88 | /* prepend this child to the children of this parent: */ |
89 | arc->next_child = parent->cg.children; | |
90 | parent->cg.children = arc; | |
5489fcc3 | 91 | |
12516a37 KR |
92 | /* prepend this parent to the parents of this child: */ |
93 | arc->next_parent = child->cg.parents; | |
94 | child->cg.parents = arc; | |
03c35bcb | 95 | } |
5489fcc3 KR |
96 | |
97 | ||
98 | static int | |
12516a37 | 99 | DEFUN (cmp_topo, (lp, rp), const PTR lp AND const PTR rp) |
5489fcc3 | 100 | { |
12516a37 KR |
101 | const Sym *left = *(const Sym **) lp; |
102 | const Sym *right = *(const Sym **) rp; | |
5489fcc3 | 103 | |
12516a37 | 104 | return left->cg.top_order - right->cg.top_order; |
03c35bcb | 105 | } |
5489fcc3 KR |
106 | |
107 | ||
108 | static void | |
12516a37 | 109 | DEFUN (propagate_time, (parent), Sym * parent) |
5489fcc3 | 110 | { |
12516a37 KR |
111 | Arc *arc; |
112 | Sym *child; | |
113 | double share, prop_share; | |
114 | ||
115 | if (parent->cg.prop.fract == 0.0) | |
116 | { | |
117 | return; | |
03c35bcb | 118 | } |
12516a37 KR |
119 | |
120 | /* gather time from children of this parent: */ | |
121 | ||
122 | for (arc = parent->cg.children; arc; arc = arc->next_child) | |
123 | { | |
124 | child = arc->child; | |
125 | if (arc->count == 0 || child == parent || child->cg.prop.fract == 0) | |
126 | { | |
127 | continue; | |
03c35bcb | 128 | } |
12516a37 KR |
129 | if (child->cg.cyc.head != child) |
130 | { | |
131 | if (parent->cg.cyc.num == child->cg.cyc.num) | |
132 | { | |
133 | continue; | |
03c35bcb | 134 | } |
12516a37 KR |
135 | if (parent->cg.top_order <= child->cg.top_order) |
136 | { | |
137 | fprintf (stderr, "[propagate] toporder botches\n"); | |
03c35bcb | 138 | } |
12516a37 KR |
139 | child = child->cg.cyc.head; |
140 | } | |
141 | else | |
142 | { | |
143 | if (parent->cg.top_order <= child->cg.top_order) | |
144 | { | |
145 | fprintf (stderr, "[propagate] toporder botches\n"); | |
146 | continue; | |
03c35bcb KR |
147 | } |
148 | } | |
12516a37 KR |
149 | if (child->ncalls == 0) |
150 | { | |
151 | continue; | |
03c35bcb | 152 | } |
12516a37 KR |
153 | |
154 | /* distribute time for this arc: */ | |
155 | arc->time = child->hist.time * (((double) arc->count) | |
156 | / ((double) child->ncalls)); | |
157 | arc->child_time = child->cg.child_time | |
158 | * (((double) arc->count) / ((double) child->ncalls)); | |
159 | share = arc->time + arc->child_time; | |
160 | parent->cg.child_time += share; | |
161 | ||
162 | /* (1 - cg.prop.fract) gets lost along the way: */ | |
163 | prop_share = parent->cg.prop.fract * share; | |
164 | ||
165 | /* fix things for printing: */ | |
166 | parent->cg.prop.child += prop_share; | |
167 | arc->time *= parent->cg.prop.fract; | |
168 | arc->child_time *= parent->cg.prop.fract; | |
169 | ||
170 | /* add this share to the parent's cycle header, if any: */ | |
171 | if (parent->cg.cyc.head != parent) | |
172 | { | |
173 | parent->cg.cyc.head->cg.child_time += share; | |
174 | parent->cg.cyc.head->cg.prop.child += prop_share; | |
03c35bcb | 175 | } |
12516a37 KR |
176 | DBG (PROPDEBUG, |
177 | printf ("[prop_time] child \t"); | |
178 | print_name (child); | |
179 | printf (" with %f %f %d/%d\n", child->hist.time, | |
5489fcc3 | 180 | child->cg.child_time, arc->count, child->ncalls); |
12516a37 KR |
181 | printf ("[prop_time] parent\t"); |
182 | print_name (parent); | |
183 | printf ("\n[prop_time] share %f\n", share)); | |
03c35bcb KR |
184 | } |
185 | } | |
5489fcc3 KR |
186 | |
187 | ||
188 | /* | |
189 | * Compute the time of a cycle as the sum of the times of all | |
190 | * its members. | |
191 | */ | |
192 | static void | |
12516a37 | 193 | DEFUN_VOID (cycle_time) |
5489fcc3 | 194 | { |
12516a37 KR |
195 | Sym *member, *cyc; |
196 | ||
197 | for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc) | |
198 | { | |
199 | for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) | |
200 | { | |
201 | if (member->cg.prop.fract == 0.0) | |
202 | { | |
203 | /* | |
204 | * All members have the same propfraction except those | |
205 | * that were excluded with -E. | |
206 | */ | |
207 | continue; | |
03c35bcb | 208 | } |
12516a37 | 209 | cyc->hist.time += member->hist.time; |
03c35bcb | 210 | } |
12516a37 | 211 | cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time; |
03c35bcb KR |
212 | } |
213 | } | |
5489fcc3 KR |
214 | |
215 | ||
216 | static void | |
12516a37 | 217 | DEFUN_VOID (cycle_link) |
5489fcc3 | 218 | { |
12516a37 KR |
219 | Sym *sym, *cyc, *member; |
220 | Arc *arc; | |
221 | int num; | |
222 | ||
223 | /* count the number of cycles, and initialize the cycle lists: */ | |
224 | ||
225 | num_cycles = 0; | |
226 | for (sym = symtab.base; sym < symtab.limit; ++sym) | |
227 | { | |
228 | /* this is how you find unattached cycles: */ | |
229 | if (sym->cg.cyc.head == sym && sym->cg.cyc.next) | |
230 | { | |
231 | ++num_cycles; | |
03c35bcb KR |
232 | } |
233 | } | |
12516a37 KR |
234 | |
235 | /* | |
236 | * cycle_header is indexed by cycle number: i.e. it is origin 1, | |
237 | * not origin 0. | |
238 | */ | |
239 | cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym)); | |
240 | ||
241 | /* | |
242 | * Now link cycles to true cycle-heads, number them, accumulate | |
243 | * the data for the cycle. | |
244 | */ | |
245 | num = 0; | |
246 | cyc = cycle_header; | |
247 | for (sym = symtab.base; sym < symtab.limit; ++sym) | |
248 | { | |
249 | if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0)) | |
250 | { | |
251 | continue; | |
03c35bcb | 252 | } |
12516a37 KR |
253 | ++num; |
254 | ++cyc; | |
255 | sym_init (cyc); | |
256 | cyc->cg.print_flag = TRUE; /* should this be printed? */ | |
257 | cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */ | |
258 | cyc->cg.cyc.num = num; /* internal number of cycle on */ | |
259 | cyc->cg.cyc.head = cyc; /* pointer to head of cycle */ | |
260 | cyc->cg.cyc.next = sym; /* pointer to next member of cycle */ | |
261 | DBG (CYCLEDEBUG, printf ("[cycle_link] "); | |
262 | print_name (sym); | |
263 | printf (" is the head of cycle %d\n", num)); | |
264 | ||
265 | /* link members to cycle header: */ | |
266 | for (member = sym; member; member = member->cg.cyc.next) | |
267 | { | |
268 | member->cg.cyc.num = num; | |
269 | member->cg.cyc.head = cyc; | |
03c35bcb | 270 | } |
12516a37 KR |
271 | |
272 | /* | |
273 | * Count calls from outside the cycle and those among cycle | |
274 | * members: | |
275 | */ | |
276 | for (member = sym; member; member = member->cg.cyc.next) | |
277 | { | |
278 | for (arc = member->cg.parents; arc; arc = arc->next_parent) | |
279 | { | |
280 | if (arc->parent == member) | |
281 | { | |
282 | continue; | |
03c35bcb | 283 | } |
12516a37 KR |
284 | if (arc->parent->cg.cyc.num == num) |
285 | { | |
286 | cyc->cg.self_calls += arc->count; | |
287 | } | |
288 | else | |
289 | { | |
290 | cyc->ncalls += arc->count; | |
03c35bcb KR |
291 | } |
292 | } | |
293 | } | |
294 | } | |
295 | } | |
5489fcc3 KR |
296 | |
297 | ||
298 | /* | |
299 | * Check if any parent of this child (or outside parents of this | |
300 | * cycle) have their print flags on and set the print flag of the | |
301 | * child (cycle) appropriately. Similarly, deal with propagation | |
302 | * fractions from parents. | |
303 | */ | |
304 | static void | |
12516a37 | 305 | DEFUN (inherit_flags, (child), Sym * child) |
5489fcc3 | 306 | { |
12516a37 KR |
307 | Sym *head, *parent, *member; |
308 | Arc *arc; | |
309 | ||
310 | head = child->cg.cyc.head; | |
311 | if (child == head) | |
312 | { | |
313 | /* just a regular child, check its parents: */ | |
314 | child->cg.print_flag = FALSE; | |
315 | child->cg.prop.fract = 0.0; | |
316 | for (arc = child->cg.parents; arc; arc = arc->next_parent) | |
317 | { | |
318 | parent = arc->parent; | |
319 | if (child == parent) | |
320 | { | |
321 | continue; | |
03c35bcb | 322 | } |
12516a37 KR |
323 | child->cg.print_flag |= parent->cg.print_flag; |
324 | /* | |
325 | * If the child was never actually called (e.g., this arc | |
326 | * is static (and all others are, too)) no time propagates | |
327 | * along this arc. | |
328 | */ | |
329 | if (child->ncalls) | |
330 | { | |
331 | child->cg.prop.fract += parent->cg.prop.fract | |
332 | * (((double) arc->count) / ((double) child->ncalls)); | |
03c35bcb KR |
333 | } |
334 | } | |
12516a37 KR |
335 | } |
336 | else | |
337 | { | |
338 | /* | |
339 | * Its a member of a cycle, look at all parents from outside | |
340 | * the cycle. | |
341 | */ | |
342 | head->cg.print_flag = FALSE; | |
343 | head->cg.prop.fract = 0.0; | |
344 | for (member = head->cg.cyc.next; member; member = member->cg.cyc.next) | |
345 | { | |
346 | for (arc = member->cg.parents; arc; arc = arc->next_parent) | |
347 | { | |
348 | if (arc->parent->cg.cyc.head == head) | |
349 | { | |
350 | continue; | |
03c35bcb | 351 | } |
12516a37 KR |
352 | parent = arc->parent; |
353 | head->cg.print_flag |= parent->cg.print_flag; | |
354 | /* | |
355 | * If the cycle was never actually called (e.g. this | |
356 | * arc is static (and all others are, too)) no time | |
357 | * propagates along this arc. | |
358 | */ | |
359 | if (head->ncalls) | |
360 | { | |
361 | head->cg.prop.fract += parent->cg.prop.fract | |
362 | * (((double) arc->count) / ((double) head->ncalls)); | |
03c35bcb KR |
363 | } |
364 | } | |
365 | } | |
12516a37 | 366 | for (member = head; member; member = member->cg.cyc.next) |
5489fcc3 | 367 | { |
12516a37 KR |
368 | member->cg.print_flag = head->cg.print_flag; |
369 | member->cg.prop.fract = head->cg.prop.fract; | |
03c35bcb KR |
370 | } |
371 | } | |
372 | } | |
5489fcc3 KR |
373 | |
374 | ||
375 | /* | |
376 | * In one top-to-bottom pass over the topologically sorted symbols | |
377 | * propagate: | |
12516a37 KR |
378 | * cg.print_flag as the union of parents' print_flags |
379 | * propfraction as the sum of fractional parents' propfractions | |
5489fcc3 KR |
380 | * and while we're here, sum time for functions. |
381 | */ | |
382 | static void | |
12516a37 | 383 | DEFUN (propagate_flags, (symbols), Sym ** symbols) |
5489fcc3 | 384 | { |
12516a37 KR |
385 | int index; |
386 | Sym *old_head, *child; | |
387 | ||
388 | old_head = 0; | |
389 | for (index = symtab.len - 1; index >= 0; --index) | |
390 | { | |
391 | child = symbols[index]; | |
392 | /* | |
393 | * If we haven't done this function or cycle, inherit things | |
394 | * from parent. This way, we are linear in the number of arcs | |
395 | * since we do all members of a cycle (and the cycle itself) | |
396 | * as we hit the first member of the cycle. | |
397 | */ | |
398 | if (child->cg.cyc.head != old_head) | |
399 | { | |
400 | old_head = child->cg.cyc.head; | |
401 | inherit_flags (child); | |
03c35bcb | 402 | } |
12516a37 KR |
403 | DBG (PROPDEBUG, |
404 | printf ("[prop_flags] "); | |
405 | print_name (child); | |
406 | printf ("inherits print-flag %d and prop-fract %f\n", | |
5489fcc3 | 407 | child->cg.print_flag, child->cg.prop.fract)); |
12516a37 KR |
408 | if (!child->cg.print_flag) |
409 | { | |
410 | /* | |
411 | * Printflag is off. It gets turned on by being in the | |
412 | * INCL_GRAPH table, or there being an empty INCL_GRAPH | |
413 | * table and not being in the EXCL_GRAPH table. | |
414 | */ | |
415 | if (sym_lookup (&syms[INCL_GRAPH], child->addr) | |
416 | || (syms[INCL_GRAPH].len == 0 | |
417 | && !sym_lookup (&syms[EXCL_GRAPH], child->addr))) | |
5489fcc3 | 418 | { |
12516a37 | 419 | child->cg.print_flag = TRUE; |
03c35bcb | 420 | } |
12516a37 KR |
421 | } |
422 | else | |
423 | { | |
424 | /* | |
425 | * This function has printing parents: maybe someone wants | |
426 | * to shut it up by putting it in the EXCL_GRAPH table. | |
427 | * (But favor INCL_GRAPH over EXCL_GRAPH.) | |
428 | */ | |
429 | if (!sym_lookup (&syms[INCL_GRAPH], child->addr) | |
430 | && sym_lookup (&syms[EXCL_GRAPH], child->addr)) | |
5489fcc3 | 431 | { |
12516a37 | 432 | child->cg.print_flag = FALSE; |
03c35bcb KR |
433 | } |
434 | } | |
12516a37 KR |
435 | if (child->cg.prop.fract == 0.0) |
436 | { | |
437 | /* | |
438 | * No parents to pass time to. Collect time from children | |
439 | * if its in the INCL_TIME table, or there is an empty | |
440 | * INCL_TIME table and its not in the EXCL_TIME table. | |
441 | */ | |
442 | if (sym_lookup (&syms[INCL_TIME], child->addr) | |
443 | || (syms[INCL_TIME].len == 0 | |
444 | && !sym_lookup (&syms[EXCL_TIME], child->addr))) | |
5489fcc3 | 445 | { |
12516a37 | 446 | child->cg.prop.fract = 1.0; |
03c35bcb | 447 | } |
12516a37 KR |
448 | } |
449 | else | |
450 | { | |
451 | /* | |
452 | * It has parents to pass time to, but maybe someone wants | |
453 | * to shut it up by puttting it in the EXCL_TIME table. | |
454 | * (But favor being in INCL_TIME tabe over being in | |
455 | * EXCL_TIME table.) | |
456 | */ | |
457 | if (!sym_lookup (&syms[INCL_TIME], child->addr) | |
458 | && sym_lookup (&syms[EXCL_TIME], child->addr)) | |
5489fcc3 | 459 | { |
12516a37 | 460 | child->cg.prop.fract = 0.0; |
03c35bcb KR |
461 | } |
462 | } | |
12516a37 KR |
463 | child->cg.prop.self = child->hist.time * child->cg.prop.fract; |
464 | print_time += child->cg.prop.self; | |
465 | DBG (PROPDEBUG, | |
466 | printf ("[prop_flags] "); | |
467 | print_name (child); | |
468 | printf (" ends up with printflag %d and prop-fract %f\n", | |
5489fcc3 | 469 | child->cg.print_flag, child->cg.prop.fract); |
12516a37 | 470 | printf ("[prop_flags] time %f propself %f print_time %f\n", |
5489fcc3 | 471 | child->hist.time, child->cg.prop.self, print_time)); |
03c35bcb KR |
472 | } |
473 | } | |
5489fcc3 KR |
474 | |
475 | ||
476 | /* | |
477 | * Compare by decreasing propagated time. If times are equal, but one | |
478 | * is a cycle header, say that's first (e.g. less, i.e. -1). If one's | |
479 | * name doesn't have an underscore and the other does, say that one is | |
480 | * first. All else being equal, compare by names. | |
481 | */ | |
482 | static int | |
12516a37 | 483 | DEFUN (cmp_total, (lp, rp), const PTR lp AND const PTR rp) |
5489fcc3 | 484 | { |
12516a37 KR |
485 | const Sym *left = *(const Sym **) lp; |
486 | const Sym *right = *(const Sym **) rp; | |
487 | double diff; | |
488 | ||
489 | diff = (left->cg.prop.self + left->cg.prop.child) | |
490 | - (right->cg.prop.self + right->cg.prop.child); | |
491 | if (diff < 0.0) | |
492 | { | |
493 | return 1; | |
03c35bcb | 494 | } |
12516a37 KR |
495 | if (diff > 0.0) |
496 | { | |
497 | return -1; | |
03c35bcb | 498 | } |
12516a37 KR |
499 | if (!left->name && left->cg.cyc.num != 0) |
500 | { | |
501 | return -1; | |
03c35bcb | 502 | } |
12516a37 KR |
503 | if (!right->name && right->cg.cyc.num != 0) |
504 | { | |
505 | return 1; | |
03c35bcb | 506 | } |
12516a37 KR |
507 | if (!left->name) |
508 | { | |
509 | return -1; | |
03c35bcb | 510 | } |
12516a37 KR |
511 | if (!right->name) |
512 | { | |
513 | return 1; | |
03c35bcb | 514 | } |
12516a37 KR |
515 | if (left->name[0] != '_' && right->name[0] == '_') |
516 | { | |
517 | return -1; | |
03c35bcb | 518 | } |
12516a37 KR |
519 | if (left->name[0] == '_' && right->name[0] != '_') |
520 | { | |
521 | return 1; | |
03c35bcb | 522 | } |
12516a37 KR |
523 | if (left->ncalls > right->ncalls) |
524 | { | |
525 | return -1; | |
03c35bcb | 526 | } |
12516a37 KR |
527 | if (left->ncalls < right->ncalls) |
528 | { | |
529 | return 1; | |
03c35bcb | 530 | } |
12516a37 | 531 | return strcmp (left->name, right->name); |
03c35bcb | 532 | } |
5489fcc3 KR |
533 | |
534 | ||
535 | /* | |
536 | * Topologically sort the graph (collapsing cycles), and propagates | |
537 | * time bottom up and flags top down. | |
538 | */ | |
12516a37 KR |
539 | Sym ** |
540 | DEFUN_VOID (cg_assemble) | |
5489fcc3 | 541 | { |
12516a37 KR |
542 | Sym *parent, **time_sorted_syms, **top_sorted_syms; |
543 | long index; | |
544 | Arc *arc; | |
545 | extern void find_call PARAMS ((Sym * parent, | |
546 | bfd_vma p_lowpc, bfd_vma p_highpc)); | |
547 | /* | |
548 | * initialize various things: | |
549 | * zero out child times. | |
550 | * count self-recursive calls. | |
551 | * indicate that nothing is on cycles. | |
552 | */ | |
553 | for (parent = symtab.base; parent < symtab.limit; parent++) | |
554 | { | |
555 | parent->cg.child_time = 0.0; | |
556 | arc = arc_lookup (parent, parent); | |
557 | if (arc && parent == arc->child) | |
558 | { | |
559 | parent->ncalls -= arc->count; | |
560 | parent->cg.self_calls = arc->count; | |
561 | } | |
562 | else | |
563 | { | |
564 | parent->cg.self_calls = 0; | |
03c35bcb | 565 | } |
12516a37 KR |
566 | parent->cg.prop.fract = 0.0; |
567 | parent->cg.prop.self = 0.0; | |
568 | parent->cg.prop.child = 0.0; | |
569 | parent->cg.print_flag = FALSE; | |
570 | parent->cg.top_order = DFN_NAN; | |
571 | parent->cg.cyc.num = 0; | |
572 | parent->cg.cyc.head = parent; | |
573 | parent->cg.cyc.next = 0; | |
574 | if (ignore_direct_calls) | |
575 | { | |
576 | find_call (parent, parent->addr, (parent + 1)->addr); | |
03c35bcb KR |
577 | } |
578 | } | |
12516a37 KR |
579 | /* |
580 | * Topologically order things. If any node is unnumbered, number | |
581 | * it and any of its descendents. | |
582 | */ | |
583 | for (parent = symtab.base; parent < symtab.limit; parent++) | |
584 | { | |
585 | if (parent->cg.top_order == DFN_NAN) | |
586 | { | |
587 | cg_dfn (parent); | |
03c35bcb KR |
588 | } |
589 | } | |
12516a37 KR |
590 | |
591 | /* link together nodes on the same cycle: */ | |
592 | cycle_link (); | |
593 | ||
594 | /* sort the symbol table in reverse topological order: */ | |
595 | top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
596 | for (index = 0; index < symtab.len; ++index) | |
597 | { | |
598 | top_sorted_syms[index] = &symtab.base[index]; | |
03c35bcb | 599 | } |
12516a37 KR |
600 | qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo); |
601 | DBG (DFNDEBUG, | |
602 | printf ("[cg_assemble] topological sort listing\n"); | |
603 | for (index = 0; index < symtab.len; ++index) | |
604 | { | |
605 | printf ("[cg_assemble] "); | |
606 | printf ("%d:", top_sorted_syms[index]->cg.top_order); | |
607 | print_name (top_sorted_syms[index]); | |
608 | printf ("\n"); | |
03c35bcb | 609 | } |
12516a37 KR |
610 | ); |
611 | /* | |
612 | * Starting from the topological top, propagate print flags to | |
613 | * children. also, calculate propagation fractions. this happens | |
614 | * before time propagation since time propagation uses the | |
615 | * fractions. | |
616 | */ | |
617 | propagate_flags (top_sorted_syms); | |
618 | ||
619 | /* | |
620 | * Starting from the topological bottom, propogate children times | |
621 | * up to parents. | |
622 | */ | |
623 | cycle_time (); | |
624 | for (index = 0; index < symtab.len; ++index) | |
625 | { | |
626 | propagate_time (top_sorted_syms[index]); | |
03c35bcb | 627 | } |
12516a37 KR |
628 | |
629 | free (top_sorted_syms); | |
630 | ||
631 | /* | |
632 | * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular | |
633 | * function names and cycle headers. | |
634 | */ | |
635 | time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *)); | |
636 | for (index = 0; index < symtab.len; index++) | |
637 | { | |
638 | time_sorted_syms[index] = &symtab.base[index]; | |
03c35bcb | 639 | } |
12516a37 KR |
640 | for (index = 1; index <= num_cycles; index++) |
641 | { | |
642 | time_sorted_syms[symtab.len + index - 1] = &cycle_header[index]; | |
03c35bcb | 643 | } |
12516a37 KR |
644 | qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *), |
645 | cmp_total); | |
646 | for (index = 0; index < symtab.len + num_cycles; index++) | |
647 | { | |
648 | time_sorted_syms[index]->cg.index = index + 1; | |
03c35bcb | 649 | } |
12516a37 | 650 | return time_sorted_syms; |
03c35bcb | 651 | } |