cfg.h

Go to the documentation of this file.

/*
        Copyright (C) 1997 CFU Corporation

        Author: Chao-yinig Fu
        Date: Oct. 21 1997

        ^..^
        (00)

         $__$
        <~00~>
         (oo)
          ||

        ```````
        C ^|^ D
         \ O /
*/

#ifndef INCLUDED_CFG_H
#define INCLUDED_CFG_H

#include <lego.H>
#include <assert.h>

class MST;

#define ExitNodeId -2           // define node id of an artificial exit node
#define ExitToEntryEdgeId -2    // define edge id from _exit to the _entry
#define LastToExitEdgeId -3     // define edge id from last node to _exit
                                // (from -3, -4, .....)

enum Color
{
        WHITE=0,
        GRAY,
        BLACK
};

enum Edge_Type
{
        ET_UNDEFINED=0,         // undefined
        ET_TREE,                // Tree edge
        ET_BACK,                // Back edge
        ET_FORWARD,             // Forward edge
        ET_CROSS,               // Cross edge
        ET_NEW,                 // New edge which is added after removing
        ET_SELFLOOP             // Selfloop edge (back edge)
};

class Node
{
public:
        Node():_node_id(-1),_weight(0),_edge_id(0),_direction(1),_next_node(NULL),_edge_type(ET_UNDEFINED),_hidden(0),_num_paths(0),_entry_to_dest(NULL),_src_to_exit(NULL),_eff_sum(0)
        {}

        Node(int node_id):_node_id(node_id),_weight(0),_edge_id(0),_direction(1),_next_node(NULL),_edge_type(ET_UNDEFINED),_hidden(0),_num_paths(0),_entry_to_dest(NULL),_src_to_exit(NULL), _eff_sum(0)
        {}

        ~Node() 
        {
        }

        void set_next_node(Node *n) {_next_node=n;}
        void set_node_id(int i) {_node_id=i;}
        void set_weight(int i) {_weight=i;}
        void set_edge_id(int i) {_edge_id=i;}
        void set_direction(int i) {_direction=i;}
        void set_edge_type(Edge_Type i) {_edge_type=i;}
        void set_hidden(int i) {_hidden=i;}
        void set_num_paths(int i) {_num_paths=i;}
        void set_entry_to_dest(Node *i) {_entry_to_dest=i;}
        void set_src_to_exit(Node *i) {_src_to_exit=i;}
        void set_eff_sum(int i) {_eff_sum=i;}

        Node *next_node() {return _next_node;}
        int node_id() {return _node_id;}
        int weight() {return _weight;}
        int edge_id() {return _edge_id;}
        int direction() {return _direction;}
        Edge_Type edge_type() {return _edge_type;}
        int hidden() {return _hidden;}
        int num_paths() {return _num_paths;}
        Node *entry_to_dest() {return _entry_to_dest;}
        Node *src_to_exit() {return _src_to_exit;}
        int eff_sum() {return _eff_sum;}

private:
        Node *_next_node;
        int _node_id;
        int _weight;    // edge weight
        int _edge_id;   // edge id
        int _direction; // 0=in, 1=out
        Edge_Type _edge_type;
        int _hidden;    // 1=this edge is hidden, 0=not hidden
        int _num_paths;

        //
        // Used for transforming back_edge to _entry->dest and src->_exit
        // Record this two nodes (adjacency-list)
        //
        Node *_entry_to_dest;
        Node *_src_to_exit;

        //
        // For efficient event counting
        //
        int _eff_sum;
};

class Node_List
{
public:
        Node_List():_node(NULL),_visit(0),_next_node_list(NULL),_color(WHITE),_predecessor(NULL),_start_time(0),_finish_time(0),_num_paths(0) {}

        ~Node_List()
        {
                Node *current_node,*next_node;
                for(current_node=node();current_node!=NULL;current_node=next_node)
                {
                        next_node=current_node->next_node();
                        delete current_node;
                }
        }

        Node *node() {return _node;}
        int visit() {return _visit;}
        Node_List *next_node_list() {return _next_node_list;}

        void set_node(Node *n) {_node=n;}
        void set_visit(int i) {_visit=1;}
        void set_next_node_list(Node_List *nl) {_next_node_list=nl;}

