/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */

/*****************************************************************
 * timing.c
 *
 * $Author: blythe $
 * $Date: 2002/05/29 01:09:10 $
 ****************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <math.h>
#include <setjmp.h>
#include <ctype.h>
#include <assert.h>

#include "cpu_interface.h"
#include "statrecord.h"
#include "statistics.h"
#include "simutil.h"
#include "sim_error.h"
#include "tcl_init.h"
#include "stack.h"

#define CPUMASK     uint

#define CPUNum ((CPUVec.CurrentCpuNum) ? CPUVec.CurrentCpuNum() : 0)

/*
#define TIMING_DEBUG
*/

typedef struct TimingTree  TimingTree;
typedef struct TimingThread TimingThread;
typedef struct TimingNode   TimingNode;

struct TimingThread {
   char   *name;
   Stack  *stack;
   uint64 compStart;
   char   active;
};

struct TimingTree {
   char *name;
   uint numThreads;
   Tcl_HashTable threads;
   TimingThread  *currentThread[SIM_MAXCPUS];
   StatRecordSwitch *selector;
   TimingNode *root;
};

struct TimingNode {
   char       *name;
   Stats      *stats;
   TimingNode *child;
   TimingNode *sibling;
   StatRecordBucket *bucket;  
   char       mutable;
};


