cfg.cpp

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 /
*/

#include "cfg.h"
#include "util.h"
#include "lego_util.h"
#include <assert.h>
#include "mst.h"

//#define CFGDEBUG
#ifdef CFGDEBUG
#define CFGLEVEL 2
#define Cdb(level,format,args...) (CFGLEVEL>=level)?emit_message(format,##args):NULL
#define Cdb_call(level,args...) (CFGLEVEL>=level)?args:NULL
#else
#define Cdb(level,format,args...)
#define Cdb_call(level,args...)
#endif  // CFGDEBUG

void CFG::build(legoProc *proc_ptr)
{
        char *proc_name=proc_ptr->GetProcName();
        set_proc_name(proc_name);
        int region_count=proc_ptr->GetCount();
        Cdb(1,"Proc: %s has %d regions",proc_name,region_count);

        //
        // Step 0. Create an exit node and put this node to root
        //
        Node *a_node=new Node(ExitNodeId);
        _exit=new Node_List();
        _exit->set_node(a_node);
        _root=_exit;    
        _node_count++;

        //
        // Step 1. build nodes and edges
        //
        recursive_build(proc_ptr,proc_ptr);

        //
        // Step 2. add edge from exit to entry
        //
        add_edge_from_exit_to_entry();

        Cdb(2,"_in_edge_count=%d _out_edge_count=%d",_in_edge_count,_out_edge_count);
        assert(_in_edge_count==_out_edge_count);
}

//
// This function will recursively call until reach the basic block rgeion
//
void CFG::recursive_build(legoProc *proc_ptr,legoRegion *region_ptr)
{
        int sub_region_count;
        legoRegion *sub_region_ptr;

        regionTypes region_type=region_ptr->GetRegionType();
        
        switch(region_type)
        {
                case RT_PROC:
                case RT_LOOP:
                case RT_LOOPBODY:
                case RT_TRACE:
                case RT_TREE:
                        sub_region_count=region_ptr->GetCount();
                        for(int i=0;i<sub_region_count;i++)
                        {
                                sub_region_ptr=(legoRegion *)region_ptr->GetItem(i);
                                recursive_build(proc_ptr,sub_region_ptr);
                        }
                        break;

                case RT_SB:
                case RT_HB:
                case RT_BB:
                        build_one_block(proc_ptr,region_ptr);
                        break;

                default:
                        fprintf(stderr,"ERROR region_type\n");
                        assert(0);
                        break;

        }
}