        Color color() {return _color;}
        Node_List *predecessor() {return _predecessor;}
        int start_time() {return _start_time;}
        int finish_time() {return _finish_time;}
        int num_paths() {return _num_paths;}

        void set_color(Color i) {_color=i;}
        void set_predecessor(Node_List *i) {_predecessor=i;}
        void set_start_time(int i) {_start_time=i;}
        void set_finish_time(int i) {_finish_time=i;}
        void set_num_paths(int i) {_num_paths=i;}
private:
        Node *_node;
        Node_List *_next_node_list;
        int _visit;     // 0=not visit, 1=visit;

        //
        // For depth first search
        //
        Color _color;
        Node_List *_predecessor;        // predecessor in the DFS tree
        int _start_time;
        int _finish_time;
        int _num_paths;
};

class CFG
{
public:
        CFG():_root(NULL),_out_edge_count(0),_in_edge_count(0),_node_count(0),_max_edge_id(0),_entry(NULL),_exit(0),_time(0),_last_to_exit_edge_id(LastToExitEdgeId),_topological_list(NULL) {}

        ~CFG() 
        {
                delete[] _proc_name;

                Node_List *current_nl,*next_nl;
                for(current_nl=_root;current_nl!=NULL;current_nl=next_nl)
                {
                        next_nl=current_nl->next_node_list();
                        delete current_nl;
                }

                delete[] _topological_list;
        }

        void set_root(Node_List *nl) {_root=nl;}
        void set_entry(Node_List *nl) {_entry=nl;}
        void set_exit(Node_List *nl) {_exit=nl;}

        void set_proc_name(char *i)
        {
                _proc_name=new char[strlen(i)+1];
                strcpy(_proc_name,i);
        }

        Node_List *root() {return _root;}
        char *proc_name() {return _proc_name;}
        int node_count() {return _node_count;}
        Node_List *entry() {return _entry;}
        Node_List *exit() {return _exit;}

        void read_file();

        void build(legoProc *proc_ptr);
        void recursive_build(legoProc *proc_ptr,legoRegion *region_ptr);
        void build_one_block(legoProc *proc_ptr,legoRegion *region_ptr);

        void print(FILE *f);
        Node_List *find_node(int node_id);
        
        int edge_count() 
        {
                assert(_in_edge_count==_out_edge_count);
                return _in_edge_count;
        }

        void dfs(int option);           // depth first search
        void dfs_visit(Node_List *nl,int option);       // depth first search visit     

        void process_back_edge();
        Node *add_edge(Node_List *souce,Node_List *dest,int edge_id);
        void add_edge_from_exit_to_entry();

        void print_dfs_tree();
        void print_edge_type(Edge_Type et);
        void print_color(Color c);
        void print_topological_list();

        void unhide_EXIT_edge();
        int assign_value();     // path profiling Figure 5 (Micro 29)

        //
        // For event counting algorithm
        //
        void event_counting(MST *mst);
        void event_dfs(int events,Node_List *v,Node_List *e_nl,Node *e,MST *mst);
        void print_eff_sum(MST *mst);

        //
        // First edge: e_nl -> e_n
        // Second edge: f_nl -> f_n
        //
        // Return 1: same direction
        //        0: opposite direction
        //
        int event_dir(Node_List *e_nl,Node *e_n,Node_List *f_nl,Node *f_n);

        void find_type_of_instrumentation(MST *mst);
        int num_of_incoming_edge(Node_List *vertex);
        void hide_ET_NEW_edge();
        void regenerate_path(FILE *ifp);

private:
        Node_List *_root;       // The root of the adjacency list
        Node_List *_entry;      //Node_List of the entry node in CFG
        Node_List *_exit;       //Node_List of the exit node in CFG
        int _in_edge_count;     // number of in edges
        int _out_edge_count;    // number of out edges
        int _node_count;        // number of nodes
        char *_proc_name;
        int _max_edge_id;       // max edge id in CFG
        int _last_to_exit_edge_id;      // define the edge id from last to _exit

        //
        // For DFS
        //
        int _time;              // global time

        //
        // For topological sort
        //
        int *_topological_list;
        int _index_of_topological_list;
};

#endif //INCLUDED_CFG_H

---