/* ***************************************************************************** * * FILE NAME : TREE.C * PROGRAMMER(S) : Robert Arnold * DATE CREATED : February 10, 1994 * * DESCRIPTON : * THE CODE IN THIS FILE WILL BE RESPONSIBLE FOR GENERATING THE CALL * GRAPH TREE STRUCTURE. * ****************************************************************************** */ #include "stats.h" #include "timeds.h" #include "inf.h" #include "tree.h" /* Added by Sibin M on Oct 25, 2004. * Process of cleaning up the TA for C++ */ #include "treedecl.h" #include "timedecl.h" #include "lib.h" /* Added by Sibin M on Oct 25, 2004. * Process of cleaning up the TA for C++ */ #include #include #include extern int memory_count; /***************************************************************************** * * FUNCTION NAME: Build_Timing_Tree * * INPUTS/OUTPUTS: * INPUT - STATS FILE * * ASSUMPTIONS: * STATS FILE: * 1. The file start with a function instance * 2. Each function instance has at least one instruction * 3. The file is structurally correct, no error checking * is provided for this. * 4. Each function instance definition begins with a number * that identifies the definition as a function instance. * (At design time, a "-1"). * 5. Each instruction category defintion is one to a line and * begins with a number that identifies the definition as * an instruction category definition ("0"). * * used to have return type struct tnode*, but didn't return anything * so I'm changing its type to void. 11/28/98 ******************************************************************************* */ void Build_Timing_Tree( struct inf_func_element* inf, string inputfile, struct tnode** timing_tree, struct tnode** main_func ) { struct tnode *func_ptr; /* ptr to each func in the timing tree */ extern bool verbose; /* For each func tnode, move loop insts to correct */ /* loop nodes */ memory_count += sizeof (struct tnode); *timing_tree = (struct tnode *) malloc (sizeof(struct tnode)); /*AMOL:Read the timing file and put them in the structure timing_tree The timing tree is the list of the tnodes(for each function there is a tnode and in each tnode there is an inst_list to keep the inst category*/ *timing_tree = Process_STATS_File(inputfile, inf); *main_func = Locate_Main(*timing_tree); /* Create loop structures for each function in the linked list */ /*AMOL for all the function in timing tree Create the loops the loops are taken from the structure func->inf_ptr->loops i.e. read from the inf file*/ for (func_ptr = *timing_tree; func_ptr && func_ptr->node_type == FNODE; Create_Loops(func_ptr), func_ptr = func_ptr->next); for (func_ptr = *timing_tree; func_ptr && func_ptr->node_type == FNODE; Move_Inst_To_Correct_Loop_Nodes(func_ptr), func_ptr = func_ptr->next); Create_Tree(*timing_tree); if (verbose) { Print_Results(*main_func); } } void Create_Tree( struct tnode* timing_tree ) { struct inst_cat *inst_ptr; struct tnode *child_node; struct tnode *node_ptr; for (node_ptr = timing_tree; node_ptr; node_ptr = node_ptr->next) { for(inst_ptr = node_ptr->instruct_list; inst_ptr; inst_ptr = inst_ptr->next) { if (strcmp(inst_ptr->func, "") != 0) { child_node = Locate_Func_Node(timing_tree, inst_ptr->func, inst_ptr->instance); if (child_node == NULL) { error ("Unable to find func tnode in creating tree"); } Add_Child_Node(node_ptr, child_node); } } } } struct tnode * Locate_Func_Node( struct tnode *root, string node_name, int instance ) { struct tnode *node_ptr = NULL; struct tnode *fnode_ptr = NULL; for (node_ptr = root; node_ptr && node_ptr->node_type == FNODE; node_ptr = node_ptr->next) { if (strcmp (node_name, node_ptr->name) == 0 && instance == node_ptr->instance ) { fnode_ptr = node_ptr; } } return fnode_ptr; } struct tnode * Process_STATS_File( string inputfile, struct inf_func_element* inf ) { string filename; /* Used to create filename for stats file */ string name; /* Function name read in from the stats file */ string pname; /* Parent name */ FILE *stats_fp; /* file pointer to the stats file */ int file_status = 0; /* Used to determine if stats file EOF is reached */ int instance; /* Instance of a func read in from the stats file */ int number; /* General use for reading numbers from stats file */ struct tnode *curr_ptr; static struct tnode *head_ptr; struct tnode *tnode_ptr; /* struct holds info for each func read from stats file*/ extern bool verbose; memory_count += 2 * sizeof (struct tnode); curr_ptr = (struct tnode *) malloc (sizeof(struct tnode)); head_ptr = (struct tnode *) malloc (sizeof(struct tnode)); /***????????***/ curr_ptr = NULL; head_ptr = NULL; strcpy (filename, inputfile); strcat (filename, STATS_FILE_EXT); stats_fp = fopen (filename, "r"); if (stats_fp == NULL) { error ("Unable to find .ist file"); } file_status = fscanf(stats_fp, "%d", &number); /*func"Read_Inst_Categories" has fscanf*/ /* statmnt reads new values for number */ while (file_status != EOF && number == STATS_FUNC_IDENTIFIER) { fscanf (stats_fp, " func %s instance %d parent %s \n", name, &instance, pname); if (verbose) { fprintf (stderr, "function %s instance = %d parent name %s\n", name, instance, pname); } tnode_ptr = Create_Tnode(name, instance, FNODE, FUNC_START_BLOCK, inf); /*AMOL:Reads all the instrucion categories and puts them in the tnode->inst_list*/ Read_Inst_Categories(stats_fp, &file_status, &number, tnode_ptr); if (head_ptr) { curr_ptr->next = tnode_ptr; curr_ptr = curr_ptr->next; } else { head_ptr = tnode_ptr; curr_ptr = tnode_ptr; } } fclose(stats_fp); /* close stats file, everything read from it */ return head_ptr; } /***************************************************************************** * * FUNCTION NAME: Create_Tnode * * ASSUMPTIONS: * 1. inf ptr passed in should point to the list of inf func elements * read in from the inf file. ******************************************************************************/ struct tnode * Create_Tnode( string name, int instance, enum tnode_type node_type, int loop_header_block, struct inf_func_element* inf ) { struct tnode *node; struct block_list *block_ptr = NULL; struct block_list *list_ptr = NULL; struct exit_block *eblock_ptr = NULL; struct exit_block *ecurr_ptr = NULL; /*****************************/ /* Begin Function Prototypes */ /*****************************/ memory_count += sizeof (struct tnode); node = (struct tnode *) malloc (sizeof(struct tnode)); node->node_type = node_type; strcpy(node->name, name); node->instance = instance; node->loop_number = 0; node->loop_header_block = loop_header_block; node->timed = false; node->wc_pipeline_time = 0; node->bc_pipeline_time = 0; /* beg & end head ?? */ node->extra_time = 0; node->extra_fh_time = 0; node->extra_fm_time = 0; node->shared_fm_time = 0; node->bc_extra_time = 0; node->bc_pc_nai_time = 0; node->wc_pc_nai_time = 0; node->wc_pipe_nai_time = 0; /* rel time & src needed & occ cyc?? */ node->wc_beg_cache_line = 0; node->wc_end_cache_line = 0; node->bc_beg_cache_line = 0; node->bc_end_cache_line = 0; /* avail times? */ node->first_line_delay = 0; node->delay_after_fm = 0; node->last_line_delay = 0; node->wc_first_prog_offset = 0; /* wc beg word num & wc fm end avail time ? */ node->last_fm = 0; node->fm_dead_cycles = 0; node->wc_finish_load = 0; /* wc delay after fm head ? */ node->path_set = NULL; node->imm_follow = NULL; node->exit_list = NULL; node->instruct_list = NULL; node->inf_ptr = Locate_Inf_Func(node, inf); node->loop_paths = NULL; node->branch = NULL; node->parent = NULL; node->sibling = NULL; node->child = NULL; node->next = NULL; /*BOOKMARK- adding the frequency model variables */ node->visa_worst_case = 0; node->icache_misses = 0; node->dcache_misses = 0; node->extra_latency = 0; node->latency_considered = 0; node->total_latency = 0; node->abs_total_latency = 0; node->overlap = 0; node->diff = 0; node->loop_paths = Locate_Loop_Paths(node->loop_header_block, node->inf_ptr); list_ptr = Determine_EBlock_List(node); for (block_ptr = list_ptr; block_ptr; block_ptr = block_ptr->next) { eblock_ptr = Create_EBlock(block_ptr->block_number); if (node->exit_list) ecurr_ptr->next = eblock_ptr; else node->exit_list = eblock_ptr; ecurr_ptr = eblock_ptr; } return node; } /*************************************************************** * * FUNCTION NAME : Create_EBlock * ****************************************************************/ struct exit_block * Create_EBlock( int eblock ) { struct exit_block *block_ptr; memory_count += sizeof (struct exit_block); block_ptr = (struct exit_block *) malloc (sizeof(struct exit_block)); block_ptr->block_number = eblock; block_ptr->best_case = Create_Best_Case_Timing(); block_ptr->worst_case = Create_Worst_Case_Timing(); block_ptr->next = NULL; return block_ptr; } /*************************************************************** * * FUNCTION NAME : Create_Worst_Case_Timing * ****************************************************************/ struct worst_case_timing * Create_Worst_Case_Timing() { struct worst_case_timing *block_ptr; memory_count += sizeof(struct worst_case_timing); block_ptr = (struct worst_case_timing *) malloc (sizeof(struct worst_case_timing)); block_ptr->fm_list = NULL; block_ptr->fh_list = NULL; return block_ptr; } struct best_case_timing * Create_Best_Case_Timing() { struct best_case_timing *block_ptr; memory_count += sizeof(struct best_case_timing); block_ptr = (struct best_case_timing *) malloc (sizeof(struct best_case_timing)); block_ptr->fm_list = NULL; block_ptr->fh_list = NULL; return block_ptr; } /*************************************************************** * * FUNCTION NAME : Create_Inst_Cat * ****************************************************************/ struct inst_cat * Create_Inst_Cat( int inst_number, int loop_number, struct category_list* cat_list, int line_number, string called_func, int instance ) { struct inst_cat *inst_ptr; memory_count += sizeof (struct inst_cat); inst_ptr = (struct inst_cat *) malloc (sizeof(struct inst_cat)); inst_ptr->inst_number = inst_number; inst_ptr->loop_number = loop_number; inst_ptr->instance = instance; inst_ptr->cat_list = cat_list; strcpy(inst_ptr->func, called_func); inst_ptr->line_number = line_number; inst_ptr->next = NULL; return inst_ptr; } /***************************************************************************** * * FUNCTION NAME: Create_Loops * * ASSUMPTIONS: * * 1. Loop nesting levels are sequencial integer values with no gaps in * the ordered list. * 2. Maximum nesting level of "0" indicates that no loops are present * in the function. * 3. Assume that the blocks that comprise a deeply nested loop will * also be included in the block listing for ALL its ancestor loops. * 4. Deeper nested loops will have a higher nesting level than * shallow nested loops. * NOTES: ******************************************************************************* * * M-SPEC void Create_Loops (func) struct tnode *func; { NOTE: func points to the function node being added to the timing tree Determine maximum nesting level; if (loops are present in the function)) { for (each nesting level)do { set loop_ptr to beginning of loop list while (loop_ptr != end of loop list) { if loop_ptr->nesting level equals current nesting level then have found a loop at this nesting level { Create node temp pointer points to the function node if nesting level != 1 { find the parent loop that contains this loop header block in its list of blocks. This must be the loop with a nesting level equal to loop_ptr nesting level - 1. Want to add the child to the parent and not the grandparent. if nesting level = 1 the parent node is the function itself else go down the list func->inf_ptr->loop searching for loops with nesting level = to current nesting level -1. When such a node is found, check the block_list to see if this loop's header block is in the node's block_list. If it is, then that node should be the parent loop to this nested loop. move the temp ptr to the parent loop } add the newly created loop node as a child to the node pointed to by the temp ptr } loop_ptr = loop_ptr->next; } } } } * ******************************************************************************* */ void Create_Loops( struct tnode* func ) { int nest_level=0; /* Current Nesting Level when parsing through loops */ int max_nest_level=0; /* Max nesting level of all loops in the function */ string loop_number; /* String rep'n of the loop nesting level */ string loop_name; /* Array used to create name to reference loop node */ struct loop_element *loop_ptr; /* used parse thru linked list of loops in inf list */ struct tnode *last_node_ptr; /* ptr to last node in linked list of all nodes */ struct tnode *parent_ptr; /* Ptr to the parent node of a loop node */ struct tnode *tnode_ptr; /* Ptr to the latest node being added to the tree */ for (last_node_ptr = func; last_node_ptr && last_node_ptr->next; last_node_ptr = last_node_ptr->next) ; max_nest_level = Determine_Max_Nest_Level(func->inf_ptr->loop); if (max_nest_level > 0) { /* Minimum nesting level for any loop is 1*/ /* 0 represents no loops present */ for (nest_level = 1; nest_level <= max_nest_level; nest_level++) { loop_ptr = func->inf_ptr->loop; while (loop_ptr) { if (loop_ptr->nest_level == nest_level) { itoa (loop_ptr->number, loop_number); /* Create node for this loop */ strcpy(loop_name, Loop_PREFIX); strcat(loop_name, " "); strcat(loop_name, loop_number); /* Parent node either is another loop or the function */ parent_ptr = Locate_Parent_Node(nest_level, loop_ptr->header, func); if (parent_ptr == NULL) { error ("time.bin (Create_Loops): parent_ptr is null"); } tnode_ptr = Create_Tnode(loop_name, 0, LNODE, loop_ptr->header, func->inf_ptr); tnode_ptr->parent = parent_ptr; last_node_ptr->next = tnode_ptr; last_node_ptr = tnode_ptr; Add_Child_Node (parent_ptr, tnode_ptr); /* Place loop node into tree */ } loop_ptr = loop_ptr->next; } } } } /*************************************************************** * * FUNCTION NAME : Determine_EBlock_List * * DESCRIPTION: * Will take in a pointer to a node in the tree and determine the exit blocks * out of that node. * ****************************************************************/ struct block_list * Determine_EBlock_List( struct tnode* node_ptr ) { struct block_list *block_ptr = NULL; struct block_list *curr_ptr = NULL; struct block_list *list_ptr = NULL; struct block_list *exit_block_ptr = NULL; struct loop_path_node *path_ptr; for (path_ptr = node_ptr->loop_paths->path; path_ptr; path_ptr = path_ptr->next) { if (path_ptr->path_type_mask & EXIT) { for (exit_block_ptr=path_ptr->exit_list; exit_block_ptr; exit_block_ptr = exit_block_ptr->next) { if (! Is_In_Block_List(exit_block_ptr->block_number, list_ptr)) { block_ptr = Create_Block_List (exit_block_ptr->block_number); if (list_ptr) { curr_ptr->next = block_ptr; } else { list_ptr = block_ptr; } curr_ptr = block_ptr; } } } } return list_ptr; } /*************************************************************** * * FUNCTION NAME : Determine_Max_Nest_Level * ****************************************************************/ int Determine_Max_Nest_Level( struct loop_element *inf_loop_list ) { int max_nest_level = 0; struct loop_element *loop_ptr = inf_loop_list; for (loop_ptr = inf_loop_list; loop_ptr; loop_ptr = loop_ptr->next) { if (loop_ptr->nest_level > max_nest_level) max_nest_level = loop_ptr->nest_level; } return max_nest_level; } /*************************************************************** * * FUNCTION NAME : Locate_Inf_Func * * DESCRIPTION: * * inf_ptr -- pointer to the list of inf functions * ****************************************************************/ struct inf_func_element * Locate_Inf_Func( struct tnode *tnode_ptr, struct inf_func_element *inf_ptr ) { string func_name; struct inf_func_element *curr_inf; if (tnode_ptr->node_type == LNODE) { return inf_ptr; } else { curr_inf = inf_ptr; while (curr_inf) { if (tnode_ptr->name[0] == '_') strcpy(func_name, tnode_ptr->name+1); else strcpy(func_name, tnode_ptr->name); if (strcmp(func_name, curr_inf->func) == 0) return curr_inf; else curr_inf = curr_inf->next; } return curr_inf; } } /*************************************************************** * * FUNCTION NAME : Locate_Loop_Paths * ****************************************************************/ struct loop_node * Locate_Loop_Paths( int loop_header_block, struct inf_func_element *inf_ptr ) { struct loop_node * loop_node_ptr; for (loop_node_ptr = inf_ptr->loop_nodes; loop_node_ptr && loop_node_ptr->header_block != loop_header_block; loop_node_ptr = loop_node_ptr->next) ; return loop_node_ptr; } /*************************************************************** * * FUNCTION NAME : Locate_Main * ****************************************************************/ struct tnode * Locate_Main( struct tnode* timing_tree ) { struct tnode *tnode_ptr; memory_count += sizeof (tnode_ptr); /*AMOL: This malloc is needed here*/ tnode_ptr = (struct tnode *) malloc (sizeof(tnode_ptr)); for (tnode_ptr = timing_tree; tnode_ptr && strcmp(tnode_ptr->name, Func_MAIN) != 0; tnode_ptr = tnode_ptr->next) ; return tnode_ptr; } /*************************************************************** * * FUNCTION NAME : Locate_Parent_Node * ****************************************************************/ struct tnode * Locate_Parent_Node( int nest_level, int header, struct tnode* func ) { int parent_nest_level = nest_level - 1; string character; /* character representation of number */ string loop_name; struct loop_element * loop_ptr; struct tnode * parent_ptr; if (parent_nest_level <= 0) return func; else { /* Assume if the parent_nest_level > 0 */ /* then the parent loop MUST bin in the list of */ /* loops in the inf information. Therefore */ /* loop_ptr should never == NULL */ loop_ptr = func->inf_ptr->loop; while ( loop_ptr->nest_level != parent_nest_level || Is_In_Block_List(header, loop_ptr->block_list) == false ) { loop_ptr = loop_ptr->next; } strcpy(loop_name, ""); strcpy(loop_name, Loop_PREFIX); strcat(loop_name, " "); itoa(loop_ptr->number, character); strcat(loop_name, character); parent_ptr = Search_Tree_For_Loop_Node(func, loop_name); return parent_ptr; } } /*************************************************************** * * FUNCTION NAME : Locate_Child_Node * ****************************************************************/ struct tnode * Locate_Child_Node( string name, int instance, struct tnode* node_ptr ) { if (node_ptr == NULL) return NULL; else if (strcmp(node_ptr->name, name) == 0 && node_ptr->instance == instance ) return node_ptr; else return Locate_Child_Node(name, instance, node_ptr->sibling); } /*************************************************************** * * FUNCTION NAME : Read_Inst_Categories * ****************************************************************/ void Read_Inst_Categories( FILE *stats_fp, int *file_status, int *number, struct tnode *tnode_ptr ) { char best_case; char worst_case; int count; int instance; int inst_cont; int inst_number; int loop_number; int line_number; /* Cache Line Number */ int nesting; /* Indicates number inst categories in list */ extern int all_cache_hits; extern bool pipeline_only; string called_func; struct inst_cat *inst_ptr; struct inst_cat *curr_ptr = NULL; struct categ**ory_list *cat_ptr = NULL; struct category_list *cat_list = NULL; struct category_list *curr_cat = NULL; /*****************************/ /* Begin Function Prototypes */ /*****************************/ tnode_ptr->instruct_list = NULL; while ( (*file_status = fscanf(stats_fp, "%d", number) != EOF) && (*number == STATS_INST_IDENTIFIER) ) { /* Set default values for called_func and instance */ strcpy (called_func, "\0"); /* These are not read on every instruction category*/ instance = 0; fscanf(stats_fp," inst %d %d %d %d", &inst_number, &loop_number, &line_number, &nesting); cat_list = NULL; curr_cat = NULL; for(count = MIN_LOOP; count < nesting; count++) { fscanf(stats_fp, " %c/%c ", &worst_case, &best_case); cat_ptr = Create_Category_List(best_case, worst_case); /* if we are performing pipeline analysis only, all instruction cache accesses are considered hits (6/1) */ if (all_cache_hits) cat_ptr = Create_Category_List(Hit_INST_CATEGORY, Hit_INST_CATEGORY); else if (pipeline_only) cat_ptr = Create_Category_List(Miss_INST_CATEGORY, Miss_INST_CATEGORY); if (cat_list) { curr_cat->next = cat_ptr; curr_cat = curr_cat->next; } else { cat_list = cat_ptr; curr_cat = cat_ptr; } } fscanf(stats_fp, "%d\n", &inst_cont); if (inst_cont == 1) { fscanf (stats_fp, "\ncall %s instance %d\n", called_func, &instance); } #ifdef CANTFIND printf ("calling Create_Inst_Cat: inst %d. loop # %d\n", inst_number, loop_number); #endif inst_ptr = Create_Inst_Cat (inst_number, loop_number, cat_list, line_number, called_func, instance); if (tnode_ptr->instruct_list) { curr_ptr->next = inst_ptr; curr_ptr = curr_ptr->next; } else { tnode_ptr->instruct_list = inst_ptr; curr_ptr = inst_ptr; } } } /*************************************************************** * * FUNCTION NAME : Search_Tree_For_Loop_Node * ****************************************************************/ struct tnode * Search_Tree_For_Loop_Node( struct tnode* root, string loop_name ) { struct tnode * node_ptr = NULL; Search_Tree(loop_name, root, &node_ptr); return node_ptr; } /*************************************************************** * * FUNCTION NAME : Search_Tree * ****************************************************************/ void Search_Tree( string loop_name, struct tnode *root, struct tnode **node_ptr ) { if (root) { if (strcmp(root->name, loop_name) == 0) *node_ptr = root; else { Search_Tree(loop_name, root->child, node_ptr); Search_Tree(loop_name, root->sibling, node_ptr); } } } /*************************************************************** * * FUNCTION NAME : Add_Child_Node * ****************************************************************/ void Add_Child_Node( struct tnode *parent_ptr, struct tnode *tnode_ptr ) { struct tnode * node_ptr; if (parent_ptr->child) { for (node_ptr = parent_ptr->child; node_ptr->sibling; node_ptr = node_ptr->sibling) ; node_ptr->sibling = tnode_ptr; } else { parent_ptr->child = tnode_ptr; } tnode_ptr->parent = parent_ptr; if (tnode_ptr->node_type == LNODE) tnode_ptr->instance = parent_ptr->instance; } /***************************************************************************** * * FUNCTION NAME: Move_Inst_To_Correct_Loop_Nodes * ******************************************************************************* * * M-SPEC set curr instruction pointer to func->instruct_list while (curr_inst) { Determine the node that the current instruction belongs to If (curr_inst doesn't belong to func) { find the child node of func that it belongs to move the instruction to the instruction list of that tree node if (the instruction is a call instruction) { create a tree node for the invoked function as a child node of the parent tree node } } } *******************************************************************************/ void Move_Inst_To_Correct_Loop_Nodes( struct tnode* func ) { string loop_name; string snumber; struct inst_cat *inst_ptr, *temp_ptr = NULL; struct inst_cat *prev_inst_ptr = NULL; struct inst_cat *loop_inst_ptr; struct tnode *loop_node_ptr; /*****************************/ /* Begin Function Prototypes */ /*****************************/ int SPECIAL = 0; for (inst_ptr = func->instruct_list; inst_ptr; prev_inst_ptr = inst_ptr, inst_ptr = inst_ptr->next) { /*RESET POINTER if special*/ if (SPECIAL) { inst_ptr = temp_ptr; prev_inst_ptr = NULL; SPECIAL = 0; } if (inst_ptr->loop_number > 0) /* if loop num> 0 then inst belongs in a loop node */ { itoa (inst_ptr->loop_number, snumber); strcpy(loop_name, ""); strcpy(loop_name, Loop_PREFIX); strcat(loop_name, " "); strcat(loop_name, snumber); loop_node_ptr = Search_Tree_For_Loop_Node(func, loop_name); if (loop_node_ptr == NULL) { error ("(Move_Inst_To_Correct_Loop_Nodes):loop_node_ptr is null"); } for (loop_inst_ptr = loop_node_ptr->instruct_list; loop_inst_ptr && loop_inst_ptr->next != NULL; loop_inst_ptr = loop_inst_ptr->next); /* Move loop_inst_ptr to the end of the list of instructions in the loop node that you are moving the instructions to. */ if (prev_inst_ptr) /* Moving an instruction in the middle of the list */ { prev_inst_ptr->next = inst_ptr->next; inst_ptr->next = NULL; if (loop_inst_ptr) loop_inst_ptr->next = inst_ptr; else loop_node_ptr->instruct_list = inst_ptr; inst_ptr = prev_inst_ptr; /* reset inst_ptr to prev inst so that it will see */ /* the next inst from the for loop action */ } else /* Move instruction from beginning of the list */ { func->instruct_list = inst_ptr->next; inst_ptr->next = NULL; if (loop_inst_ptr) loop_inst_ptr->next = inst_ptr; else loop_node_ptr->instruct_list = inst_ptr; inst_ptr = func->instruct_list; temp_ptr = inst_ptr; SPECIAL = 1; /* reset inst_ptr to beginning of list for loop */ } } } } /***************************************************************************** * * FUNCTION NAMES: * reverse - given a string, reverse the characters in the string * itoa - convert given integer to its character representation * * These functions were received by Randy White to convert an integer * into a string constant. * ******************************************************************************/ void reverse( char* s ) { int c, i, j; for (i=0, j=strlen(s)-1; i < j; i++, j--) c = s[i], s[i] = s[j], s[j] = c; } void itoa( int n, char* s ) { int i, sign; sign = n; i = 0; do { s[i++] = abs(n % 10) + '0'; } while ((n /= 10) != 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); } void Print_Results( struct tnode * func ) { printf (" FUNCTION NAME WORST CASE\n" " TOTAL TIME\n" " NAIVE ESTIM\n"); Print_Tree(func); } void Print_Parameters( struct tnode* func ) { printf (" FUNCTION NAME WORST CASE\n" " TOTAL TIME\n"); Print_Parameter_Tree(func); } void Print_Tree( struct tnode* func ) { extern bool bc_only, wc_only, naive_too, wrap_around, cache_only; int i, j, wcet1 = 0, wcet2 = 0, bcet1 = 0, bcet2 = 0, tab = 26; static int indent = 0; if (func == NULL) return; for (i = 0; i < indent; i++) printf ("%c", ' '); printf ("%s (%d) ", func->name, func->instance); for (j = i + strlen(func->name); j < tab; j++) printf("%c", ' '); printf (" "); if (!bc_only) { if (cache_only) /* for cache only 5/15/99 */ wcet1 = func->wc_pipe_nai_time; else if (naive_too) wcet1 = func->wc_pc_nai_time; /* if (wrap_around) wcet2 = func->wc_pipeline_time + func->extra_time + func->first_line_delay + func->delay_after_fm + func->last_line_delay + func->fm_dead_cycles; else {*/ wcet2 = func->wc_pipeline_time + func->shared_fm_time + func->extra_time; /*} */ /*for else wrap_Around */ poss_update (&wcet2, func->wc_abs_time, "node's abs time for wcet2"); } if (!wc_only) { if (cache_only) bcet1 = func->bc_pipe_nai_time; else if (naive_too) bcet1 = func->bc_pc_nai_time; bcet2 = func->bc_pipeline_time; } if (wcet1 > 0) printf ("%-10d", wcet1); else printf (" "); if (wcet2 > 0) { printf ("%-10d(%d+%d+%d)\tVISA = %d PC = %d", wcet2,func->wc_pipeline_time,func->extra_time, func->shared_fm_time,func->visa_worst_case, func->inf_ptr->block->instruct_list->PC); } else printf (" "); if (bcet1 > 0) printf ("%-10d", bcet1); else printf (" "); if (bcet2 > 0) printf ("%-10d", bcet2); else printf (" "); printf ("\n"); indent += 3; Print_Tree(func->child); printf ("\n"); indent -= 3; Print_Tree(func->sibling); } void Print_Parameter_Tree( struct tnode* func ) { extern bool bc_only, wc_only, naive_too, wrap_around, cache_only; int i, j, wcet1 = 0, wcet2 = 0, wcet3 = 0, bcet1 = 0, bcet2 = 0, tab = 26; static int indent = 0; if (func == NULL) return; for (i = 0; i < indent; i++) printf ("%c", ' '); printf ("%s (%d) ", func->name, func->instance); for (j = i + strlen(func->name); j < tab; j++) printf("%c", ' '); printf (" "); if (!bc_only) { if (cache_only) /* for cache only 5/15/99 */ wcet1 = func->wc_pipe_nai_time; else if (naive_too) wcet1 = func->wc_pc_nai_time; /* if (wrap_around) wcet2 = func->wc_pipeline_time + func->extra_time + func->first_line_delay + func->delay_after_fm + func->last_line_delay + func->fm_dead_cycles; else {*/ wcet2 = func->wc_pipeline_time; wcet3 = func->total_latency + func->shared_fm_time + func->extra_time; /*}*/ /*for else wrap_Around */ poss_update (&wcet2, func->wc_abs_time, "node's abs time for wcet2"); } if (!wc_only) { if (cache_only) bcet1 = func->bc_pipe_nai_time; else if (naive_too) bcet1 = func->bc_pc_nai_time; bcet2 = func->bc_pipeline_time; } if (wcet1 > 0) printf ("%-10d", wcet1); else printf (" "); if (wcet2 > 0){ printf ("I + M*L = %-5d + %-5d*L \t(%d + %d +%d)", wcet2,wcet3,func->total_latency, func->extra_time,func->shared_fm_time); printf("\n%d %d\n",func->dcache_misses, func->icache_misses); } //func->extra_time,func->shared_fm_time); else printf (" "); if (bcet1 > 0) printf ("%-10d", bcet1); else printf (" "); if (bcet2 > 0) printf ("%-10d", bcet2); else printf (" "); printf ("\n"); indent += 3; Print_Parameter_Tree(func->child); printf ("\n"); indent -= 3; Print_Parameter_Tree(func->sibling); } void Print_Debug( struct tnode* func ) { extern bool bc_only, wc_only, naive_too, wrap_around, cache_only; int i, j, wcet1 = 0, wcet2 = 0,wcet3=0, bcet1 = 0, bcet2 = 0, tab = 26; static int indent = 0; struct inst_cat *temp_inst; struct inf_func_element *temp_inf; struct loop_element *temp_loop; struct block_element *temp_b; struct path_element *temp_pe; struct loop_node *temp_ln; struct loop_node *temp_node; struct loop_path_node *temp_path; struct block_list * temp_exit; struct loop_block_list * temp_block; extern bool PARAMETERIZE; int counter = 0; if (func == NULL) return; for (i = 0; i < indent; i++) printf ("%c", ' '); printf ("%s (%d) ", func->name, func->instance); for (j = i + strlen(func->name); j < tab; j++) printf("%c", ' '); printf (" "); if (!bc_only) { if (cache_only) /* for cache only 5/15/99 */ wcet1 = func->wc_pipe_nai_time; else if (naive_too) wcet1 = func->wc_pc_nai_time; /* if (wrap_around) wcet2 = func->wc_pipeline_time + func->extra_time + func->first_line_delay + func->delay_after_fm + func->last_line_delay + func->fm_dead_cycles; else {*/ wcet2 = func->wc_pipeline_time; if (!PARAMETERIZE) wcet2+= func->shared_fm_time + func->extra_time; wcet3 = func->total_latency + func->shared_fm_time + func->extra_time; /*} */ /*for else wrap_Around */ poss_update (&wcet2, func->wc_abs_time, "node's abs time for wcet2"); } if (!wc_only) { if (cache_only) bcet1 = func->bc_pipe_nai_time; else if (naive_too) bcet1 = func->bc_pc_nai_time; bcet2 = func->bc_pipeline_time; } if (wcet1 > 0) printf ("%-10d", wcet1); else printf (" "); if (wcet2 > 0) { printf ("%-10d(%d+%d+%d)\n\n", wcet2,func->wc_pipeline_time,func->extra_time, func->shared_fm_time); printf("\t\t%-5d + %-5d*L \t(%d + %d +%d)\n\n", wcet2,wcet3,func->total_latency, func->extra_time,func->shared_fm_time); /*Printing the times for all paths */ } else printf (" "); for (temp_node = func->loop_paths; temp_node; temp_node = NULL) { printf ("\t\t\tLOOP NO %d MAX ITERATIONS = %d\n",temp_node->number, temp_node->max_iterations); for (temp_path = temp_node->path; temp_path; temp_path = temp_path->next) { counter++; printf ("\t\t\t\t %d PATH NO %d %d \n", counter,temp_path->number,temp_path); printf("\t\t\t\t\t"); for (temp_block = temp_path->path_list; temp_block; temp_block = temp_block->next) { printf(" %d(%d)",temp_block->block_number,temp_block->wc_time); if (temp_block->is_loop_node) printf("LOOP "); } printf("\n\t\t\t\t\t"); for (temp_exit= temp_path->exit_list; temp_exit; temp_exit= temp_exit->next) { printf(" %d",temp_exit->block_number); } printf("\n"); printf("\t\t\t\tpath_cycles = %d\n",temp_path->path_cycles); if (PARAMETERIZE) printf("\t\t\t\ttotal_latency = %d\n",temp_path->total_latency); if (func->node_type == LNODE) printf("header %d\n",func->loop_header_block); } counter = 0; } printf("\n\n"); /* printf("cats\n"); for (temp_inst = func->instruct_list ; temp_inst; temp_inst= temp_inst->next) { printf("%d %d %d %s %d \n",temp_inst->inst_number, temp_inst->line_number, temp_inst->loop_number, temp_inst->func, temp_inst->instance); } printf("inf\n"); i =0; for (temp_inf = func->inf_ptr; temp_inf; temp_inf = temp_inf->next) { printf("more %d\n",i++); printf("%s %d %d %d \n", temp_inf->func, temp_inf->number, temp_inf->min_block_number, temp_inf->max_block_number); for (temp_loop = temp_inf->loop; temp_loop ; temp_loop= temp_loop->next) { printf("%d %d %d \n",temp_loop->number, temp_loop->min_iterations, temp_loop->max_iterations); printf("blocks\n"); for (temp_exit= temp_loop->block_list; temp_exit; temp_exit= temp_exit->next) { printf(" %d",temp_exit->block_number); } printf("\n"); printf("exits\n"); for (temp_exit= temp_loop->exit_list; temp_exit; temp_exit= temp_exit->next) { printf(" %d",temp_exit->block_number); } printf("\n"); } } */ if (bcet1 > 0) printf ("%-10d", bcet1); else printf (" "); if (bcet2 > 0) printf ("%-10d", bcet2); else printf (" "); printf ("\n"); indent += 3; Print_Debug(func->child); printf ("\n"); indent -= 3; Print_Debug(func->sibling); } void Peek_At_Tree(struct tnode * func) { extern bool bc_only, wc_only, naive_too, wrap_around, cache_only; int i, j, wcet1 = 0, wcet2 = 0, bcet1 = 0, bcet2 = 0, tab = 26; static int indent = 0; if (func == NULL) return; for (i = 0; i < indent; i++) printf ("%c", ' '); printf ("%s (%d) ", func->name, func->instance); printf ("\n"); indent += 3; Peek_At_Tree(func->child); indent -= 3; Peek_At_Tree(func->sibling); }