//
// build one block (SB, HB or BB)
//
void CFG::build_one_block(legoProc *proc_ptr,legoRegion *region_ptr)
{
        regionTypes region_type=region_ptr->GetRegionType();

        assert(region_type==RT_SB || region_type==RT_HB || region_type==RT_BB);

        //
        // Step 1. increment _node_count
        //
        _node_count++;

        //
        // Step 2. Create new Node and new Node_List
        //
        Node *current_node=new Node(region_ptr->GetRegionId());
        Node_List *nl=new Node_List();
        nl->set_node(current_node);

        //
        // Step 3. add to the head of _root
        //
        if(_root==NULL)
        {
                _root=nl;
        }
        else
        {
                nl->set_next_node_list(_root);
                _root=nl;
        }

        //
        // Step 4. Iterate in_edge to increment _in_edge_count
        //
        edgeList *edge,*in_edge,*out_edge;
        in_edge=region_ptr->GetInEdgesPtr();
        out_edge=region_ptr->GetOutEdgesPtr();

        for(edge=in_edge;edge!=NULL;edge=edge->GetNextListPtr())
        {
                Cdb(3,">>> in_edge >>> valid=%d",edge->GetValid());

                if(edge->GetValid()==0)
                {
                        //
                        // This node is an entry node.
                        // Set _entry to it
                        //
                        if(_entry!=NULL)
                                assert(0);

                        _entry=nl;
                }
                else
                {
                        if(edge->GetEdgeId()>_max_edge_id)
                                _max_edge_id=edge->GetEdgeId();

                        _in_edge_count++;

                        //opEdges *an_op_edge=edge->GetEdgePtr();
                        //int now_op_id=an_op_edge->GetFromOpId();
                        //int now_region_id=find_legoRegion_with_op_id(proc_ptr,now_op_id)->GetRegionId();
                        //Node *a_node=new Node(now_region_id);
                        //int edge_weight=an_op_edge->GetEdgeAttrListPtr()->GetAttrValPtr()->GetAttrValue();
                        //a_node->set_weight(edge_weight);
                        //a_node->set_next_node(current_node->next_node());
                        //a_node->set_direction(0);     // In
                        //a_node->set_edge_id(edge->GetEdgeId());
                        //current_node->set_next_node(a_node);
                }
        }

        //
        // Step 4. Iterate out_edge to increment _out_edge_count and create edge
        //
        for(edge=out_edge;edge!=NULL;edge=edge->GetNextListPtr())
        {
                Cdb(3,">>> out_edge >>> valid=%d",edge->GetValid());

                if(edge->GetValid()==0)
                {
                        //
                        // This node is a last node.
                        // Create an edge from this node to _exit
                        //
                        assert(_exit!=NULL);

                        Node *a_node=new Node(ExitNodeId);
                        int edge_weight=(int)region_ptr->GetWeight();
                        a_node->set_weight(edge_weight);
                        a_node->set_next_node(current_node->next_node());
                        a_node->set_direction(1);       // Out 
                        a_node->set_edge_id(_last_to_exit_edge_id--);
                        current_node->set_next_node(a_node);

                        // update _out_edge_count and _in_edge_count
                        _out_edge_count++;
                        _in_edge_count++;
                }
                else
                {
                        if(edge->GetEdgeId()>_max_edge_id)
                                _max_edge_id=edge->GetEdgeId();

                        _out_edge_count++;

                        opEdges *an_op_edge=edge->GetEdgePtr();
                        int now_op_id=an_op_edge->GetToOpId();
                        legoRegion *lego_block=find_lego_block_with_op_id(proc_ptr,now_op_id);
                        assert(lego_block!=NULL);
                        int now_region_id=lego_block->GetRegionId();
                        Node *a_node=new Node(now_region_id);
                        int edge_weight=an_op_edge->GetEdgeAttrListPtr()->GetAttrValPtr()->GetAttrValue();
                        a_node->set_weight(edge_weight);
                        a_node->set_next_node(current_node->next_node());
                        a_node->set_direction(1);       // Out 
                        a_node->set_edge_id(edge->GetEdgeId());
                        current_node->set_next_node(a_node);
                }
        }
}

//
// Add one edge from _exit to _entry
//
void CFG::add_edge_from_exit_to_entry()
{
        // For _entry adjacency list
        //Node *n=new Node(_exit->node()->node_id());
        //n->set_edge_id(ExitToEntryEdgeId);
        //n->set_direction(0);
        //n->set_next_node(_entry->node()->next_node());

        int edge_weight=0;
        assert(_entry!=NULL);
        assert(_exit!=NULL);

        for(Node *adj_list=_entry->node()->next_node();adj_list!=NULL;adj_list=adj_list->next_node())
        {
                if(adj_list->direction()==1)
                        edge_weight+=adj_list->weight();
        }
        //n->set_weight(edge_weight);
        //_entry->node()->set_next_node(n);
        
        _in_edge_count++;

        // For _exit adjacency list
        Node *n=new Node(_entry->node()->node_id());
        n->set_edge_id(ExitToEntryEdgeId);
        n->set_direction(1);
        n->set_next_node(_exit->node()->next_node());
        n->set_weight(edge_weight);
        _exit->node()->set_next_node(n);
        _out_edge_count++;
}

