/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include	<stdlib.h>
#include	"gprof.h"

double	printtime;
sztype	total_names;
int	ncycle;
nltype	*cyclenl;

/*
 *	add (or just increment) an arc
 */
void
addarc(nltype *parentp, nltype *childp, actype count)
{
	arctype		*arcp;

#ifdef DEBUG
	if (debug & TALLYDEBUG) {
		(void) printf("[addarc] %lld arcs from %s to %s\n",
		    count, parentp->name, childp->name);
	}
#endif /* DEBUG */
	arcp = arclookup(parentp, childp);
	if (arcp != 0) {
		/*
		 *	a hit:  just increment the count.
		 */
#ifdef DEBUG
		if (!Dflag) {
			if (debug & TALLYDEBUG) {
				(void) printf("[tally] hit %lld += %lld\n",
				    arcp->arc_count, count);
			}
		} else {
			if (debug & TALLYDEBUG) {
				(void) printf("[tally] hit %lld -= %lld\n",
				    arcp->arc_count, count);
			}
		}

#endif /* DEBUG */
		if (!Dflag)
			arcp->arc_count += count;
		else {
			arcp->arc_count -= count;
			if (arcp->arc_count < 0)
				arcp->arc_count = 0;
		}
		return;
	}
	arcp = (arctype *)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
 */
nltype	**topsortnlp;

static int
topcmp(const void *arg1, const void *arg2)
{
	nltype **npp1 = (nltype **)arg1;
	nltype **npp2 = (nltype **)arg2;

	return ((*npp1)->toporder - (*npp2)->toporder);
}

static void
timepropagate(nltype *parentp)
{
	arctype	*arcp;
	nltype	*childp;
	double	share;
	double	propshare;

	if (parentp->propfraction == 0.0) {
		return;
	}
	/*
	 *	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) {
			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) {
				(void) fprintf(stderr,
				    "[propagate] toporder botches\n");
			}
			childp = childp->cyclehead;
		} else {
			if (parentp->toporder <= childp->toporder) {
				(void) fprintf(stderr,
				    "[propagate] toporder botches\n");
				continue;
			}
		}
		if (childp->ncall == 0) {
			continue;
		}
		/*
		 *	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;
		}
#ifdef DEBUG
		if (debug & PROPDEBUG) {
			(void) printf("[dotime] child \t");
			printname(childp);
			(void) printf(" with %f %f %lld/%lld\n",
			    childp->time, childp->childtime,
			    arcp->arc_count, childp->ncall);
			(void) printf("[dotime] parent\t");
			printname(parentp);
			(void) printf("\n[dotime] share %f\n", share);
		}
#endif /* DEBUG */
	}
}


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) {
				/*
				 * all members have the same propfraction
				 * except those that were excluded with -E
				 */
				continue;
			}
			cyclenlp->time += childp->time;
		}
		cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time;
	}
}


static void
dotime(void)
{
	int	index;

	cycletime();
	for (index = 0; index < total_names; index += 1) {
		timepropagate(topsortnlp[index]);
	}
}


