/* ***************************************************************************** * * * File NAME : PATH.C * PROGRAMMER(S) : Robert Arnold * DATE CREATED : July 19, 1993 * * LAST EDITED : Thu Sep 15 09:53:37 1994 by arnold (Robert Arnold) on xi * ****************************************************************************** */ #include "timeds.h" /* Added by Sibin M on Oct 25, 2004. * Process of cleaning up the TA for C++ */ #include "path.h" #include "lib.h" #include /* Added by Sibin M on Oct 25, 2004. * Process of cleaning up the TA for C++ */ #include #ifdef DISPLAY #define printc printf #else #define printc #endif /********************************************************** * * FUNCTION NAME : Create_Timing_Paths * * DESCRIPTION: * This function will go through the flow-of-control information * from the function lists and determine all possible paths * through the code. * ***********************************************************/ void Create_Timing_Paths( struct inf_func_element** func ) { struct block_list *succ_list; struct loop_node *loop_node_ptr; struct path_element *head_ptr; struct path_element *path_ptr; struct path_element *cb_ptr; struct path_element *new_path; struct block_element *func_block_ptr; extern bool verbose; if (verbose) { printc ("CREATING TIMING PATHS FOR FUNCTION : %s\n", (*func)->func); } Create_Loop_Nodes(*func); if (verbose) { for (loop_node_ptr = (*func)->loop_nodes; loop_node_ptr; loop_node_ptr = loop_node_ptr->next) Print_Loop_Node(loop_node_ptr); } /*AMOL: Creates a path node and checks if the node is in a loop + pointer to the block with block_number is given*/ head_ptr = Create_Path_Element((*func)->min_block_number, (*func)->loop_nodes); path_ptr = head_ptr; /*AMOL: 1 Create a list of nodes from the first block by using the block number 2 Add it to the */ while (path_ptr) { /*Here cb_ptr is struct path_element * */ for (cb_ptr = path_ptr; cb_ptr->succ; cb_ptr = cb_ptr->succ) ; while (cb_ptr) { /*AMOL:Searches the list of blocks from the func->block with the block_number of the last element in the path lsit*/ func_block_ptr = Find_Func_Block_Struct ((*func)->block, cb_ptr->block_number); /*AMOL:*Add the replicas of the block of successors*/ if (cb_ptr->is_loop_node == false) succ_list = Determine_Block_Succ_List (func_block_ptr); else succ_list = Determine_Loop_Exit_Blocks (cb_ptr->block_number, *func); /*AMOL: Copy the original list of succesors in new path and append this block in succ list the This makes diff paths*/ while (Multiple_Blocks_In_Blocklist(succ_list) == true) { new_path = Copy_Path_List(path_ptr, (*func)->loop_nodes); Append_Path_Succ_Block (new_path, &succ_list, (*func)->loop_nodes); new_path->next = path_ptr->next; path_ptr->next = new_path; } if (succ_list) Append_Path_Succ_Block(path_ptr, &succ_list, (*func)->loop_nodes); cb_ptr = cb_ptr->succ; } path_ptr = path_ptr->next; } (*func)->path = head_ptr; } /**************************************************************** * * FUNCTION NAME : Create_Loop_Nodes; * * ASSUMPTIONS: * 1. This function will assume that each loop will have at least * one path thru it. This path is not required to exit the loop * so it has the capability of handling infinite loops. * * 2. Assume that any one node in the loop path can have at most 1 exit * block out of the loop from that node. * * 3. Since each function is considered to be a loop that iterates 1 time, * the assumption will be that at least 1 loop node will be created for * each function. That loop node will have a nesting level of 0. * * * QUESTIONS: * 1. If the first block in a loop is a nested loop, how will this * algorithm react. * * * ALGORITHM * while (loop_ptr) * { * if (loop_ptr->exit_block == LIST_TERMINATOR) * while ( cb_ptr) * { * get list of successor blocks; * if (bp_ptr is backedge) * { * if (more than 1 block exists in list of succ blocks) * { * make new path; * copy current path to new path; * append 1st block in the list of successor blocks that is * in the loop and dominates the current block to the * new path's exit block list * } * else * append 1st block in the list of sucessor blocks that is * in the loop and dominates the current block to the * current path's exit block list * } * else if ( cb_ptr is exit block) * { * if (more than 1 block exists in list of succ blocks) * { * make new path; * copy current path to new path; * append 1st block in list of successor blocks that is not * in the loop to the new path's exit block list * } * else * append 1st block in the list of successor blocks that is * not in the loop to the current path's exit block list * } * * while ( more than 1 successor block exists in list * of successor blocks) * { * make new path; * copy current path to new path; * append first successor block in list to end of new path list * } * * if (succssor block exists in list of successor blocks) * append block to current path list; * * move cb_ptr to end of path list; * } * loop_ptr = loop_ptr->next; * * } * ****************************************************************/ void Create_Loop_Nodes( struct inf_func_element* func ) { int max_nesting_level; /* loop nesting levels within the function */ struct loop_element *func_loop_ptr = NULL; /* points to the inf loop structs within func */ struct block_element *func_block_ptr = NULL; /* points to the inf block structs within func */ struct loop_node *loop_node_ptr; /* points to node containing all paths thru loop*/ struct loop_node *tmp_ptr = NULL; /* used to make lint happy */ struct loop_path_node *loop_path_ptr = NULL; struct loop_path_node *new_path = NULL; struct loop_block_list *cb_ptr = NULL; /* points to blocks within each path thru loop */ struct block_list *succ_list = NULL; /* list of successor blocks to current block */ extern bool verbose; if (verbose) { printc ("I just entered Create_Loop_Nodes for func = %s\n", func->func); } func->loop_nodes = NULL; /*AMOL : goes through func->loop->nest_level; loop=loop->next to get the max level*/ max_nesting_level = Find_Max_Loop_Nesting_Level (func->loop); for ( ; max_nesting_level >= 0; max_nesting_level--) { if (verbose) { printc ("start of big for-loop with max_nesting_level = %d\n", max_nesting_level); } func_loop_ptr = func->loop; /* point to list of loops inside function */ while (func_loop_ptr) { if (verbose) { printc (" start of outer while (func_loop_ptr)\n"); } while ( (func_loop_ptr) && (func_loop_ptr->nest_level != max_nesting_level)) func_loop_ptr = func_loop_ptr->next; if (func_loop_ptr) { if (verbose) { printc (" about to call Create_Loop_Node\n"); } /* the loop node for a loop represents all */ /* the paths thru that loop with all important info */ loop_node_ptr = Create_Loop_Node (func_loop_ptr->number, func_loop_ptr->header, func_loop_ptr->nest_level, func_loop_ptr->min_iterations, func_loop_ptr->max_iterations, func_loop_ptr->abs_min_iterations, func_loop_ptr->abs_max_iterations); /* made the assumption that at least 1 path*/ /* thru the loop exists, therefore create */ /* struct to hold the loop path. */ /*AMOL:Create a path node which has a lot of struct values*/ loop_node_ptr->path = Create_Loop_Path (func_loop_ptr->header); loop_node_ptr->path->path_list = Create_Loop_Block_List( func_loop_ptr->block_list->block_number, false, tmp_ptr); loop_path_ptr = loop_node_ptr->path; while (loop_path_ptr) { if (verbose) { printc (" start of inner while (func_loop_ptr)\n"); Print_Loop_Node (loop_node_ptr); } /* All incomplete paths will have the */ /* incomplete paths set to NULL */ if (loop_path_ptr->exit_list == NULL) { if (verbose) { printc (" exit list is null\n"); Print_Loop_Node (loop_node_ptr); } /*cb_ptr is a struct loop_block_list * */ cb_ptr = Move_To_Loop_Path_End (loop_path_ptr); while (cb_ptr) { if (verbose) { printc (" start of while (cb_ptr)\n"); Print_Loop_Node (loop_node_ptr); } func_block_ptr = Find_Func_Block_Struct (func->block, cb_ptr->block_number); if (cb_ptr->is_loop_node == false) succ_list = Determine_Block_Succ_List (func_block_ptr); else succ_list = Determine_Loop_Exit_Blocks ( cb_ptr->block_number, func); if (Loop_Backedge(succ_list, func_block_ptr) == true) { if (Multiple_Blocks_In_Blocklist(succ_list) == true ) { if (verbose) { printc (" setting new_path (1)\n"); Print_Loop_Node (loop_node_ptr); } new_path = Copy_Loop_Path_Node_List(loop_path_ptr); Append_Dom_Block(new_path, &succ_list, func_loop_ptr, func_block_ptr); /* * don't add to list of paths! 2/2/99 */ /* new_path->next = loop_path_ptr->next; loop_path_ptr->next = new_path; */ loop_path_ptr->path_type_mask |= BACKEDGE; if (verbose) { printc (" after setting new_path (1)\n"); Print_Loop_Node (loop_node_ptr); } } else Append_Dom_Block(loop_path_ptr, &succ_list, func_loop_ptr, func_block_ptr); } if (Loop_Exit_Block (cb_ptr->block_number, func_loop_ptr) == true) { if (Multiple_Blocks_In_Blocklist(succ_list) == true) { if (verbose) printc (" setting new_path (2)\n"); new_path = Copy_Loop_Path_Node_List(loop_path_ptr); if (max_nesting_level > 0) Append_Exit_Block(new_path, &succ_list, func_loop_ptr); else { Append_Block_Blocklist(cb_ptr->block_number, &new_path->exit_list); new_path->path_type_mask |= EXIT; } new_path->next = loop_path_ptr->next; loop_path_ptr->next = new_path; } else { if (max_nesting_level > 0) { if (verbose) { printc (" before append exit block\n"); Print_Loop_Node (loop_node_ptr); } Append_Exit_Block(loop_path_ptr, &succ_list, func_loop_ptr); if (verbose) { printc (" after append exit block\n"); Print_Loop_Node (loop_node_ptr); } } else { Append_Block_Blocklist(cb_ptr->block_number, &loop_path_ptr->exit_list); loop_path_ptr->path_type_mask |= EXIT; } } } while (Multiple_Blocks_In_Blocklist(succ_list) == true) { if (verbose) printc (" setting new_path (3)\n"); new_path = Copy_Loop_Path_Node_List(loop_path_ptr); Append_Succ_Block(new_path, &succ_list, func->loop_nodes); new_path->next = loop_path_ptr->next; loop_path_ptr->next = new_path; } if (succ_list) Append_Succ_Block(loop_path_ptr, &succ_list, func->loop_nodes); cb_ptr = cb_ptr->next; } } else loop_path_ptr = loop_path_ptr->next; } if (func->loop_nodes) { loop_node_ptr->next = func->loop_nodes; func->loop_nodes = loop_node_ptr; } else func->loop_nodes = loop_node_ptr; func_loop_ptr = func_loop_ptr->next; } } } if (verbose) { printc ("returning from Create_Loop_Nodes\n"); } } /*************************************************************** * * FUNCTION NAME : Find_Max_Loop_Nesting_Level * ****************************************************************/ int Find_Max_Loop_Nesting_Level( struct loop_element* loop_list ) { int max_level = 0; struct loop_element *curr_loop; curr_loop = loop_list; while (curr_loop) { if (curr_loop->nest_level > max_level) max_level = curr_loop->nest_level; curr_loop = curr_loop->next; } return max_level; } /*************************************************************** * * FUNCTION NAME : Append_Dom_Block * * DESCRIPTION: * This function will take the first dominator block from the list of * successor blocks and append it to the exit path of the loop node * passed in. * ****************************************************************/ void Append_Dom_Block( struct loop_path_node* path, struct block_list** succ_list, struct loop_element* func_loop_ptr, struct block_element* func_block_ptr ) { struct block_list *list_ptr; for (list_ptr = *succ_list; list_ptr; list_ptr = list_ptr->next) { if(Is_In_Block_List (list_ptr->block_number, func_loop_ptr->block_list) && Is_In_Block_List (list_ptr->block_number, func_block_ptr->dom) ) { Append_Block_Blocklist (list_ptr->block_number, &(path->exit_list)); Delete_Blocklist(list_ptr->block_number, succ_list); path->path_type_mask |= BACKEDGE; } } } /*************************************************************** * * FUNCTION NAME : Append_Exit_Block * * DESCRIPTION: * This function will take the first exit block from the list of * successor blocks and append it to the specified path. * ****************************************************************/ void Append_Exit_Block( struct loop_path_node* path, struct block_list** succ_list, struct loop_element* func_loop_ptr ) { struct block_list *list_ptr; for (list_ptr = *succ_list; list_ptr; list_ptr = list_ptr->next) { if (Is_In_Block_List(list_ptr->block_number, func_loop_ptr->block_list) == false) { Append_Block_Blocklist (list_ptr->block_number, &(path->exit_list)); Delete_Blocklist(list_ptr->block_number, succ_list); path->path_type_mask |= EXIT; } } } /*************************************************************** * * FUNCTION NAME : Append_Succ_Block * * DESCRIPTION: * This function will take the first block from the list of successor blocks * and append it to the path. * ****************************************************************/ void Append_Succ_Block( struct loop_path_node* path, struct block_list** succ_list, struct loop_node* loop_node_list ) { if (*succ_list) { Append_Block_Pathlist ((*succ_list)->block_number, loop_node_list, path->path_list); Delete_Blocklist((*succ_list)->block_number, succ_list); } } /*************************************************************** * * FUNCTION NAME : Append_Path_Succ_Block * ****************************************************************/ void Append_Path_Succ_Block( struct path_element* path, struct block_list** succ_list, struct loop_node* loop_node_list ) { if (*succ_list) { Append_Block_Path ((*succ_list)->block_number, loop_node_list, path); Delete_Blocklist ((*succ_list)->block_number, succ_list); } } /*************************************************************** * * FUNCTION NAME : Determine_Successor_Blocks * * DESCRIPTION: * This function will take in a block number and * determine the list of successor blocks * ****************************************************************/ struct block_list * Determine_Block_Succ_List( struct block_element* func_block_ptr ) { struct block_list *list_ptr = NULL; struct block_list *head_ptr = NULL; struct block_list *block_ptr = NULL; struct block_list *curr_ptr = NULL; if (func_block_ptr && func_block_ptr->succ) { for (list_ptr = func_block_ptr->succ; list_ptr; list_ptr=list_ptr->next) { block_ptr = Create_Block_List(list_ptr->block_number); if (head_ptr) { curr_ptr->next = block_ptr; curr_ptr = curr_ptr->next; } else { head_ptr = block_ptr; curr_ptr = block_ptr; } } } return head_ptr; } /*************************************************************** * * FUNCTION NAME : Determine_Loop_Exit_Blocks * * DESCRIPTION: * This function will read in the block number * and return a pointer to a list of all possible blocks * that the loop can exit to. If no exit blocks exist, * then a NULL pointer will be returned. * * NOTE: Exit blocks in this function are defined to be the successor * blocks to the exit blocks in the loop. * ****************************************************************/ struct block_list * Determine_Loop_Exit_Blocks( int block_number, struct inf_func_element* func ) { struct block_list *list_ptr = NULL; struct block_list *head_ptr = NULL; struct block_list *curr_ptr = NULL; struct block_list *block_ptr = NULL; struct loop_element *func_loop_ptr; struct loop_path_node *path; struct loop_node *node_ptr = func->loop_nodes; for (; (node_ptr) && (node_ptr->header_block != block_number); node_ptr = node_ptr->next) ; if (node_ptr) { func_loop_ptr = Find_Func_Loop_Struct(block_number, func->loop); for (path = node_ptr->path; path; path = path->next) { if (path->path_type_mask & EXIT) for (list_ptr=path->exit_list; list_ptr; list_ptr = list_ptr->next) if ( Is_In_Block_List(list_ptr->block_number, func_loop_ptr->block_list) == false && Is_In_Block_List(list_ptr->block_number, head_ptr) == false ) { block_ptr = Create_Block_List (list_ptr->block_number); if (head_ptr) { curr_ptr->next = block_ptr; curr_ptr = curr_ptr->next; } else { head_ptr = block_ptr; curr_ptr = block_ptr; } } } } return head_ptr; } /*************************************************************** * * FUNCTION NAME : Loop_Backedge * ****************************************************************/ bool Loop_Backedge( struct block_list* succ_list, struct block_element* func_block_ptr ) { struct block_list *list_ptr; for (list_ptr = succ_list; list_ptr; list_ptr = list_ptr->next) if (Is_In_Block_List(list_ptr->block_number,func_block_ptr->dom) == true) { return true; } return false; } /*************************************************************** * * FUNCTION NAME : Loop_Exit_Block * ****************************************************************/ bool Loop_Exit_Block( int block_number, struct loop_element* func_loop_ptr ) { if (Is_In_Block_List(block_number,func_loop_ptr->exit_list) == true) return true; return false; } /*************************************************************** * * FUNCTION NAME : Find_Func_Block_Struct * * DESCRIPTION: * This function will take a block number and search the list of block * structures for that particular block. * ****************************************************************/ struct block_element * Find_Func_Block_Struct( struct block_element* head_block_ptr, int block_number ) { struct block_element *block_ptr = head_block_ptr; if (head_block_ptr) while (block_ptr && block_ptr->block_number != block_number) block_ptr = block_ptr->next; return block_ptr; } /*************************************************************** * * FUNCTION NAME : Find_Func_Loop_Struct * * DESCRIPTION: * This function will take a block number and search the list of loop * structures for that loop structure definition * ****************************************************************/ struct loop_element * Find_Func_Loop_Struct( int block_number, struct loop_element* loop_struct_ptr ) { struct loop_element *loop_ptr = loop_struct_ptr; if (loop_ptr) while (loop_ptr && loop_ptr->block_list->block_number != block_number) loop_ptr = loop_ptr->next; return loop_ptr; } /*************************************************************** * * FUNCTION NAME : Move_To_Loop_Path_End * * DESCRIPTION: * This function will take in a pointer to a path and * return a pointer to the last path node in the path. * * ASSUMPTIONS: * * cb_ptr = Move_To_Loop_Path_End (loop_path_ptr); * struct loop_path_node *loop_path_ptr = NULL; * ****************************************************************/ struct loop_block_list * Move_To_Loop_Path_End( struct loop_path_node* path ) { struct loop_block_list *curr_ptr = NULL; if (path) { if (path->path_list) { curr_ptr = path->path_list; while (curr_ptr->next) curr_ptr = curr_ptr->next; } } return curr_ptr; } void Print_Loop_Node( struct loop_node* loop_node_ptr ) { struct block_list *block_ptr; struct loop_block_list *path_block_ptr; struct loop_path_node *loop_path_ptr; printc ("\n PRINTING LOOP NODE \n"); printc (" loop header block = %d\n", loop_node_ptr->header_block); printc (" MIN ITERATION = %d\n", loop_node_ptr->min_iterations); printc (" MAX ITERATION = %d\n", loop_node_ptr->max_iterations); for (loop_path_ptr = loop_node_ptr->path; loop_path_ptr; loop_path_ptr = loop_path_ptr->next) { if (loop_path_ptr->path_type_mask == (BACKEDGE | EXIT)) printc (" BOTH BACKEDGE AND EXIT\n"); else if (loop_path_ptr->path_type_mask & BACKEDGE) printc (" BACKEDGE\n"); else if (loop_path_ptr->path_type_mask & EXIT) printc (" EXIT\n"); else if (loop_path_ptr->path_type_mask == NONE) printc (" NONE\n"); else { printf ("unknown path_type_mask %d in Print_Loop_Node()", loop_path_ptr->path_type_mask); exit (1); } printc (" PATH LIST = "); for (path_block_ptr = loop_path_ptr->path_list; path_block_ptr; path_block_ptr = path_block_ptr->next) { printc(" %d ", path_block_ptr->block_number); } printc ("\n"); printc (" EXIT LIST = "); for (block_ptr = loop_path_ptr->exit_list; block_ptr; block_ptr = block_ptr->next) { printc(" %d ", block_ptr->block_number); } printc ("\n\n"); } }