void CFG::print(FILE *f)
{
        Node_List *nl;
        Node *n;

        fprintf(f,"\nCFG-------------------------------------\nProc: %s has %d nodes\n",_proc_name,_node_count);
        fprintf(f,"in_edge_count=%d out_edge_count=%d\n",_in_edge_count,_out_edge_count);

        if(_entry!=NULL)
        {
                fprintf(f,"Entry node is: %d\n",_entry->node()->node_id());
        }
        if(_exit!=NULL)
        {
                fprintf(f,"Exit node is: %d\n",_exit->node()->node_id());
        }

        for(nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                n=nl->node();
                fprintf(f,"\nnode_id=%d visit=%d\n",n->node_id(),nl->visit());

                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        fprintf(f,"\tnode_id=%d weight=%d edge_id=%d direction=%d\n",n->node_id(),n->weight(),n->edge_id(),n->direction());     
                }
        }
}

Node_List *CFG::find_node(int node_id)
{
        Node_List *current_nl;

        for(current_nl=root();current_nl!=NULL;current_nl=current_nl->next_node_list())
        {
                Node *node=current_nl->node();
                if(node->node_id()==node_id)
                        return current_nl;
        }
        
        // Cannot find_node with node_id
        fprintf(stderr,"!!! Cannot find node_id=%d\n",node_id);
        assert(0);
        return(NULL);
}

//
// If option=1, set edge_type
// If option=0, don't set edge_type
//
void CFG::dfs(int option)
{
        Cdb(1,"CFG::dfs()");

        // Initialization
        for(Node_List *nl=_root;nl!=NULL;nl=nl->next_node_list())
        {
                nl->set_color(WHITE);
                nl->set_predecessor(NULL);
        }

        // Reset time
        _time=0;

        //
        // Initial topological list
        //
        _topological_list=new int[_node_count];
        _index_of_topological_list=0;

        // Visit from the _entry node of CFG
        dfs_visit(_entry,option);

        Cdb(2,"_entry is done");

        // Visit the remainder nodes
        for(Node_List *nl=_root;nl!=NULL;nl=nl->next_node_list())
        {
                if(nl->color()==WHITE)
                {
                        assert(0);
                        dfs_visit(nl,option);
                }
        }
}

//
// If option=1, set edge_type
// If option=0, don't set edge_type
//
void CFG::dfs_visit(Node_List *nl,int option)
{
        Cdb(1,"CFG::dfs_visit()");
        Cdb(2,"Examine start node_id=%d",nl->node()->node_id());

        nl->set_color(GRAY);

        _time++;
        nl->set_start_time(_time);

        for(Node *n=nl->node()->next_node();n!=NULL;n=n->next_node())
        {
                Cdb(2,"[%d]'s Adjacency list: hidden=%d edge_id=%d direction=%d node_id=%d",nl->node()->node_id(),n->hidden(),n->edge_id(),n->direction(),n->node_id());

                //
                // Search outgoing edges
                //
                if(n->direction()==1 && n->hidden()==0)
                {
                        Cdb(2,"[%d]'s Adjacency list: edge_id=%d (to %d)",nl->node()->node_id(),n->edge_id(),n->node_id());

                        //if(n->edge_type()!=ET_UNDEFINED)
                                //assert(0);

                        Node_List *to_nl=find_node(n->node_id());

                        Color to_nl_color=to_nl->color();
                        if(to_nl_color==WHITE)
                        {
                                Cdb(2,"Its color is WHITE");

                                if(option==1)
                                {
                                        n->set_edge_type(ET_TREE);
                                        Cdb(2,"Its egde type is TREE");
                                }

                                to_nl->set_predecessor(nl);
                                dfs_visit(to_nl,option);
                        }
                        else if(to_nl_color==GRAY && option==1)
                        {
                                Cdb(2,"Its color is GRAY");
                                if(to_nl!=nl)
                                {
                                        n->set_edge_type(ET_BACK);
                                        Cdb(2,"Its egde type is BACK");
                                }
                                else
                                {
                                        n->set_edge_type(ET_SELFLOOP);
                                        Cdb(2,"Its egde type is SELFLOOP");
                                }
                        }
                        else if(to_nl_color==BLACK && option==1)
                        {
                                Cdb(2,"Its color is BLACK");
                                if(nl->start_time() < to_nl->start_time())
                                {
                                        n->set_edge_type(ET_FORWARD);
                                        Cdb(2,"Its egde type is FORWARD");
                                }
                                else
                                {
                                        n->set_edge_type(ET_CROSS);
                                        Cdb(2,"Its egde type is CROSS");
                                }
                        }
                        else if(option==1)
                                assert(0);
                }
        }

        nl->set_color(BLACK);

        _time++;
        nl->set_finish_time(_time);

        assert(_index_of_topological_list<=_node_count);
        _topological_list[_index_of_topological_list]=nl->node()->node_id();
        _index_of_topological_list++;
}

