#include <stdlib.h>
#include "stuff/errors.h"
#include "gprof.h"
static int topcmp(
nltype **npp1,
nltype **npp2);
static void dotime(
void);
static void timepropagate(
nltype *parentp);
static void cyclelink(
void);
static void cycletime(
void);
static void doflags(
void);
static void inheritflags(
nltype *childp);
void
addarc(
nltype *parentp,
nltype *childp,
unsigned long count,
unsigned long order)
{
arctype *arcp;
#ifdef DEBUG
if(debug & TALLYDEBUG){
printf("[addarc] %lu arcs from %s to %s\n" ,
count, parentp->name, childp->name);
}
#endif
arcp = arclookup(parentp, childp);
if(arcp != NULL){
#ifdef DEBUG
if(debug & TALLYDEBUG){
printf("[tally] hit %ld += %lu\n",
arcp->arc_count, count);
}
#endif
arcp->arc_count += count;
return;
}
arcp = (arctype *)calloc(1, sizeof(arctype));
arcp->arc_parentp = parentp;
arcp->arc_childp = childp;
arcp->arc_count = count;
arcp->arc_order = order;
arcp->arc_childlist = parentp->children;
parentp->children = arcp;
arcp->arc_parentlist = childp->parents;
childp->parents = arcp;
}
static nltype **topsortnlp = NULL;
static
int
topcmp(
nltype **npp1,
nltype **npp2)
{
return((*npp1)->toporder - (*npp2)->toporder);
}
nltype **
doarcs(
void)
{
nltype *parentp, **timesortnlp;
arctype *arcp;
long index;
for(parentp = nl; parentp < npe; parentp++){
parentp->childtime = 0.0;
arcp = arclookup(parentp, parentp);
if(arcp != NULL){
parentp->ncall -= arcp->arc_count;
parentp->selfcalls = arcp->arc_count;
}
else{
parentp->selfcalls = 0;
}
parentp->propfraction = 0.0;
parentp->propself = 0.0;
parentp->propchild = 0.0;
parentp->printflag = FALSE;
parentp->toporder = DFN_NAN;
parentp->cycleno = 0;
parentp->cyclehead = parentp;
parentp->cnext = 0;
}
for(parentp = nl; parentp < npe; parentp++){
if(parentp->toporder == DFN_NAN){
dfn(parentp);
}
}
cyclelink();
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 *),
(int (*)(const void *, const void *))topcmp);
#ifdef DEBUG
if(debug & DFNDEBUG){
printf( "[doarcs] topological sort listing\n");
for(index = 0; index < nname; index += 1){
printf("[doarcs] ");
printf("%d:", topsortnlp[index]->toporder);
printname(topsortnlp[index]);
printf("\n");
}
}
#endif
doflags();
dotime();
timesortnlp = (nltype **)calloc(nname + ncycle, sizeof(nltype *));
if(timesortnlp == NULL)
fatal("ran out of memory for sorting");
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 *),
(int (*)(const void *, const void *))totalcmp);
for(index = 0; index < nname + ncycle; index++){
timesortnlp[index]->index = index + 1;
}
return(timesortnlp);
}
static
void
dotime(
void)
{
int index;
cycletime();
for(index = 0; index < nname; index += 1){
timepropagate(topsortnlp[index]);
}
}
static
void
timepropagate(
nltype *parentp)
{
arctype *arcp;
nltype *childp;
double share;
double propshare;
if(parentp->propfraction == 0.0){
return;
}
for(arcp = parentp->children; arcp; arcp = arcp->arc_childlist){
childp = arcp->arc_childp;
if(arcp->arc_count == 0){
continue;
}
if(childp == parentp){
continue;
}
if(childp->propfraction == 0.0){
continue;
}
if(childp->cyclehead != childp){
if(parentp->cycleno == childp->cycleno){
continue;
}
if(parentp->toporder <= childp->toporder){
fprintf(stderr, "[propagate] toporder botches\n");
}
childp = childp->cyclehead;
}
else{
if(parentp->toporder <= childp->toporder){
fprintf(stderr, "[propagate] toporder botches\n");
continue;
}
}
if(childp->ncall == 0){
continue;
}
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;
propshare = parentp->propfraction * share;
parentp->propchild += propshare;
arcp->arc_time *= parentp->propfraction;
arcp->arc_childtime *= parentp->propfraction;
if(parentp->cyclehead != parentp){
parentp->cyclehead->childtime += share;
parentp->cyclehead->propchild += propshare;
}
#ifdef DEBUG
if(debug & PROPDEBUG){
printf("[dotime] child \t");
printname(childp);
printf(" with %f %f %ld/%ld\n",
childp->time, childp->childtime,
arcp->arc_count, childp->ncall);
printf("[dotime] parent\t");
printname(parentp);
printf("\n[dotime] share %f\n", share);
}
#endif
}
}
static
void
cyclelink(
void)
{
nltype *nlp;
nltype *cyclenlp;
int cycle;
nltype *memberp;
arctype *arcp;
ncycle = 0;
for(nlp = nl; nlp < npe; nlp++){
if(nlp->cyclehead == nlp && nlp->cnext != 0){
ncycle += 1;
}
}
cyclenl = (nltype *)calloc(ncycle + 1, sizeof(nltype));
if(cyclenl == NULL)
fatal("no room for %lu bytes of cycle headers",
(ncycle + 1) * sizeof(nltype));
cycle = 0;
for(nlp = nl; nlp < npe; nlp++){
if(!(nlp->cyclehead == nlp && nlp->cnext != 0)){
continue;
}
cycle += 1;
cyclenlp = &cyclenl[cycle];
cyclenlp->name = 0;
cyclenlp->value = 0;
cyclenlp->time = 0.0;
cyclenlp->childtime = 0.0;
cyclenlp->ncall = 0;
cyclenlp->selfcalls = 0;
cyclenlp->propfraction = 0.0;
cyclenlp->propself = 0.0;
cyclenlp->propchild = 0.0;
cyclenlp->printflag = TRUE;
cyclenlp->index = 0;
cyclenlp->toporder = DFN_NAN;
cyclenlp->cycleno = cycle;
cyclenlp->cyclehead = cyclenlp;
cyclenlp->cnext = nlp;
cyclenlp->parents = 0;
cyclenlp->children = 0;
#ifdef DEBUG
if(debug & CYCLEDEBUG){
printf("[cyclelink] ");
printname(nlp);
printf(" is the head of cycle %d\n", cycle);
}
#endif
for(memberp = nlp; memberp; memberp = memberp->cnext){
memberp->cycleno = cycle;
memberp->cyclehead = cyclenlp;
}
for(memberp = nlp; memberp; memberp = memberp->cnext){
for(arcp = memberp->parents; arcp; arcp = arcp->arc_parentlist){
if(arcp->arc_parentp == memberp){
continue;
}
if(arcp->arc_parentp->cycleno == cycle){
cyclenlp->selfcalls += arcp->arc_count;
}
else{
cyclenlp->ncall += arcp->arc_count;
}
}
}
}
}
static
void
cycletime(
void)
{
int cycle;
nltype *cyclenlp;
nltype *childp;
for(cycle = 1; cycle <= ncycle; cycle += 1){
cyclenlp = &cyclenl[cycle];
for(childp = cyclenlp->cnext; childp; childp = childp->cnext){
if(childp->propfraction == 0.0){
continue;
}
cyclenlp->time += childp->time;
}
cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time;
}
}
static
void
doflags(
void)
{
int index;
nltype *childp;
nltype *oldhead;
oldhead = 0;
for(index = nname-1; index >= 0; index -= 1){
childp = topsortnlp[index];
if(childp->cyclehead != oldhead){
oldhead = childp->cyclehead;
inheritflags(childp);
}
#ifdef DEBUG
if(debug & PROPDEBUG){
printf("[doflags] ");
printname(childp);
printf(" inherits printflag %d and propfraction %f\n",
childp->printflag, childp->propfraction);
}
#endif
if(!childp->printflag){
if(onlist(flist, childp->name) ||
(!fflag && !onlist(elist, childp->name))){
childp->printflag = TRUE;
}
}
else{
if((!onlist(flist, childp->name)) &&
onlist(elist, childp->name)){
childp->printflag = FALSE;
}
}
if(childp->propfraction == 0.0){
if(onlist(Flist, childp->name) ||
(!Fflag && !onlist(Elist, childp->name))){
childp->propfraction = 1.0;
}
}
else{
if(!onlist(Flist, childp->name) &&
onlist(Elist, childp->name)){
childp->propfraction = 0.0;
}
}
childp->propself = childp->time * childp->propfraction;
printtime += childp->propself;
#ifdef DEBUG
if(debug & PROPDEBUG){
printf("[doflags] ");
printname(childp);
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);
}
#endif
}
}
static
void
inheritflags(
nltype *childp)
{
nltype *headp;
arctype *arcp;
nltype *parentp;
nltype *memp;
headp = childp->cyclehead;
if(childp == headp){
childp->printflag = FALSE;
childp->propfraction = 0.0;
for(arcp = childp->parents; arcp ; arcp = arcp->arc_parentlist){
parentp = arcp->arc_parentp;
if(childp == parentp){
continue;
}
childp->printflag |= parentp->printflag;
if(childp->ncall){
childp->propfraction += parentp->propfraction *
(((double)arcp->arc_count) /
((double)childp->ncall));
}
}
}
else{
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){
continue;
}
parentp = arcp->arc_parentp;
headp->printflag |= parentp->printflag;
if(headp->ncall){
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;
}
}
}