static int CmdCreate(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdExit(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdDump(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdSwitch(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdTerminate(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdStart(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdVector(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdEnd(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdCurrent(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdStackList(Tcl_Interp *interp, int argc, char *argv[]);
static int CmdFields(Tcl_Interp *interp, int argc, char *argv[]);


static TimingTree *TreeCreate(char *TreeName);
static TimingTree *TreeLookup(char *treeName);
static void TreeDump(TimingTree *tree);

static TimingThread *ThreadCreate(TimingTree *tree, char *threadName,
                                  char *startStates[], int numStartStates);
static TimingThread *ThreadLookup(TimingTree *tree, char *threadName);
static void ThreadExit(TimingTree *tree, TimingThread *thread);
static int ThreadStartPhase(TimingTree *tree, TimingThread *thread, char *phaseName,
                            int mutable);
static void ThreadEndPhase(TimingTree *tree, TimingThread *thread, char *phaseName);

static void TimingStackList(Stack *stack);


static TimingNode *NodeCreate(char *name);
static TimingNode *NodeFind(TimingNode *parent, char *name);
static void NodeZip(TimingTree *tree, TimingNode *src, TimingNode *dest);
static void OverflowDebug(Tcl_Interp *interp, TimingThread *thread);


static Tcl_HashTable trees;

static tclcmd timingCmds[] = {
{   "create",     3, CmdCreate,      " create treeName"},
{   "exit",       3, CmdExit,        " exit treeName"},
{   "dump",       3, CmdDump,        " dump treeName"},
{   "switch",    -1, CmdSwitch,      " switch treeName threadName ?phase ...?"},
{   "terminate",  4, CmdTerminate,   " terminate treeName threadName"},
{   "start",     -1, CmdStart,       " start treeName phaseName ?threadName?"},
{   "start?",    -1, CmdStart,       " start? treeName phaseName ?threadName?"},
{   "vector",    -1, CmdVector,      " vector treeName phaseName ?threadName?"},
{   "end",       -1, CmdEnd,         " end treeName phaseName ?threadName?"},
{   "current",   -1, CmdCurrent,     " current treeName ?threadName?"},
{   "dumpstack", -1, CmdStackList,   " dumpstack treeName ?threadName?"},
{   "fields",     2, CmdFields,      " fields"},
{   NULL,         0, NULL,           NULL}
};

/****************************************************************
 * TimingInit
 ****************************************************************/
void 
TimingInit(Tcl_Interp *interp)
{
   Tcl_InitHashTable(&trees, TCL_STRING_KEYS);

   Tcl_CreateCommand(interp, "timing", DispatchCmd, (ClientData)timingCmds, 
                     NULL);
}

/*****************************************************************
 * CmdCreate
 *
 * Create a new timing tree. This will be the level at which you 
 * limit timing to certain pid's.
 ****************************************************************/
static int 
CmdCreate(Tcl_Interp *interp, int argc, char *argv[])
{
   char *treeName = argv[2];
   
   if (TreeCreate(treeName) == NULL) {
      Tcl_AppendResult(interp, "tree name already taken \"",
                       treeName, "\"", NULL);
      return TCL_ERROR;
   }
   return TCL_OK;
}

/*****************************************************************
 * CmdExit
 *
 * Assorted cleanup routines to get all of the timing stuff in order
 * before printing. 
 *****************************************************************/
static int 
CmdExit(Tcl_Interp *interp, int argc, char *argv[])
{
   Tcl_HashEntry *entry;
   Tcl_HashSearch search;
   TimingTree  *tree;
   char *treeName;
   
   treeName  = argv[2];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   for (entry = Tcl_FirstHashEntry(&tree->threads, &search); entry;
        entry = Tcl_NextHashEntry(&search)) {
      ThreadExit(tree, (TimingThread *)Tcl_GetHashValue(entry));
   }
   
   return TCL_OK;
}

/*****************************************************************
 * CmdStart
 *
 * Entry point to a new phase... add it if it doesn't exist yet.
 * This is a "push".
 ****************************************************************/
static int 
CmdStart(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   char *treeName;
   char *phaseName;
   
   if ((argc != 4) && (argc != 5)) {
      Tcl_AppendResult(interp, "wrong number of arguments", NULL);
      return TCL_ERROR;
   }
   
   treeName = argv[2];
   phaseName = argv[3];

   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   if (argc == 5) {
      thread = ThreadLookup(tree, argv[4]);
      if (!thread) {
         CPUWarning("TIMING: no thread named %s\n", argv[4]);
         return TCL_OK;
      }

   } else {
      thread = tree->currentThread[CPUNum];
      if (!thread) {
         Tcl_AppendResult(interp, "no current thread in \"", treeName, "\"", NULL);
         return TCL_ERROR;
      }
   }

   if (StackEmpty(thread->stack)) {
      Tcl_AppendResult(interp, "cannot start phase on terminated thread", NULL);
      return TCL_ERROR;
   }
   
   if (thread->active) {
      if (ThreadStartPhase(tree, thread, phaseName, argv[1][5]) != TCL_OK) {
	 OverflowDebug(interp, thread);
         return TCL_ERROR;
      }
      
   } else {
      ThreadEndPhase(tree, thread, "DESCHED");

      if (ThreadStartPhase(tree, thread, phaseName, argv[1][5]) != TCL_OK) {
         OverflowDebug(interp, thread);
         return TCL_ERROR;
      }
      
      if (ThreadStartPhase(tree, thread, "DESCHED", 0) != TCL_OK) {
         OverflowDebug(interp, thread);
         return TCL_ERROR;
      }
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Start thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif

   return TCL_OK;
}

/*****************************************************************
 * CmdVector
 ****************************************************************/
static int 
CmdVector(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   TimingNode *node;
   char *treeName;
   char *phaseName;
   
   if ((argc != 4) && (argc != 5)) {
      Tcl_AppendResult(interp, "wrong number of arguments", NULL);
      return TCL_ERROR;
   }
   
   treeName = argv[2];
   phaseName = argv[3];

   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   if (argc == 5) {
      thread = ThreadLookup(tree, argv[4]);
      if (!thread) {
         CPUWarning("TIMING: no thread named %s\n", argv[4]);
         return TCL_OK;
      }

   } else {
      thread = tree->currentThread[CPUNum];
      if (!thread) {
         Tcl_AppendResult(interp, "no current thread in \"", treeName, "\"", NULL);
         return TCL_ERROR;
      }
   }

   if (StackEmpty(thread->stack)) {
      Tcl_AppendResult(interp, "cannot vector phase on terminated thread", NULL);
      return TCL_ERROR;
   }
   
   if (thread->active) {
      node = UINT64_TO_PTR(StackIndex(thread->stack, 2));
   } else {
      node = UINT64_TO_PTR(StackIndex(thread->stack, 5));
   }
   
   ASSERT(node);

   if (!node->mutable) {
      CPUWarning("TIMING: CPU %d CYCLE %lld: node not mutable, tree: %s, node: %s\n", 
                 CPUNum, CPUVec.CycleCount(CPUNum), treeName, node->name);
      TimingStackList(thread->stack);
      return TCL_OK;
   }

   ASSERT(!node->sibling);
   
   free(node->name);
   node->name = SaveString(phaseName);

   return TCL_OK;
}

/*****************************************************************
 * CmdEnd
 *
 * End of an existing phase. Print a warning if this ending phase
 * doesn't match the top of the stack.
 ****************************************************************/
static int 
CmdEnd(Tcl_Interp *interp, int argc, char *argv[])
{
   char *treeName;
   char *phaseName;
   TimingTree *tree;
   TimingThread *thread;
   
   if ((argc != 4) && (argc != 5)) {
      Tcl_AppendResult(interp, "wrong number of arguments", NULL);
      return TCL_ERROR;
   }
   
   treeName  = argv[2];
   phaseName = argv[3];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   if (argc == 5) {
      thread = ThreadLookup(tree, argv[4]);
      if (!thread) {
         CPUWarning("TIMING: no thread named %s\n", argv[4]);
         return TCL_OK;
      }

   } else {
      thread = tree->currentThread[CPUNum];
      if (!thread) {
         Tcl_AppendResult(interp, "no current thread in \"", treeName, "\"", NULL);
         return TCL_ERROR;
      }
   }

   if (StackEmpty(thread->stack)) {
      Tcl_AppendResult(interp, "cannot end phase on terminated thread", NULL);
      return TCL_ERROR;
   }
   
   if (thread->active) {
      ThreadEndPhase(tree, thread, phaseName);
      
   } else {
      ThreadEndPhase(tree, thread, "DESCHED");
      ThreadEndPhase(tree, thread, phaseName);
      ThreadStartPhase(tree, thread, "DESCHED", 0);
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: End thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif

   return TCL_OK;
}


/*****************************************************************
 * CmdCurrent
 *
 * Return the top phase on the stack
 ****************************************************************/
static int
CmdCurrent(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   TimingNode *node;
   char *treeName;

   if (argc !=3 && argc !=4) { 
      Tcl_AppendResult(interp,"wrong number of arguments",NULL);
      return TCL_ERROR;
   }

   treeName  = argv[2];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   if (argc == 4) {
      if (!(thread = ThreadLookup(tree, argv[3]))) {
         Tcl_AppendResult(interp, "no thread named \"", argv[3], "\"", NULL);
         return TCL_ERROR;
      }

   } else {
      if (!(thread = tree->currentThread[CPUNum])) {
         Tcl_AppendResult(interp, "no current thread", NULL);
         return TCL_ERROR;
      }
      ASSERT(thread->active);
   }

   if (StackEmpty(thread->stack)) {
      Tcl_AppendResult(interp, "cannot get current phase on terminated thread", NULL);
      return TCL_ERROR;
   }

   
   if (thread->active) {
      node = UINT64_TO_PTR(StackIndex(thread->stack, 2));
   } else {
      node = UINT64_TO_PTR(StackIndex(thread->stack, 5));
   }
   
   if (node) {
      ASSERT(node->name);
      Tcl_AppendResult(interp, node->name, NULL);
   } else {
      Tcl_AppendResult(interp, "", NULL);
   }
   
   return TCL_OK;
}


/*****************************************************************
 * CmdStackList
 *
 * Access from TCL to stacklist debugging command
 ****************************************************************/
static int
CmdStackList(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   char *treeName;

   if (argc !=3 && argc !=4) { 
      Tcl_AppendResult(interp,"wrong number of arguments",NULL);
      return TCL_ERROR;
   }

   treeName  = argv[2];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   if (argc == 4) {
      if (!(thread = ThreadLookup(tree, argv[3]))) {
         Tcl_AppendResult(interp, "no thread named \"", argv[3], "\"", NULL);
         return TCL_ERROR;
      }

   } else {
      if (!(thread = tree->currentThread[CPUNum])) {
         Tcl_AppendResult(interp, "no current thread", NULL);
         return TCL_ERROR;
      }
   }

   TimingStackList(thread->stack);
   return TCL_OK;
}


/*****************************************************************
 * CmdSwitch
 *
 * Move to another thread... create a stack for it if it doesn't
 * exist. 
 ****************************************************************/
static int 
CmdSwitch(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   char *treeName;
   char *threadName;
   char **startState;
   int  numStartStates;
   
   if ((argc < 4)) {
      Tcl_AppendResult(interp, "wrong # args: should be \"",
                       argv[0], timingCmds[3].usage, "\"", NULL);
      return TCL_ERROR;
   }

   treeName  = argv[2];
   threadName = argv[3];
   startState = &(argv[4]);
   numStartStates = argc - 4;

   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   /* First, if this thread has not yet exited, then push DESCHED */
   thread = tree->currentThread[CPUNum];
   if (thread && !StackEmpty(thread->stack)) {
      if (ThreadStartPhase(tree, thread, "DESCHED", 0) != TCL_OK) {
         OverflowDebug(interp, thread);
         return TCL_ERROR;
      }
   }

   if (thread) {
      thread->active = 0;
   }
   
   /* See if a stack for new thread exists... if not, create one */
   thread = ThreadLookup(tree, threadName);
   if (!thread) {
      thread = ThreadCreate(tree, threadName, startState, numStartStates);
      CPUPrint("TIMING: CPUNum %d created thread %s\n", CPUNum, threadName); 
   } else {
      ASSERT(!thread->active);
      /* If we switch back to an existing thread, it should have been
         in the desched state */
      ThreadEndPhase(tree, thread, "DESCHED");
   }

   thread->active = 1;
   tree->currentThread[CPUNum] = thread;

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Switch to thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif

   return TCL_OK;
}

/*****************************************************************
 * CmdTerminate
 *
 * Thread is finished, cleanup its stack.
 ****************************************************************/
static int 
CmdTerminate(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   char *treeName;
   char *threadName;
   
   treeName  = argv[2];
   threadName = argv[3];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }
   
   thread = tree->currentThread[CPUNum];

   if (strcmp(thread->name, threadName)) {
      Tcl_AppendResult(interp, "\"", threadName, "\" is not current thread", NULL);
      return TCL_ERROR;
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Exit thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif
   
   ThreadExit(tree, tree->currentThread[CPUNum]);

   return TCL_OK;
}

/*****************************************************************
 * CmdDump
 *****************************************************************/
static int 
CmdDump(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree  *tree;
   char *treeName;

   if ((argc != 3)) {
      Tcl_AppendResult(interp, "wrong # args: should be \"",
                       argv[0], timingCmds[5].usage, "\"", NULL);
      return TCL_ERROR;
   }

   treeName  = argv[2];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   TreeDump(tree);

   return TCL_OK;
}

/*****************************************************************
 * CmdFields
 *****************************************************************/
static int 
CmdFields(Tcl_Interp *interp, int argc, char *argv[])
{

   if ((argc != 2)) {
      Tcl_AppendResult(interp, "wrong # args: should be \"",
                       argv[0], timingCmds[8].usage, "\"", NULL);
      return TCL_ERROR;
   }

   Tcl_AppendResult(TCLInterp,"TIMING: ", NULL);
   StatRecordDumpFields();

   return TCL_OK;
}

/****************************************************************
 * TreeCreate 
 *
 ****************************************************************/
TimingTree *
TreeCreate(char *treeName)
{
   TimingTree *tree;
   TimingNode *node;
   int new = 0;
   Tcl_HashEntry *entry = Tcl_CreateHashEntry(&trees, treeName, &new);
   char rootName[24];
   
   if (!new) {
      return NULL;
   }

   tree = (TimingTree *)ZMALLOC(sizeof(TimingTree),"TimingTree");

   Tcl_InitHashTable(&(tree->threads), TCL_STRING_KEYS);

   tree->name = Tcl_GetHashKey(&trees, entry);
   tree->numThreads = 0;
   tree->currentThread[0] = NULL;
   tree->selector = StatRecordNewSwitch("timing");

   CPUPrint("TIMING: new tree %s\n", treeName);
#ifdef notdef
   CPUPrint("TIMING: ");
   StatRecordDumpFields();
#endif
   
   sprintf(rootName, "ROOT");

   node = NodeFind(NULL, rootName);
   tree->root = node;

   Tcl_SetHashValue(entry, tree);

   return tree;
}

/*****************************************************************
 * TreeLookup
 *
 *****************************************************************/
TimingTree *
TreeLookup(char *treeName)
{
   TimingTree *tree = NULL;
   Tcl_HashEntry *entry = Tcl_FindHashEntry(&trees, treeName);
   
   if (entry) {
      tree = Tcl_GetHashValue(entry);
      ASSERT(tree);
   }
   return tree;
}

/*****************************************************************
 * TreeDump
 *****************************************************************/
static void DumpTree(char *name, TimingNode *node, char *parentName, 
                     int depth);

static void
TreeDump(TimingTree *tree)
{
   ASSERT(tree != NULL);
   ASSERT(tree->root);
   DumpTree(tree->name, tree->root, tree->root->name, 0);
   Tcl_AppendResult(TCLInterp, "TIMING: tree ", tree->name, " END\n", NULL);
}

static void
DumpTree(char *name, TimingNode *node, char *parentName, int depth)
{
   char buf[32];
   if (!node)  return;

   sprintf(buf,"%d",depth);
   Tcl_AppendResult(TCLInterp, "TIMING: tree ",name," depth ", buf, 
                    " name ", node->name, " parent ", parentName, " ", NULL);
   StatsList(node->stats, "TIMING: ");
   StatRecordDumpBucket(node->name, node->bucket, "TIMING: ");

   DumpTree(name, node->child, node->name, depth+1);
   DumpTree(name, node->sibling, parentName, depth);
}


/*****************************************************************
 * ThreadCreate
 *
 *****************************************************************/
TimingThread *
ThreadCreate(TimingTree *tree, char *threadName, char **startStates,
             int numStartStates)
{
   TimingThread *thread;
   TimingNode *node, *node2;
   int i;
   int new = 0;

   Tcl_HashEntry *entry = Tcl_CreateHashEntry(&(tree->threads), 
                                              threadName, &new);
   ASSERT(new);

   thread = (TimingThread *)ZMALLOC(sizeof(TimingThread),"TimingThread");

   ASSERT(thread);

   thread->name  = Tcl_GetHashKey(&(tree->threads), entry);
   thread->stack = StackInit();

   StackPush(thread->stack, PTR_TO_UINT64(tree->root));
   StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum));
   StackPush(thread->stack, (StackItem)0);

   node = tree->root;
   for (i=0; i<numStartStates; i++) {
      node2 = NodeFind(node, startStates[i]);
      ASSERT(node2);
      StackPush(thread->stack, PTR_TO_UINT64(node2));
      StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum));
      StackPush(thread->stack, (StackItem)0);
      node = node2;
   }

   thread->compStart = CPUVec.CycleCount(CPUNum);
   thread->active = 1;
   
   Tcl_SetHashValue(entry, thread);

   StatRecordSetSwitch(tree->selector, CPUNum, node->bucket);
   thread->compStart = CPUVec.CycleCount(CPUNum);

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Create %s thread %s\n", tree->name, threadName); 
   for (i=numStartStates-1; i>=0; i--) {
      CPUPrint("\t[%d] %s\n", i, startStates[i]);
   }
#endif
   
   return thread;
}

/*****************************************************************
 * ThreadLookup
 *****************************************************************/
TimingThread *
ThreadLookup(TimingTree *tree, char *threadName)
{
   TimingThread *thread = NULL;
   Tcl_HashEntry *entry = Tcl_FindHashEntry(&(tree->threads), threadName);
   
   if (entry) {
      thread = Tcl_GetHashValue(entry);
   } else {
      thread = NULL;
   }
   
   return thread;
}

/*****************************************************************
 * ThreadExit
 *****************************************************************/
static void
ThreadExit(TimingTree *tree, TimingThread *thread)
{  
   TimingNode *node = NULL;
   TimingNode *next = NULL;
   uint64 compTotal;
   uint64 compTime;   
   uint64 startTime;
   
   ASSERT(thread != NULL);

   if (!StackEmpty(thread->stack)) {
      if (thread->compStart) {
         compTime = (uint64)StackPop(thread->stack);
         StackPush(thread->stack,
                   (StackItem)(compTime + (CPUVec.CycleCount(CPUNum)
                                           - thread->compStart)));
      }      
      
      while (!StackEmpty(thread->stack)) {
         compTotal = (uint64)StackPop(thread->stack);
         startTime = (uint64)StackPop(thread->stack);
         node =  UINT64_TO_PTR(StackPop(thread->stack));
         StatsEntry(node->stats, CPUVec.CycleCount(CPUNum) - startTime, compTotal);
         if (node->mutable) {
            ASSERT(!node->sibling);
            next = UINT64_TO_PTR(StackIndex(thread->stack, 2));
            ASSERT(next);
            NodeZip(tree, node, NodeFind(next, node->name));
         }
      }
      
      ASSERT(!node || !strncmp(node->name, "ROOT", 4));
   }
}

/*****************************************************************
 * ThreadStartPhase
 *****************************************************************/
static int
ThreadStartPhase(TimingTree *tree, TimingThread *thread, char *phaseName, int mutable)
{
   TimingNode *parent;
   TimingNode *node;
   uint64 compTime;

   parent = UINT64_TO_PTR(StackIndex(thread->stack, 2));
   ASSERT(parent);
   
   compTime = (uint64)StackPop(thread->stack);
   StackPush(thread->stack, (StackItem)(compTime + (CPUVec.CycleCount(CPUNum)
                                       - thread->compStart)));

   if (mutable) {
      node = NodeCreate(phaseName);
      node->sibling = NULL;
      node->mutable = 1;
   } else {
      node = NodeFind(parent, phaseName);
      ASSERT(!node->mutable);
   }
   
   /* node for node */
   if (StackPush(thread->stack, PTR_TO_UINT64(node))) {
      return TCL_ERROR;
   }
   
   /* cycle count for latency */
   if (StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum))) {
      (void) StackPop(thread->stack);
      return TCL_ERROR;
   }
   
   /* sum for computation */
   if (StackPush(thread->stack, (StackItem)0)) {
      (void) StackPop(thread->stack);
      (void) StackPop(thread->stack);
      return TCL_ERROR;
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Start %s on thread %s at %lld %#llx\n", 
            node->name, thread->name, CPUVec.CycleCount(CPUNum),
            CPUVec.CurrentPC(CPUNum));
   TimingStackList(thread->stack);
#endif

   StatRecordSetSwitch(tree->selector, CPUNum, node->bucket);
   thread->compStart = CPUVec.CycleCount(CPUNum);
   
   return TCL_OK;
}

/*****************************************************************
 * ThreadEndPhase
 *****************************************************************/
static void
ThreadEndPhase(TimingTree *tree, TimingThread *thread, char *phaseName)
{
   TimingNode *node;
   TimingNode *next;
   uint64 comp;
   uint64 compTotal;
   uint64 latTotal;

   node =  UINT64_TO_PTR(StackIndex(thread->stack, 2));
   ASSERT(node);

   if (strcmp(phaseName, node->name)) {
      CPUWarning("TIMING: %d tree %s thread %s ending \"%s\" but in \"%\"\n",
                 CPUNum, tree->name, thread->name, phaseName, node->name);
      TimingStackList(thread->stack);
      return;
   }

   comp = (CPUVec.CycleCount(CPUNum) - thread->compStart);
   /* on embra we have the problem the cycle count may go backwards */
   comp = ((int64)comp > 0) ? comp : 0;
   compTotal = (uint64)StackPop(thread->stack) + comp;

   latTotal = CPUVec.CycleCount(CPUNum) - (uint64)StackPop(thread->stack);
   /* on embra we have the problem the cycle count may go backwards */
   latTotal = ((int64)latTotal > 0) ? latTotal : 0;
   
   node = UINT64_TO_PTR(StackPop(thread->stack));
   ASSERT(node);

   StatsEntry(node->stats, latTotal, compTotal);

   next = UINT64_TO_PTR(StackIndex(thread->stack, 2));

   if (!next) {
      CPUError("TIMING: CPU %d: Popping ROOT???\n", CPUNum);  
   }

   if (node->mutable) {
      ASSERT(!node->sibling);
      NodeZip(tree, node, NodeFind(next, node->name));
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: End %s on thread %s at %lld %#llx\n", 
            node->name, thread->name, CPUVec.CycleCount(CPUNum),
            CPUVec.CurrentPC(CPUNum));
   TimingStackList(thread->stack);
#endif

   StatRecordSetSwitch(tree->selector, CPUNum, next->bucket); 
   thread->compStart = CPUVec.CycleCount(CPUNum);
}

/*****************************************************************
 * NodeCreate
 *****************************************************************/
static TimingNode *
NodeCreate(char *name)
{
   TimingNode *n;

   n = (TimingNode *)ZMALLOC(sizeof(TimingNode),"TimingNode");

   n->name = SaveString(name);
   n->bucket = StatRecordNewBucket();
   n->stats = StatsCreate(0, 0, 0); 
   n->child = NULL;
   n->sibling = NULL;
   n->mutable = 0;
   
   return n;
}

/*****************************************************************
 * NodeFind
 *****************************************************************/
static TimingNode *
NodeFind(TimingNode *parent, char *name)
{
   TimingNode *n;
   
   if (!parent) {
      return NodeCreate(name);
   }

   n = parent->child;
   
   while (n) {
      if (!strcmp(n->name, name)) {
         return n;
      } else {
         n = n->sibling;
      }
   }
   
   n =  NodeCreate(name);
   n->sibling = parent->child;
   parent->child = n;

   return n;
}

/*****************************************************************
 * NodeFind
 *****************************************************************/
static void
NodeZip(TimingTree *tree, TimingNode *src, TimingNode *dest)
{
   TimingNode *child;
   TimingNode *kill;
   
   ASSERT(src);
   ASSERT(dest);

   StatRecordTransferBucket(tree->selector, src->bucket, dest->bucket);
   StatsTransfer(src->stats, dest->stats);
   
   child = src->child;
   while (child) {
      kill = child;
      child = child->sibling;
      NodeZip(tree, kill, NodeFind(dest, kill->name));
   }

   free(src->name);
   StatRecordFreeBucket(src->bucket);
   StatsDestroy(src->stats);
   free(src);
}

/*****************************************************************
 * TimingStackList - Helpful debugging routine
 *****************************************************************/
void
TimingStackList(Stack *stack) 
{
   TimingNode *node;
   int i = stack->head;
   int j;

   while (i >= 0) {
      node =  UINT64_TO_PTR((stack->element[i-2]));
      j = (int)stack->element[i-1];
      CPUPrint("\t[%2d] = %12s started at %12d", i/3, node->name, j);
      if (node->mutable) {
         CPUPrint(" mutable");
      }
      CPUPrint("\n");
      i -= 3;
   }
}

/*****************************************************************
 * Stack overflow -- print history of nodes for debugging
 *****************************************************************/

static void
OverflowDebug(Tcl_Interp *interp, TimingThread *thread)
{
  int i;

  Tcl_AppendResult(interp, "stack overflow for ", thread->name, ":", NULL);
  for (i = 2; ; i += 3) {
    TimingNode *node = (TimingNode*) StackIndex(thread->stack, i);
    if (!node) break;
    Tcl_AppendResult(interp, " ", node->name, NULL);
  }
}