void CFG::print_topological_list()
{
        fprintf(stderr,"Topological List\n");

        for(int i=0;i<_index_of_topological_list;i++)
        {
                fprintf(stderr,"[%d] %d\n",i,_topological_list[i]);
        }
}

void CFG::print_dfs_tree()
{
        Node_List *nl;
        Node *n;

        fprintf(stderr,"\nCFG::print_dfs_tree()\n");
        fprintf(stderr,"Proc: %s has %d nodes\n",_proc_name,_node_count);
        fprintf(stderr,"_in_edge_count=%d _out_edge_count=%d\n",_in_edge_count,_out_edge_count);
        fprintf(stderr,"_entry: %d\n",_entry->node()->node_id());
        fprintf(stderr,"_exit: %d\n",_exit->node()->node_id());
        fprintf(stderr,"_max_edge_id: %d\n",_max_edge_id);

        for(nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                n=nl->node();
                fprintf(stderr,"\n_node_id=%d _num_paths=%d _color=",n->node_id(),nl->num_paths());
                print_color(nl->color());

                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //if(n->direction()==1)
                        //{
                                fprintf(stderr,"_hidden=%d _node_id=%d _weight=%d _edge_id=%d _direction=%d _num_paths=%d _edge_type=",n->hidden(),n->node_id(),n->weight(),n->edge_id(),n->direction(),n->num_paths());        
                                print_edge_type(n->edge_type());
                        //}
                }
        }
}

void CFG::print_edge_type(Edge_Type et)
{
        if(et==ET_UNDEFINED)
                fprintf(stderr,"ET_UNDEFINED\n");
        else if(et==ET_TREE)
                fprintf(stderr,"ET_TREE\n");
        else if(et==ET_BACK)
                fprintf(stderr,"ET_BACK\n");
        else if(et==ET_FORWARD)
                fprintf(stderr,"ET_FORWARD\n");
        else if(et==ET_CROSS)
                fprintf(stderr,"ET_CROSS\n");
        else if(et==ET_NEW)
                fprintf(stderr,"ET_NEW\n");
        else if(et==ET_SELFLOOP)
                fprintf(stderr,"ET_SELFLOOP\n");
        else
                assert(0);
}

void CFG::print_color(Color c)
{
        if(c==WHITE)
                fprintf(stderr,"WHITE\n");
        else if(c==GRAY)
                fprintf(stderr,"GRAY\n");
        else if(c==BLACK)
                fprintf(stderr,"BLACK\n");
        else
                assert(0);
}

