* Copyright (c) 1983 Regents of the University of California.
* Redistribution and use in source and binary forms are permitted
* provided that the above copyright notice and this paragraph are
* duplicated in all such forms and that any documentation,
* advertising materials, and other materials related to such
* distribution and use acknowledge that the software was developed
* by the University of California, Berkeley. The name of the
* University may not be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
static char sccsid
[] = "@(#)arcs.c 5.5 (Berkeley) %G%";
* add (or just increment) an arc
addarc( parentp
, childp
, count
)
if ( debug
& TALLYDEBUG
) {
printf( "[addarc] %d arcs from %s to %s\n" ,
count
, parentp
-> name
, childp
-> name
);
arcp
= arclookup( parentp
, childp
);
* a hit: just increment the count.
if ( debug
& TALLYDEBUG
) {
printf( "[tally] hit %d += %d\n" ,
arcp
-> arc_count
, count
);
arcp
-> arc_count
+= count
;
arcp
= calloc( 1 , sizeof *arcp
);
arcp
-> arc_parentp
= parentp
;
arcp
-> arc_childp
= childp
;
arcp
-> arc_count
= count
;
* prepend this child to the children of this parent
arcp
-> arc_childlist
= parentp
-> children
;
parentp
-> children
= arcp
;
* prepend this parent to the parents of this child
arcp
-> arc_parentlist
= childp
-> parents
;
childp
-> parents
= arcp
;
* the code below topologically sorts the graph (collapsing cycles),
* and propagates time bottom up and flags top down.
* the topologically sorted name list pointers
return (*npp1
) -> toporder
- (*npp2
) -> toporder
;
nltype
*parentp
, **timesortnlp
;
* 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
-> propfraction
= 0.0;
parentp
-> propself
= 0.0;
parentp
-> propchild
= 0.0;
parentp
-> printflag
= FALSE
;
parentp
-> toporder
= DFN_NAN
;
parentp
-> cyclehead
= parentp
;
findcall( parentp
, parentp
-> value
, (parentp
+1) -> value
);
* topologically order things
* if any node is unnumbered,
* number it and any of its descendents.
for ( parentp
= nl
; parentp
< npe
; parentp
++ ) {
if ( parentp
-> toporder
== DFN_NAN
) {
* 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 top,
* propagate print flags to children.
* also, calculate propagation fractions.
* this happens before time propagation
* since time propagation uses the fractions.
* starting from the topological bottom,
* propogate children times up to parents.
* Now, sort by propself + propchild.
* sorting both the regular function names
timesortnlp
= (nltype
**) calloc( nname
+ ncycle
, sizeof(nltype
*) );
if ( timesortnlp
== (nltype
**) 0 ) {
fprintf( stderr
, "%s: ran out of memory for sorting\n" , whoami
);
for ( index
= 0 ; index
< nname
; index
++ ) {
timesortnlp
[index
] = &nl
[index
];
for ( index
= 1 ; index
<= ncycle
; index
++ ) {
timesortnlp
[nname
+index
-1] = &cyclenl
[index
];
qsort( timesortnlp
, nname
+ ncycle
, sizeof(nltype
*) , totalcmp
);
for ( index
= 0 ; index
< nname
+ ncycle
; index
++ ) {
timesortnlp
[ index
] -> index
= index
+ 1;
for ( index
= 0 ; index
< nname
; index
+= 1 ) {
timepropagate( topsortnlp
[ index
] );
if ( parentp
-> propfraction
== 0.0 ) {
* gather time from children of this parent.
for ( arcp
= parentp
-> children
; arcp
; arcp
= arcp
-> arc_childlist
) {
childp
= arcp
-> arc_childp
;
if ( arcp
-> arc_count
== 0 ) {
if ( childp
== parentp
) {
if ( childp
-> propfraction
== 0.0 ) {
if ( childp
-> cyclehead
!= childp
) {
if ( parentp
-> cycleno
== childp
-> cycleno
) {
if ( parentp
-> toporder
<= childp
-> toporder
) {
fprintf( stderr
, "[propagate] toporder botches\n" );
childp
= childp
-> cyclehead
;
if ( parentp
-> toporder
<= childp
-> toporder
) {
fprintf( stderr
, "[propagate] toporder botches\n" );
if ( childp
-> ncall
== 0 ) {
* 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
;
parentp
-> childtime
+= share
;
* ( 1 - propfraction ) gets lost along the way
propshare
= parentp
-> propfraction
* share
;
* fix things for printing
parentp
-> propchild
+= propshare
;
arcp
-> arc_time
*= parentp
-> propfraction
;
arcp
-> arc_childtime
*= parentp
-> propfraction
;
* add this share to the parent's cycle header, if any.
if ( parentp
-> cyclehead
!= parentp
) {
parentp
-> cyclehead
-> childtime
+= share
;
parentp
-> cyclehead
-> propchild
+= propshare
;
if ( debug
& PROPDEBUG
) {
printf( "[dotime] child \t" );
printf( " with %f %f %d/%d\n" ,
childp
-> time
, childp
-> childtime
,
arcp
-> arc_count
, childp
-> ncall
);
printf( "[dotime] parent\t" );
printf( "\n[dotime] share %f\n" , share
);
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 ) {
* cyclenl is indexed by cycle number:
* i.e. it is origin 1, not origin 0.
cyclenl
= (nltype
*) calloc( ncycle
+ 1 , sizeof( nltype
) );
fprintf( stderr
, "%s: No room for %d bytes of cycle headers\n" ,
whoami
, ( ncycle
+ 1 ) * sizeof( nltype
) );
* 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
= &cyclenl
[cycle
];
cyclenlp
-> name
= 0; /* the name */
cyclenlp
-> value
= 0; /* the pc entry point */
cyclenlp
-> time
= 0.0; /* ticks in this routine */
cyclenlp
-> childtime
= 0.0; /* cumulative ticks in children */
cyclenlp
-> ncall
= 0; /* how many times called */
cyclenlp
-> selfcalls
= 0; /* how many calls to self */
cyclenlp
-> propfraction
= 0.0; /* what % of time propagates */
cyclenlp
-> propself
= 0.0; /* how much self time propagates */
cyclenlp
-> propchild
= 0.0; /* how much child time propagates */
cyclenlp
-> printflag
= TRUE
; /* should this be printed? */
cyclenlp
-> index
= 0; /* index in the graph list */
cyclenlp
-> toporder
= DFN_NAN
; /* graph call chain top-sort order */
cyclenlp
-> cycleno
= cycle
; /* internal number of cycle on */
cyclenlp
-> cyclehead
= cyclenlp
; /* pointer to head of cycle */
cyclenlp
-> cnext
= nlp
; /* pointer to next member of cycle */
cyclenlp
-> parents
= 0; /* list of caller arcs */
cyclenlp
-> children
= 0; /* list of callee arcs */
if ( debug
& CYCLEDEBUG
) {
printf( "[cyclelink] " );
printf( " is the head of cycle %d\n" , cycle
);
* link members to cycle header
for ( memberp
= nlp
; memberp
; memberp
= memberp
-> cnext
) {
memberp
-> cycleno
= cycle
;
memberp
-> cyclehead
= cyclenlp
;
* count calls from outside the cycle
* and those among cycle members
for ( memberp
= nlp
; memberp
; memberp
= memberp
-> cnext
) {
for ( arcp
=memberp
->parents
; arcp
; arcp
=arcp
->arc_parentlist
) {
if ( arcp
-> arc_parentp
== memberp
) {
if ( arcp
-> arc_parentp
-> cycleno
== cycle
) {
cyclenlp
-> selfcalls
+= arcp
-> arc_count
;
cyclenlp
-> ncall
+= arcp
-> arc_count
;
for ( cycle
= 1 ; cycle
<= ncycle
; cycle
+= 1 ) {
cyclenlp
= &cyclenl
[ cycle
];
for ( childp
= cyclenlp
-> cnext
; childp
; childp
= childp
-> cnext
) {
if ( childp
-> propfraction
== 0.0 ) {
* all members have the same propfraction except those
* that were excluded with -E
cyclenlp
-> time
+= childp
-> time
;
cyclenlp
-> propself
= cyclenlp
-> propfraction
* cyclenlp
-> time
;
* in one top to bottom pass over the topologically sorted namelist
* printflag as the union of parents' printflags
* propfraction as the sum of fractional parents' propfractions
* and while we're here, sum time for functions.
for ( index
= nname
-1 ; index
>= 0 ; index
-= 1 ) {
childp
= topsortnlp
[ index
];
* if we haven't done this function or cycle,
* inherit things from parent.
* this way, we are linear in the number of arcs
* since we do all members of a cycle (and the cycle itself)
* as we hit the first member of the cycle.
if ( childp
-> cyclehead
!= oldhead
) {
oldhead
= childp
-> cyclehead
;
if ( debug
& PROPDEBUG
) {
printf( " inherits printflag %d and propfraction %f\n" ,
childp
-> printflag
, childp
-> propfraction
);
if ( ! childp
-> printflag
) {
* or there not being any -f list and not being on -e list.
if ( onlist( flist
, childp
-> name
)
|| ( !fflag
&& !onlist( elist
, childp
-> name
) ) ) {
childp
-> printflag
= TRUE
;
* this function has printing parents:
* maybe someone wants to shut it up
* by putting it on -e list. (but favor -f over -e)
if ( ( !onlist( flist
, childp
-> name
) )
&& onlist( elist
, childp
-> name
) ) {
childp
-> printflag
= FALSE
;
if ( childp
-> propfraction
== 0.0 ) {
* no parents to pass time to.
* collect time from children if
* or there isn't any -F list and its not on -E list.
if ( onlist( Flist
, childp
-> name
)
|| ( !Fflag
&& !onlist( Elist
, childp
-> name
) ) ) {
childp
-> propfraction
= 1.0;
* it has parents to pass time to,
* but maybe someone wants to shut it up
* by puttting it on -E list. (but favor -F over -E)
if ( !onlist( Flist
, childp
-> name
)
&& onlist( Elist
, childp
-> name
) ) {
childp
-> propfraction
= 0.0;
childp
-> propself
= childp
-> time
* childp
-> propfraction
;
printtime
+= childp
-> propself
;
if ( debug
& PROPDEBUG
) {
printf( " ends up with printflag %d and propfraction %f\n" ,
childp
-> printflag
, childp
-> propfraction
);
printf( "time %f propself %f printtime %f\n" ,
childp
-> time
, childp
-> propself
, printtime
);
* check if any parent of this child
* (or outside parents of this cycle)
* have their print flags on and set the
* print flag of the child (cycle) appropriately.
* similarly, deal with propagation fractions from parents.
headp
= childp
-> cyclehead
;
* just a regular child, check its parents
childp
-> printflag
= FALSE
;
childp
-> propfraction
= 0.0;
for (arcp
= childp
-> parents
; arcp
; arcp
= arcp
-> arc_parentlist
) {
parentp
= arcp
-> arc_parentp
;
if ( childp
== parentp
) {
childp
-> printflag
|= parentp
-> printflag
;
* if the child was never actually called
* (e.g. this arc is static (and all others are, too))
* no time propagates along this arc.
childp
-> propfraction
+= parentp
-> propfraction
* ( ( (double) arcp
-> arc_count
)
/ ( (double) childp
-> ncall
) );
* its a member of a cycle, look at all parents from
headp
-> printflag
= FALSE
;
headp
-> propfraction
= 0.0;
for ( memp
= headp
-> cnext
; memp
; memp
= memp
-> cnext
) {
for (arcp
= memp
->parents
; arcp
; arcp
= arcp
->arc_parentlist
) {
if ( arcp
-> arc_parentp
-> cyclehead
== headp
) {
parentp
= arcp
-> arc_parentp
;
headp
-> printflag
|= parentp
-> printflag
;
* if the cycle was never actually called
* (e.g. this arc is static (and all others are, too))
* no time propagates along this arc.
headp
-> propfraction
+= parentp
-> propfraction
* ( ( (double) arcp
-> arc_count
)
/ ( (double) headp
-> ncall
) );
for ( memp
= headp
; memp
; memp
= memp
-> cnext
) {
memp
-> printflag
= headp
-> printflag
;
memp
-> propfraction
= headp
-> propfraction
;