/*
 * 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);
}