// 
//  When see a back edge (u->v),
//  Add two edges (_entry->v), and (u->_exit) in CFG
//  The edge type of these two edges are ET_NEW
//
void CFG::process_back_edge()
{
        Cdb(1,"CFG::process_back_edge()");

        Cdb(2,"Proc: %s has %d nodes",_proc_name,_node_count);
        Cdb(2,"in_edge_count=%d out_edge_count=%d",_in_edge_count,_out_edge_count);
        Cdb(2,"Entry node is: %d",_entry->node()->node_id());
        Cdb(2,"Exit node is: %d",_exit->node()->node_id());

        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                Cdb(2,"\nnode_id=%d",n->node_id());

                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        if(n->direction()==1)
                        {
                                Cdb(2,"hidden=%d node_id=%d edge_id=%d direction=%d edge_type=",n->hidden(),n->node_id(),n->edge_id(),n->direction());  
                                Cdb(2,print_edge_type(n->edge_type()));

                                //
                                // If the edge is to ExitToEntryEdgeId
                                // set this edge hidden=1
                                // Continue to next adj list
                                //
                                if(n->edge_id()==ExitToEntryEdgeId)
                                {
                                        n->set_hidden(1);
                                        continue;
                                }

                                if(n->edge_type()==ET_BACK || n->edge_type()==ET_SELFLOOP)
                                {
                                        //
                                        // This edge becomes hidden
                                        //
                                        n->set_hidden(1);

                                        Node_List *sink=find_node(n->node_id());

                                        //
                                        // If self loop, don't add new edges
                                        //
                                        if(n->edge_type()==ET_SELFLOOP)
                                        {
                                                Cdb(2,"Self Loop");
                                        }
                                        else
                                        {
                                                _max_edge_id++;
                                                Node *new_node=add_edge(_entry,sink,_max_edge_id);
                                                n->set_entry_to_dest(new_node);
                                                Cdb(2,"new_node _edge_id=%d",new_node->edge_id());

                                                _max_edge_id++;
                                                new_node=add_edge(nl,_exit,_max_edge_id);
                                                n->set_src_to_exit(new_node);
                                                Cdb(2,"new_node _edge_id=%d",new_node->edge_id());
                                        }
                                        Cdb_call(3,getchar());
                                }
                        }
                }
        }
}

//
// Create an edge from source to dest with edge_id
// Retrun this new Node (adjacency-list)
//
Node *CFG::add_edge(Node_List *source,Node_List *dest,int edge_id)
{
        //Node *n=source->node();

        // 
        // Edge out of source node
        //
        Node *new_node=new Node(dest->node()->node_id());
        new_node->set_direction(1);
        new_node->set_edge_id(edge_id);
        new_node->set_edge_type(ET_NEW);

        new_node->set_next_node(source->node()->next_node());
        source->node()->set_next_node(new_node);

        Cdb(2,"Add _edge_id=%d from %d to %d",edge_id,source->node()->node_id(),dest->node()->node_id());

        // 
        // Edge into dest node
        //
        Node *other_node=new Node(source->node()->node_id());
        other_node->set_direction(0);
        other_node->set_edge_id(edge_id);
        other_node->set_edge_type(ET_NEW);

        other_node->set_next_node(dest->node()->next_node());
        dest->node()->set_next_node(other_node);

        //
        // Update edge counts
        //
        _in_edge_count++;
        _out_edge_count++;

        return new_node;
}

//
// Return 1, if the number of paths is less than 2^20
// Return 0, if the number of paths is greater than 2^20, we stop profiling
//
int CFG::assign_value()
{
        Cdb(1,"CFG::assign_value()");

        for(int i=0;i<_index_of_topological_list;i++)
        {
                Node_List *nl=find_node(_topological_list[i]);
                Cdb(2,"This node is %d",nl->node()->node_id());

                //
                // We only have one leaf node, which is _exit.
                //
                if(i==0)
                {
                        assert(nl==_exit);
                        nl->set_num_paths(1);
                }
                else
                {
                        nl->set_num_paths(0);

                        for(Node *n=nl->node()->next_node();n!=NULL;n=n->next_node())
                        {
                                if(n->direction()==1 && n->hidden()==0)
                                {
                                        n->set_num_paths(nl->num_paths());
                                        Cdb(2,"_edge_id=%d _num_paths=%d",n->edge_id(),n->num_paths());
                                        Node_List *to_nl=find_node(n->node_id());
                                        int new_num_paths=nl->num_paths()+to_nl->num_paths();
                                        nl->set_num_paths(new_num_paths);
                                        if(new_num_paths>(1<<20))
                                                return 0;
                                }
                        }
                }

                Cdb(2,"_node_id=%d _num_paths=%d",nl->node()->node_id(),nl->num_paths());
                Cdb_call(3,getchar());
        }
        return 1;
}

