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.
21 static char sccsid
[] = "@(#)arcs.c 5.6 (Berkeley) 6/1/90";
27 * add (or just increment) an arc
29 addarc( parentp
, childp
, count
)
37 if ( debug
& TALLYDEBUG
) {
38 printf( "[addarc] %d arcs from %s to %s\n" ,
39 count
, parentp
-> name
, childp
-> name
);
42 arcp
= arclookup( parentp
, childp
);
45 * a hit: just increment the count.
48 if ( debug
& TALLYDEBUG
) {
49 printf( "[tally] hit %d += %d\n" ,
50 arcp
-> arc_count
, count
);
53 arcp
-> arc_count
+= count
;
56 arcp
= (arctype
*) calloc( 1 , sizeof *arcp
);
57 arcp
-> arc_parentp
= parentp
;
58 arcp
-> arc_childp
= childp
;
59 arcp
-> arc_count
= count
;
61 * prepend this child to the children of this parent
63 arcp
-> arc_childlist
= parentp
-> children
;
64 parentp
-> children
= arcp
;
66 * prepend this parent to the parents of this child
68 arcp
-> arc_parentlist
= childp
-> parents
;
69 childp
-> parents
= arcp
;
73 * the code below topologically sorts the graph (collapsing cycles),
74 * and propagates time bottom up and flags top down.
78 * the topologically sorted name list pointers
86 return (*npp1
) -> toporder
- (*npp2
) -> toporder
;
92 nltype
*parentp
, **timesortnlp
;
97 * initialize various things:
98 * zero out child times.
99 * count self-recursive calls.
100 * indicate that nothing is on cycles.
102 for ( parentp
= nl
; parentp
< npe
; parentp
++ ) {
103 parentp
-> childtime
= 0.0;
104 arcp
= arclookup( parentp
, parentp
);
106 parentp
-> ncall
-= arcp
-> arc_count
;
107 parentp
-> selfcalls
= arcp
-> arc_count
;
109 parentp
-> selfcalls
= 0;
111 parentp
-> propfraction
= 0.0;
112 parentp
-> propself
= 0.0;
113 parentp
-> propchild
= 0.0;
114 parentp
-> printflag
= FALSE
;
115 parentp
-> toporder
= DFN_NAN
;
116 parentp
-> cycleno
= 0;
117 parentp
-> cyclehead
= parentp
;
118 parentp
-> cnext
= 0;
120 findcall( parentp
, parentp
-> value
, (parentp
+1) -> value
);
124 * topologically order things
125 * if any node is unnumbered,
126 * number it and any of its descendents.
128 for ( parentp
= nl
; parentp
< npe
; parentp
++ ) {
129 if ( parentp
-> toporder
== DFN_NAN
) {
134 * link together nodes on the same cycle
138 * Sort the symbol table in reverse topological order
140 topsortnlp
= (nltype
**) calloc( nname
, sizeof(nltype
*) );
141 if ( topsortnlp
== (nltype
**) 0 ) {
142 fprintf( stderr
, "[doarcs] ran out of memory for topo sorting\n" );
144 for ( index
= 0 ; index
< nname
; index
+= 1 ) {
145 topsortnlp
[ index
] = &nl
[ index
];
147 qsort( topsortnlp
, nname
, sizeof(nltype
*) , topcmp
);
149 if ( debug
& DFNDEBUG
) {
150 printf( "[doarcs] topological sort listing\n" );
151 for ( index
= 0 ; index
< nname
; index
+= 1 ) {
152 printf( "[doarcs] " );
153 printf( "%d:" , topsortnlp
[ index
] -> toporder
);
154 printname( topsortnlp
[ index
] );
160 * starting from the topological top,
161 * propagate print flags to children.
162 * also, calculate propagation fractions.
163 * this happens before time propagation
164 * since time propagation uses the fractions.
168 * starting from the topological bottom,
169 * propogate children times up to parents.
173 * Now, sort by propself + propchild.
174 * sorting both the regular function names
177 timesortnlp
= (nltype
**) calloc( nname
+ ncycle
, sizeof(nltype
*) );
178 if ( timesortnlp
== (nltype
**) 0 ) {
179 fprintf( stderr
, "%s: ran out of memory for sorting\n" , whoami
);
181 for ( index
= 0 ; index
< nname
; index
++ ) {
182 timesortnlp
[index
] = &nl
[index
];
184 for ( index
= 1 ; index
<= ncycle
; index
++ ) {
185 timesortnlp
[nname
+index
-1] = &cyclenl
[index
];
187 qsort( timesortnlp
, nname
+ ncycle
, sizeof(nltype
*) , totalcmp
);
188 for ( index
= 0 ; index
< nname
+ ncycle
; index
++ ) {
189 timesortnlp
[ index
] -> index
= index
+ 1;
191 return( timesortnlp
);
199 for ( index
= 0 ; index
< nname
; index
+= 1 ) {
200 timepropagate( topsortnlp
[ index
] );
204 timepropagate( parentp
)
212 if ( parentp
-> propfraction
== 0.0 ) {
216 * gather time from children of this parent.
218 for ( arcp
= parentp
-> children
; arcp
; arcp
= arcp
-> arc_childlist
) {
219 childp
= arcp
-> arc_childp
;
220 if ( arcp
-> arc_count
== 0 ) {
223 if ( childp
== parentp
) {
226 if ( childp
-> propfraction
== 0.0 ) {
229 if ( childp
-> cyclehead
!= childp
) {
230 if ( parentp
-> cycleno
== childp
-> cycleno
) {
233 if ( parentp
-> toporder
<= childp
-> toporder
) {
234 fprintf( stderr
, "[propagate] toporder botches\n" );
236 childp
= childp
-> cyclehead
;
238 if ( parentp
-> toporder
<= childp
-> toporder
) {
239 fprintf( stderr
, "[propagate] toporder botches\n" );
243 if ( childp
-> ncall
== 0 ) {
247 * distribute time for this arc
249 arcp
-> arc_time
= childp
-> time
250 * ( ( (double) arcp
-> arc_count
) /
251 ( (double) childp
-> ncall
) );
252 arcp
-> arc_childtime
= childp
-> childtime
253 * ( ( (double) arcp
-> arc_count
) /
254 ( (double) childp
-> ncall
) );
255 share
= arcp
-> arc_time
+ arcp
-> arc_childtime
;
256 parentp
-> childtime
+= share
;
258 * ( 1 - propfraction ) gets lost along the way
260 propshare
= parentp
-> propfraction
* share
;
262 * fix things for printing
264 parentp
-> propchild
+= propshare
;
265 arcp
-> arc_time
*= parentp
-> propfraction
;
266 arcp
-> arc_childtime
*= parentp
-> propfraction
;
268 * add this share to the parent's cycle header, if any.
270 if ( parentp
-> cyclehead
!= parentp
) {
271 parentp
-> cyclehead
-> childtime
+= share
;
272 parentp
-> cyclehead
-> propchild
+= propshare
;
275 if ( debug
& PROPDEBUG
) {
276 printf( "[dotime] child \t" );
278 printf( " with %f %f %d/%d\n" ,
279 childp
-> time
, childp
-> childtime
,
280 arcp
-> arc_count
, childp
-> ncall
);
281 printf( "[dotime] parent\t" );
282 printname( parentp
);
283 printf( "\n[dotime] share %f\n" , share
);
291 register nltype
*nlp
;
292 register nltype
*cyclenlp
;
298 * Count the number of cycles, and initialze the cycle lists
301 for ( nlp
= nl
; nlp
< npe
; nlp
++ ) {
303 * this is how you find unattached cycles
305 if ( nlp
-> cyclehead
== nlp
&& nlp
-> cnext
!= 0 ) {
310 * cyclenl is indexed by cycle number:
311 * i.e. it is origin 1, not origin 0.
313 cyclenl
= (nltype
*) calloc( ncycle
+ 1 , sizeof( nltype
) );
314 if ( cyclenl
== 0 ) {
315 fprintf( stderr
, "%s: No room for %d bytes of cycle headers\n" ,
316 whoami
, ( ncycle
+ 1 ) * sizeof( nltype
) );
320 * now link cycles to true cycleheads,
321 * number them, accumulate the data for the cycle
324 for ( nlp
= nl
; nlp
< npe
; nlp
++ ) {
325 if ( !( nlp
-> cyclehead
== nlp
&& nlp
-> cnext
!= 0 ) ) {
329 cyclenlp
= &cyclenl
[cycle
];
330 cyclenlp
-> name
= 0; /* the name */
331 cyclenlp
-> value
= 0; /* the pc entry point */
332 cyclenlp
-> time
= 0.0; /* ticks in this routine */
333 cyclenlp
-> childtime
= 0.0; /* cumulative ticks in children */
334 cyclenlp
-> ncall
= 0; /* how many times called */
335 cyclenlp
-> selfcalls
= 0; /* how many calls to self */
336 cyclenlp
-> propfraction
= 0.0; /* what % of time propagates */
337 cyclenlp
-> propself
= 0.0; /* how much self time propagates */
338 cyclenlp
-> propchild
= 0.0; /* how much child time propagates */
339 cyclenlp
-> printflag
= TRUE
; /* should this be printed? */
340 cyclenlp
-> index
= 0; /* index in the graph list */
341 cyclenlp
-> toporder
= DFN_NAN
; /* graph call chain top-sort order */
342 cyclenlp
-> cycleno
= cycle
; /* internal number of cycle on */
343 cyclenlp
-> cyclehead
= cyclenlp
; /* pointer to head of cycle */
344 cyclenlp
-> cnext
= nlp
; /* pointer to next member of cycle */
345 cyclenlp
-> parents
= 0; /* list of caller arcs */
346 cyclenlp
-> children
= 0; /* list of callee arcs */
348 if ( debug
& CYCLEDEBUG
) {
349 printf( "[cyclelink] " );
351 printf( " is the head of cycle %d\n" , cycle
);
355 * link members to cycle header
357 for ( memberp
= nlp
; memberp
; memberp
= memberp
-> cnext
) {
358 memberp
-> cycleno
= cycle
;
359 memberp
-> cyclehead
= cyclenlp
;
362 * count calls from outside the cycle
363 * and those among cycle members
365 for ( memberp
= nlp
; memberp
; memberp
= memberp
-> cnext
) {
366 for ( arcp
=memberp
->parents
; arcp
; arcp
=arcp
->arc_parentlist
) {
367 if ( arcp
-> arc_parentp
== memberp
) {
370 if ( arcp
-> arc_parentp
-> cycleno
== cycle
) {
371 cyclenlp
-> selfcalls
+= arcp
-> arc_count
;
373 cyclenlp
-> ncall
+= arcp
-> arc_count
;
386 for ( cycle
= 1 ; cycle
<= ncycle
; cycle
+= 1 ) {
387 cyclenlp
= &cyclenl
[ cycle
];
388 for ( childp
= cyclenlp
-> cnext
; childp
; childp
= childp
-> cnext
) {
389 if ( childp
-> propfraction
== 0.0 ) {
391 * all members have the same propfraction except those
392 * that were excluded with -E
396 cyclenlp
-> time
+= childp
-> time
;
398 cyclenlp
-> propself
= cyclenlp
-> propfraction
* cyclenlp
-> time
;
403 * in one top to bottom pass over the topologically sorted namelist
405 * printflag as the union of parents' printflags
406 * propfraction as the sum of fractional parents' propfractions
407 * and while we're here, sum time for functions.
416 for ( index
= nname
-1 ; index
>= 0 ; index
-= 1 ) {
417 childp
= topsortnlp
[ index
];
419 * if we haven't done this function or cycle,
420 * inherit things from parent.
421 * this way, we are linear in the number of arcs
422 * since we do all members of a cycle (and the cycle itself)
423 * as we hit the first member of the cycle.
425 if ( childp
-> cyclehead
!= oldhead
) {
426 oldhead
= childp
-> cyclehead
;
427 inheritflags( childp
);
430 if ( debug
& PROPDEBUG
) {
431 printf( "[doflags] " );
433 printf( " inherits printflag %d and propfraction %f\n" ,
434 childp
-> printflag
, childp
-> propfraction
);
437 if ( ! childp
-> printflag
) {
440 * it gets turned on by
442 * or there not being any -f list and not being on -e list.
444 if ( onlist( flist
, childp
-> name
)
445 || ( !fflag
&& !onlist( elist
, childp
-> name
) ) ) {
446 childp
-> printflag
= TRUE
;
450 * this function has printing parents:
451 * maybe someone wants to shut it up
452 * by putting it on -e list. (but favor -f over -e)
454 if ( ( !onlist( flist
, childp
-> name
) )
455 && onlist( elist
, childp
-> name
) ) {
456 childp
-> printflag
= FALSE
;
459 if ( childp
-> propfraction
== 0.0 ) {
461 * no parents to pass time to.
462 * collect time from children if
464 * or there isn't any -F list and its not on -E list.
466 if ( onlist( Flist
, childp
-> name
)
467 || ( !Fflag
&& !onlist( Elist
, childp
-> name
) ) ) {
468 childp
-> propfraction
= 1.0;
472 * it has parents to pass time to,
473 * but maybe someone wants to shut it up
474 * by puttting it on -E list. (but favor -F over -E)
476 if ( !onlist( Flist
, childp
-> name
)
477 && onlist( Elist
, childp
-> name
) ) {
478 childp
-> propfraction
= 0.0;
481 childp
-> propself
= childp
-> time
* childp
-> propfraction
;
482 printtime
+= childp
-> propself
;
484 if ( debug
& PROPDEBUG
) {
485 printf( "[doflags] " );
487 printf( " ends up with printflag %d and propfraction %f\n" ,
488 childp
-> printflag
, childp
-> propfraction
);
489 printf( "time %f propself %f printtime %f\n" ,
490 childp
-> time
, childp
-> propself
, printtime
);
497 * check if any parent of this child
498 * (or outside parents of this cycle)
499 * have their print flags on and set the
500 * print flag of the child (cycle) appropriately.
501 * similarly, deal with propagation fractions from parents.
503 inheritflags( childp
)
511 headp
= childp
-> cyclehead
;
512 if ( childp
== headp
) {
514 * just a regular child, check its parents
516 childp
-> printflag
= FALSE
;
517 childp
-> propfraction
= 0.0;
518 for (arcp
= childp
-> parents
; arcp
; arcp
= arcp
-> arc_parentlist
) {
519 parentp
= arcp
-> arc_parentp
;
520 if ( childp
== parentp
) {
523 childp
-> printflag
|= parentp
-> printflag
;
525 * if the child was never actually called
526 * (e.g. this arc is static (and all others are, too))
527 * no time propagates along this arc.
529 if ( childp
-> ncall
) {
530 childp
-> propfraction
+= parentp
-> propfraction
531 * ( ( (double) arcp
-> arc_count
)
532 / ( (double) childp
-> ncall
) );
537 * its a member of a cycle, look at all parents from
540 headp
-> printflag
= FALSE
;
541 headp
-> propfraction
= 0.0;
542 for ( memp
= headp
-> cnext
; memp
; memp
= memp
-> cnext
) {
543 for (arcp
= memp
->parents
; arcp
; arcp
= arcp
->arc_parentlist
) {
544 if ( arcp
-> arc_parentp
-> cyclehead
== headp
) {
547 parentp
= arcp
-> arc_parentp
;
548 headp
-> printflag
|= parentp
-> printflag
;
550 * if the cycle was never actually called
551 * (e.g. this arc is static (and all others are, too))
552 * no time propagates along this arc.
554 if ( headp
-> ncall
) {
555 headp
-> propfraction
+= parentp
-> propfraction
556 * ( ( (double) arcp
-> arc_count
)
557 / ( (double) headp
-> ncall
) );
561 for ( memp
= headp
; memp
; memp
= memp
-> cnext
) {
562 memp
-> printflag
= headp
-> printflag
;
563 memp
-> propfraction
= headp
-> propfraction
;
This page took 0.041871 seconds and 4 git commands to generate.