static void
cyclelink(void)
{
	nltype	*nlp;
	nltype	*cyclenlp;
	int		cycle;
	nltype		*memberp;
	arctype		*arcp;
	mod_info_t	*mi;

	/*
	 *	Count the number of cycles, and initialize the cycle lists
	 */
	ncycle = 0;
	for (mi = &modules; mi; mi = mi->next) {
		for (nlp = mi->nl; nlp < mi->npe; nlp++) {
			/*
			 *	this is how you find unattached cycles
			 */
			if (nlp->cyclehead == nlp && nlp->cnext != 0) {
				ncycle += 1;
			}
		}
	}

	/*
	 *	cyclenl is indexed by cycle number:
	 *	i.e. it is origin 1, not origin 0.
	 */
	cyclenl = (nltype *) calloc(ncycle + 1, sizeof (nltype));
	if (cyclenl == 0) {
		(void) fprintf(stderr,
		    "%s: No room for %d bytes of cycle headers\n",
		    whoami, (ncycle + 1) * sizeof (nltype));
		done();
	}

	/*
	 *	now link cycles to true cycleheads,
	 *	number them, accumulate the data for the cycle
	 */
	cycle = 0;
	for (mi = &modules; mi; mi = mi->next) {
		for (nlp = mi->nl; nlp < mi->npe; nlp++) {
			if (!(nlp->cyclehead == nlp && nlp->cnext != 0)) {
				continue;
			}
			cycle += 1;
			cyclenlp = &cyclenl[cycle];
			cyclenlp->name = 0;		/* the name */
			cyclenlp->value = 0;		/* pc entry point */
			cyclenlp->time = 0.0;		/* ticks in 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 of 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;	/* head of cycle ptr */
			cyclenlp->cnext = nlp;		/* ptr to next member */
							/*	of cycle */
			cyclenlp->parents = 0;		/* caller arcs list */
			cyclenlp->children = 0;		/* callee arcs list */
#ifdef DEBUG
			if (debug & CYCLEDEBUG) {
				(void) printf("[cyclelink] ");
				printname(nlp);
				(void) printf(" is the head of cycle %d\n",
				    cycle);
			}
#endif /* DEBUG */
			/*
			 *	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)
						continue;

					if (arcp->arc_parentp->cycleno ==
					    cycle) {
						cyclenlp->selfcalls +=
						    arcp->arc_count;
					} else {
						cyclenlp->ncall +=
						    arcp->arc_count;
					}
				}
			}
		}
	}
}


/*
 *	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.
 */
static void
inheritflags(nltype *childp)
{
	nltype	*headp;
	arctype	*arcp;
	nltype	*parentp;
	nltype	*memp;

	headp = childp->cyclehead;
	if (childp == headp) {
		/*
		 *	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) {
				continue;
			}
			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.
			 */
			if (childp->ncall) {
				childp->propfraction += parentp->propfraction
				    * (((double)arcp->arc_count)
				    / ((double)childp->ncall));
			}
		}
	} else {
		/*
		 *	its a member of a cycle, look at all parents from
		 *	outside the cycle
		 */
		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 the cycle was never actually called
				 *	(e.g. this arc is static (and all
				 *	others are, too)) no time propagates
				 *	along this arc.
				 */
				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;
		}
	}
}


/*
 * check here if *any* of its parents is printable
 * then return true else return false
 */
static int
check_ancestors(nltype *siblingp)
{
	arctype *parentsp;
	if (!siblingp->parents)
		return (1);
	for (parentsp = siblingp->parents; parentsp;
	    parentsp = parentsp->arc_parentlist) {
		if (parentsp->arc_parentp->printflag)
			return (1);
	}
	return (0);
}


/*
 * check if the parents it passes time are *all* on
 * the Elist in which case we do not pass the time
 */
static int
check_parents(nltype *siblingp)
{
	arctype *parentsp;
	if (!siblingp->parents)
		return (1);
	for (parentsp = siblingp->parents; parentsp;
	    parentsp = parentsp->arc_parentlist) {
		if (!onlist(Elist, parentsp->arc_parentp->name))
			return (1);
	}
	return (0);
}


/*
 *	in one top to bottom pass over the topologically sorted namelist
 *	propagate:
 *		printflag as the union of parents' printflags
 *		propfraction as the sum of fractional parents' propfractions
 *	and while we're here, sum time for functions.
 */
static void
doflags(void)
{
	int	index;
	nltype	*childp;
	nltype	*oldhead;

	oldhead = 0;
	for (index = total_names - 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;
			inheritflags(childp);
		}
#ifdef DEBUG
		if (debug & PROPDEBUG) {
			(void) printf("[doflags] ");
			printname(childp);
			(void) printf(
			    " inherits printflag %d and propfraction %f\n",
			    childp->printflag, childp->propfraction);
		}
#endif /* DEBUG */
		if (!childp->printflag) {
			bool	on_flist;
			/*
			 *	printflag is off
			 *	it gets turned on by
			 *	being on -f list,
			 *	or there not being any -f list
			 *	and not being on -e list.
			 */
			if (((on_flist = onlist(flist, childp->name)) != 0) ||
			    (!fflag && !onlist(elist, childp->name))) {
				if (on_flist || check_ancestors(childp))
					childp->printflag = TRUE;
			}
		} else {
			/*
			 *	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
			 *	its on -F list,
			 *	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;
			}
		} else {
			/*
			 *	it has parents to pass time to,
			 *	but 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)) {
				if (check_parents(childp))
					childp->propfraction = 0.0;
			}
		}
		childp->propself = childp->time * childp->propfraction;
		printtime += childp->propself;
#ifdef DEBUG
		if (debug & PROPDEBUG) {
			(void) printf("[doflags] ");
			printname(childp);
			(void) printf(" ends up with printflag %d and "
			    "propfraction %f\n",
			    childp->printflag, childp->propfraction);
			(void) printf("time %f propself %f printtime %f\n",
			    childp->time, childp->propself, printtime);
		}
#endif /* DEBUG */
	}
}


nltype **
doarcs(void)
{
	nltype	*parentp, **timesortnlp;
	arctype	*arcp;
	long	i, index;

	extern mod_info_t	modules;
	mod_info_t		*mi;

	/*
	 *	initialize various things:
	 *	    zero out child times.
	 *	    count self-recursive calls.
	 *	    indicate that nothing is on cycles.
	 */
	for (mi = &modules; mi; mi = mi->next) {
		for (parentp = mi->nl; parentp < mi->npe; parentp++) {
			parentp->childtime = 0.0;
			arcp = arclookup(parentp, parentp);
			if (arcp != 0) {
				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;

			/*
			 * Inspecting text space is valid only for
			 * the program executable.
			 */
			if (cflag && (mi == &modules)) {
				findcalls(parentp, parentp->value,
				    parentp->value + parentp->sz);
			}
		}
	}

	/*
	 *	topologically order things
	 *	if any node is unnumbered,
	 *	    number it and any of its descendents.
	 */
	for (mi = &modules; mi; mi = mi->next) {
		for (parentp = mi->nl; parentp < mi->npe; parentp++) {
			if (parentp->toporder == DFN_NAN) {
				dfn(parentp);
			}
		}
	}

	/*
	 *	link together nodes on the same cycle
	 */
	cyclelink();
	/*
	 *	Sort the symbol tables in reverse topological order
	 */
	topsortnlp = (nltype **) calloc(total_names, sizeof (nltype *));
	if (topsortnlp == (nltype **) 0) {
		(void) fprintf(stderr,
		    "[doarcs] ran out of memory for topo sorting\n");
	}
	index = 0;
	for (mi = &modules; mi; mi = mi->next) {
		for (i = 0; i < mi->nname; i++)
			topsortnlp[index++] = &(mi->nl[i]);
	}

	qsort(topsortnlp, total_names, sizeof (nltype *), topcmp);
#ifdef DEBUG
	if (debug & DFNDEBUG) {
		(void) printf("[doarcs] topological sort listing\n");
		for (index = 0; index < total_names; index += 1) {
			(void) printf("[doarcs] ");
			(void) printf("%d:", topsortnlp[ index ]->toporder);
			printname(topsortnlp[ index ]);
			(void) printf("\n");
		}
	}
#endif /* DEBUG */
	/*
	 *	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.
	 */
	doflags();
	/*
	 *	starting from the topological bottom,
	 *	propogate children times up to parents.
	 */
	dotime();
	/*
	 *	Now, sort by propself + propchild.
	 *	sorting both the regular function names
	 *	and cycle headers.
	 */
	timesortnlp = (nltype **) calloc(total_names + ncycle,
	    sizeof (nltype *));
	if (timesortnlp == (nltype **) 0) {
		(void) fprintf(stderr,
		    "%s: ran out of memory for sorting\n", whoami);
	}

	index = 0;
	for (mi = &modules; mi; mi = mi->next) {
		for (i = 0; i < mi->nname; i++)
			timesortnlp[index++] = &(mi->nl[i]);
	}

	for (index = 1; index <= ncycle; index++)
		timesortnlp[total_names+index-1] = &cyclenl[index];

	qsort(timesortnlp, total_names + ncycle, sizeof (nltype *), totalcmp);

	for (index = 0; index < total_names + ncycle; index++)
		timesortnlp[index]->index = index + 1;

	return (timesortnlp);
}