void CFG::read_file()
{
        FILE *ifp=fopen("my.cfg","r");

        assert(ifp!=NULL);

        int node_count,edge_count;
        fscanf(ifp,"node_count=%d edge_count=%d\n",&node_count,&edge_count);
        fprintf(stderr,"node_count=%d edge_count\n",node_count,edge_count);
        _node_count=node_count;
        _in_edge_count=edge_count;
        _out_edge_count=edge_count;

        int entry_node,exit_node;
        fscanf(ifp,"entry_node=%d exit_node=%d\n",&entry_node,&exit_node);
        fprintf(stderr,"entry_node=%d exit_node=%d\n",entry_node,exit_node);

        Node_List *nl,*prev_nl;
        Node *n;
        for(int i=0;i<node_count;i++)
        {
                int node_id;
                int edge_count;
                fscanf(ifp,"%d (%d)\t",&node_id,&edge_count);
                fprintf(stderr,"%d (%d)\t",node_id,edge_count);

                nl=new Node_List();
                n=new Node(node_id);
                nl->set_node(n);

                if(_root==NULL)
                {
                        _root=nl;
                }
                else
                {
                        prev_nl->set_next_node_list(nl);
                }

                for(int j=0;j<edge_count;j++)
                {
                        fscanf(ifp,"%d ",&node_id);
                        fprintf(stderr,"%d ",node_id);

                        Node *adj_node=new Node(node_id);
                        _max_edge_id++;
                        adj_node->set_edge_id(_max_edge_id);
                        n->set_next_node(adj_node);
                        n=adj_node;
                }
                fscanf(ifp,"\n");
                fprintf(stderr,"\n");

                prev_nl=nl;
        }

        _entry=find_node(entry_node);
        _exit=find_node(exit_node);
        set_proc_name("my.cfg");
        add_edge_from_exit_to_entry();
}

//
// Un-hide this edge ExitToEntryEdgeId
//
void CFG::unhide_EXIT_edge()
{
        Cdb(1,"CFG::unhide_EXIT_edge()");

        Node_List *nl;
        Node *n;

        for(nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //if(n->direction()==1)
                        //{

                                if(n->edge_id()==ExitToEntryEdgeId)
                                        n->set_hidden(0);
                        //}
                }
        }
}

//
// hide ET_NEW edge
//
void CFG::hide_ET_NEW_edge()
{
        Cdb(1,"CFG::hide_ET_NEW_edge()");

        Node_List *nl;
        Node *n;

        for(nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //if(n->direction()==1)
                        //{
                                if(n->edge_type()==ET_NEW)
                                        n->set_hidden(1);

                        //}
                }
        }
}


//
// Efficiently Computing Program Events (from paper)
//
void CFG::event_counting(MST *mst)
{
        Cdb(1,"CFG::event_counting()");

        event_dfs(0,_entry,NULL,NULL,mst);

        //
        // Find edges: not in MST
        //
        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //
                        // Check edges with out direction and hidden=0 
                        // The current edge is n
                        //
                        if(n->direction()==1 && n->hidden()==0)
                        {
                                if(mst->is_mst(n->edge_id())==0)
                                {
                                        int new_eff_sum=n->eff_sum()+n->num_paths();
                                        n->set_eff_sum(new_eff_sum);
                                        Cdb(2,"new_eff_sum=%d",n->eff_sum());
                                }
                        }
                }
        }
}

