static char *sccsid
= "@(#)arcs.c 1.1 (Berkeley) %G%";
return (*npp1
) -> toporder
- (*npp2
) -> toporder
;
* sort by decreasing total time (time+childtime)
* if times are equal, but one is a cycle header,
* say that's first (e.g. less)
register nltype
*np1
= *npp1
;
register nltype
*np2
= *npp2
;
diff
= ( np1
-> time
+ np1
-> childtime
)
- ( np2
-> time
+ np2
-> childtime
);
if ( np1
-> name
== 0 && np1
-> cycleno
!= 0 )
if ( np2
-> name
== 0 && np1
-> cycleno
!= 0 )
* initialize various things:
* count self-recursive calls.
* indicate that nothing is on cycles.
for ( parentp
= nl
; parentp
< npe
; parentp
++ ) {
parentp
-> childtime
= 0.0;
arcp
= arclookup( parentp
, parentp
);
parentp
-> ncall
-= arcp
-> arc_count
;
parentp
-> selfcalls
= arcp
-> arc_count
;
parentp
-> selfcalls
= 0;
parentp
-> cyclehead
= parentp
;
* topologically order things
* from each of the roots of the call graph
for ( parentp
= nl
; parentp
< npe
; parentp
++ ) {
if ( parentp
-> parents
== 0 ) {
* link together nodes on the same cycle
* Sort the symbol table in reverse topological order
topsortnlp
= (nltype
**) calloc( nname
, sizeof(nltype
*) );
if ( topsortnlp
== (nltype
**) 0 ) {
fprintf( stderr
, "[doarcs] ran out of memory for topo sorting\n" );
for ( index
= 0 ; index
< nname
; index
+= 1 ) {
topsortnlp
[ index
] = &nl
[ index
];
qsort( topsortnlp
, nname
, sizeof(nltype
*) , topcmp
);
if ( debug
& DFNDEBUG
) {
printf( "[doarcs] topological sort listing\n" );
for ( index
= 0 ; index
< nname
; index
+= 1 ) {
printf( "%d:" , topsortnlp
[ index
] -> toporder
);
printname( topsortnlp
[ index
] );
* starting from the topological bottom,
* propogate children times
for ( index
= 0 ; index
< nname
; index
+= 1 ) {
parentp
= topsortnlp
[ index
];
for ( arcp
= parentp
->children
; arcp
; arcp
= arcp
->arc_childlist
) {
childp
= arcp
-> arc_childp
;
if ( debug
& ARCDEBUG
) {
printf( " %d (%d) times\n" ,
arcp
-> arc_count
, childp
-> ncall
);
if ( arcp
-> arc_count
== 0 ) {
if ( childp
-> ncall
== 0 ) {
if ( childp
== parentp
) {
if ( childp
-> cyclehead
!= childp
) {
if ( parentp
-> cycleno
== childp
-> cycleno
) {
if ( debug
& ARCDEBUG
) {
printf( "[doarcs]\t it's a call into cycle %d\n" ,
if ( parentp
-> toporder
<= childp
-> toporder
) {
fprintf( stderr
, "[doarcs] toporder botches\n" );
childp
= childp
-> cyclehead
;
if ( parentp
-> toporder
<= childp
-> toporder
) {
fprintf( stderr
, "[doarcs] toporder botches\n" );
* distribute time for this arc
arcp
-> arc_time
= childp
-> time
*
( ( (double) arcp
-> arc_count
) /
( (double) childp
-> ncall
) );
arcp
-> arc_childtime
= childp
-> childtime
*
( ( (double) arcp
-> arc_count
) /
( (double) childp
-> ncall
) );
share
= arcp
-> arc_time
+ arcp
-> arc_childtime
;
if ( debug
& ARCDEBUG
) {
printf( " time %8.2f + childtime %8.2f\n" ,
childp
-> time
, childp
-> childtime
);
printf( "[doarcs]\t this is %d arcs of the %d calls\n",
arcp
-> arc_count
, childp
-> ncall
);
printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" ,
arcp
-> arc_time
, arcp
-> arc_childtime
,
parentp
-> childtime
+= share
;
* add this share to the cycle header, if any
if ( parentp
-> cyclehead
!= parentp
) {
if ( debug
& ARCDEBUG
) {
printf( "[doarcs]\t and to cycle %d\n" ,
parentp
-> cyclehead
-> childtime
+= share
;
register nltype
*parentp
;
register nltype
*cyclenlp
;
* Count the number of cycles, and initialze the cycle lists
for ( nlp
= nl
; nlp
< npe
; nlp
++ ) {
* this is how you find unattached cycles
if ( nlp
-> cyclehead
== nlp
&& nlp
-> cnext
!= 0 ) {
if ( cyclemax
> ncycles
) {
fprintf( stderr
, "prof: %d cycles in %d names exceeds %f%%\n" ,
cyclemax
, nname
, CYCLEFRACTION
* 100.0 );
* now link cycles to true cycleheads,
* number them, accumulate the data for the cycle
for ( nlp
= nl
; nlp
< npe
; nlp
++ ) {
if ( nlp
-> cyclehead
!= nlp
|| nlp
-> cnext
== 0 ) {
cyclenlp
= &nl
[nname
+cycle
];
cyclenlp
-> cycleno
= cycle
;
cyclenlp
-> cyclehead
= cyclenlp
;
if ( debug
& CYCLEDEBUG
) {
printf( "[cyclelink] " );
printf( " is the head of cycle %d\n" , cycle
);
* n-squaredly (in the size of the cycle)
* find all the call within the cycle
* (including self-recursive calls)
* and remove them, thus making the cycle into
* `node' with calls only from the outside.
* note: that this doesn't deal with
* self-recursive calls outside cycles (sigh).
for ( parentp
= nlp
; parentp
; parentp
= parentp
-> cnext
) {
parentp
-> cycleno
= cycle
;
parentp
-> cyclehead
= cyclenlp
;
for ( childp
= nlp
; childp
; childp
= childp
-> cnext
) {
if ( parentp
== childp
) {
arcp
= arclookup( parentp
, childp
);
callsamong
+= arcp
-> arc_count
;
if ( debug
& CYCLEDEBUG
) {
printf("[cyclelink] %s calls sibling %s %d times\n",
parentp
-> name
, childp
-> name
,
* collect calls and time around the cycle,
* and save it in the cycle header.
for ( parentp
= nlp
; parentp
; parentp
= parentp
-> cnext
) {
ncall
+= parentp
-> ncall
;
if ( debug
& CYCLEDEBUG
) {
printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" ,
cycle
, time
, ncall
, callsamong
);
cyclenlp
-> ncall
= ncall
;
cyclenlp
-> selfcalls
= callsamong
;
cyclenlp
-> childtime
= 0.0;