void CFG::print_eff_sum(MST *mst)
{
        Cdb(1,"CFG::print_eff_sum()");
        //
        // Find edges: not in MST
        //
        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //
                        // Check edges with out direction and hidden=0 
                        // The current edge is n
                        //
                        if(n->direction()==1 && n->hidden()==0)
                        {
                                if(mst->is_mst(n->edge_id())==0)
                                {
                                        fprintf(stderr,"_edge_id=%d (from %d to %d) new_eff_sum=%d\n",n->edge_id(),nl->node()->node_id(),n->node_id(),n->eff_sum());
                                }
                        }
                }
        }
}
void CFG::event_dfs(int events,Node_List *v,Node_List *e_nl,Node *e,MST *mst)
{
        Cdb(1,"CFG::event_dfs()");
        Cdb(2,"events=%d Node_List=%d",events,v->node()->node_id());
        if(e!=NULL)
        {
                Cdb(2,"_edge_id=%d from %d to %d",e->edge_id(),e_nl->node()->node_id(),e->node_id());
        }
        Cdb(1,"Start search (_node_id=%d)",v->node()->node_id());

        //
        // Find edge: in MST & edges!=e & edges's target==v
        //
        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //
                        // Check edges with out direction and hidden=0 
                        // The current edge is "n"
                        //
                        if(n->direction()==1 && n->hidden()==0)
                        {
                                if(mst->is_mst(n->edge_id()) && n!=e && n->node_id()==v->node()->node_id())
                                {
                                        Cdb(2,"Find _edge_id=%d from %d to %d",n->edge_id(),nl->node()->node_id(),n->node_id());

                                        int dir=event_dir(e_nl,e,nl,n);
                                        Cdb(2,"Find dir=%d",dir);
                                        Cdb(2,"Find num_paths=%d",n->num_paths());
                                        int new_event=dir*events+n->num_paths();
                                        Cdb(2,"new_event=%d",new_event);

                                        Cdb_call(3,getchar());
                                        event_dfs(new_event,nl,nl,n,mst);
                                }
                        }
                }
        }
        Cdb(2,"Finish with first search (_node_id=%d)",v->node()->node_id());
        Cdb_call(3,getchar());

        //
        // Find edge: in MST & edges!=e & edges's source==v
        //
        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                //
                // check if source!=v
                // go to next iteration
                //
                if(nl!=v)
                        continue;

                Node *n=nl->node();

                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //
                        // Check edges with out direction and hidden=0 
                        //
                        if(n->direction()==1 && n->hidden()==0)
                        {
                                if(mst->is_mst(n->edge_id()) && n!=e)
                                {
                                        Cdb(2,"Find _edge_id=%d from %d to %d",n->edge_id(),nl->node()->node_id(),n->node_id());

                                        int dir=event_dir(e_nl,e,nl,n);
                                        Cdb(2,"Find dir=%d",dir);
                                        Cdb(2,"Find num_paths=%d",n->num_paths());
                                        Node_List *target=find_node(n->node_id());
                                        int new_event=dir*events+n->num_paths();
                                        Cdb(2,"new_event=%d",new_event);
                                        Cdb_call(3,getchar());
                                        event_dfs(new_event,target,nl,n,mst);
                                }
                        }
                }
        }
        Cdb(2,"Finish with second search (_node_id=%d)",v->node()->node_id());
        Cdb_call(3,getchar());

        //
        // Find edge: isnot in MST & edges!=e & 
        //            edges's target==v or edges' source==v
        //
        for(Node_List *nl=root();nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        //
                        // Check edges with out direction and hidden=0 
                        // The current edge is n
                        //
                        if(n->direction()==1 && n->hidden()==0)
                        {
                                if(mst->is_mst(n->edge_id())==0 && n!=e )
                                {
                                        if(n->node_id()==v->node()->node_id() ||nl==v)
                                        {
                                                Cdb(2,"Find _edge_id=%d from %d to %d",n->edge_id(),nl->node()->node_id(),n->node_id());

                                                int dir=event_dir(e_nl,e,nl,n);
                                                Cdb(2,"Find dir=%d",dir);
                                                Cdb(2,"Find num_paths=%d",n->num_paths());
                                                Cdb(2,"Find eff_sum=%d",n->eff_sum());

                                                int total_eff_sum=n->eff_sum()+dir*events;
                                                n->set_eff_sum(total_eff_sum);
                                                Cdb(2,"new eff_sum=%d",n->eff_sum());
                                                Cdb_call(3,getchar());
                                        }
                                }
                        }
                }
        }
        Cdb(2,"Finish with Third search (_node_id=%d)",v->node()->node_id());

        Cdb_call(3,getchar());
}

//
// First edge: e_nl -> e_n
// Second edge: f_nl -> f_n
//
// Return 1: same direction
//        0: opposite direction
//
int CFG::event_dir(Node_List *e_nl,Node *e_n,Node_List *f_nl,Node *f_n)
{
        if(e_n==NULL)
                return 1;
        else if(e_nl->node()->node_id()==f_n->node_id() ||
                e_n->node_id()==f_nl->node()->node_id())
        {
                return 1;       // same direction
        }
        else if(e_nl->node()->node_id()==f_nl->node()->node_id() ||
                e_n->node_id()==f_n->node_id())
        {
                return -1;      // opposite direction
        }
        else
                assert(0);
}

void CFG::find_type_of_instrumentation(MST *mst)
{
        Cdb(1,"CFG::find_type_of_instrumentation");

        Node_List *queue[_node_count];
        int iq=0;       // index of queue

        //
        // Register initialization code
        //
        queue[iq]=_entry;
        iq++;

        while(iq!=0)
        {
                Node_List *v=queue[0];
                Cdb(2,"Check node_id=%d",v->node()->node_id());

                for(int i=1;i<iq;i++)
                {
                        queue[i-1]=queue[i];
                }
                iq--;
        
                for(Node *e=v->node()->next_node();e!=NULL;e=e->next_node())
                {
                        if(e->direction()==1 && e->hidden()==0)
                        {
                                Cdb(2,"edge_id=%d (from %d to %d)",e->edge_id(),v->node()->node_id(),e->node_id());
                                if(mst->is_mst(e->edge_id())==0)
                                {
                                        // Type r=inc(e)
                                        Cdb(2,"Type r=inc(e)");
                                        Cdb_call(2,getchar());
                                }
                                else if(num_of_incoming_edge(find_node(e->node_id()))==1)
                                {
                                        Cdb(2,"Add node_id=%d to queue",e->node_id());
                                        Cdb_call(2,getchar());
                                        queue[iq]=find_node(e->node_id());
                                        iq++;
                                }
                                else
                                {
                                        // Type r=0;
                                        Cdb(2,"Type r=0");
                                        Cdb_call(2,getchar());
                                }
                        }
                }
        }
}

int CFG::num_of_incoming_edge(Node_List *vertex)
{
        int num=0;

        for(Node_List *nl=_root;nl!=NULL;nl=nl->next_node_list())
        {
                Node *n=nl->node();
                for(n=n->next_node();n!=NULL;n=n->next_node())
                {
                        if(n->direction()==1 && n->hidden()==0 && n->node_id()==vertex->node()->node_id())
                        {
                                num++;
                        }
                }
        }
        return num;
}

//
// Regenerate paths
//
void CFG::regenerate_path(FILE *ifp)
{
        Cdb(1,"CFG::regenerate_path");

        for(int i=0;i<_entry->num_paths();i++)
        {
                int path_value=i;

                fprintf(ifp,"sum=%d: %d",i,_entry->node()->node_id());
                
                Node_List *nl=_entry;
                do
                {
                        Node *max_v=NULL;

                        for(Node *v=nl->node()->next_node();v!=NULL;v=v->next_node())
                        {
                                if(v->direction()==0 || v->edge_type()==ET_BACK || v->edge_type()==ET_SELFLOOP)
                                        continue;

                                int value;

                                if(max_v==NULL)
                                        max_v=v;

                                value=v->num_paths();
                                if(value<=path_value && value>max_v->num_paths())
                                        max_v=v;
                        }

                        //fprintf(ifp,"_(%d)_%d",max_v->edge_id(),max_v->node_id());
                        fprintf(ifp," %d",max_v->node_id());
                        nl=find_node(max_v->node_id());
                        path_value=path_value-max_v->num_paths();
                }
                while(nl!=_exit);

                fprintf(ifp,"\n");
        }
}

---