Add edges between FuncNodes

diff --git a/funcnode.cc b/funcnode.cc
index 19601fac5c4f3bd62882f8ba8456afb8ad36af0f..c490ba228fe504cf51487df7cbb753491f4328b2 100644 (file)
--- a/funcnode.cc
+++ b/funcnode.cc
@@ -2,12 +2,14 @@
 
 FuncNode::FuncNode(ModelHistory * history) :
        history(history),
-       predicate_tree_initialized(false),
        exit_count(0),
        func_inst_map(),
        inst_list(),
        entry_insts(),
-       predicate_tree_position()
+       predicate_tree_position(),
+       edge_table(32),
+       out_edges(),
+       in_edges()
 {
        predicate_tree_entry = new Predicate(NULL, true);
        predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true);
@@ -603,6 +605,39 @@ inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid)
        return (*thrd_inst_act_map)[thread_id];
 }
 
+/* Add FuncNodes that this node may follow */
+void FuncNode::add_out_edge(FuncNode * other)
+{
+       if ( !edge_table.contains(other) ) {
+               edge_table.put(other, OUT_EDGE);
+               out_edges.push_back(other);
+               return;
+       }
+
+       edge_type_t edge = edge_table.get(other);
+       if (edge == IN_EDGE) {
+               edge_table.put(other, BI_EDGE);
+               out_edges.push_back(other);
+       }
+}
+
+/* Add FuncNodes that come before this node */
+void FuncNode::add_in_edge(FuncNode * other)
+{
+       if ( !edge_table.contains(other) ) {
+               edge_table.put(other, IN_EDGE);
+               in_edges.push_back(other);
+               return;
+       }
+
+       edge_type_t edge = edge_table.get(other);
+       if (edge == OUT_EDGE) {
+               edge_table.put(other, BI_EDGE);
+               in_edges.push_back(other);
+       }
+}
+
+
 void FuncNode::print_predicate_tree()
 {
        model_print("digraph function_%s {\n", func_name);

diff --git a/funcnode.h b/funcnode.h
index c70bc59c05c13e996be0e1da4d501b3c04395fce..a2037dc3c040c206d719f0ca710d6a224215007e 100644 (file)
--- a/funcnode.h
+++ b/funcnode.h
@@ -11,6 +11,10 @@
 typedef ModelList<FuncInst *> func_inst_list_mt;
 typedef HashTable<FuncInst *, ModelAction *, uintptr_t, 0> inst_act_map_t;
 
+typedef enum edge_type {
+       IN_EDGE, OUT_EDGE, BI_EDGE
+} edge_type_t;
+
 class FuncNode {
 public:
        FuncNode(ModelHistory * history);
@@ -53,6 +57,9 @@ public:
        void update_inst_act_map(thread_id_t tid, ModelAction * read_act);
        inst_act_map_t * get_inst_act_map(thread_id_t tid);
 
+       void add_out_edge(FuncNode * other);
+       void add_in_edge(FuncNode * other);
+
        void print_predicate_tree();
        void print_val_loc_map();
        void print_last_read(thread_id_t tid);
@@ -62,7 +69,6 @@ private:
        uint32_t func_id;
        const char * func_name;
        ModelHistory * history;
-       bool predicate_tree_initialized;
        Predicate * predicate_tree_entry;       // a dummy node whose children are the real entries
 
        uint32_t exit_count;
@@ -99,6 +105,11 @@ private:
 
        /* A run-time map from FuncInst to ModelAction for each thread; needed by NewFuzzer */
        SnapVector<inst_act_map_t *> * thrd_inst_act_map;
+
+       /* Store the relation between this FuncNode and other FuncNodes */
+       HashTable<FuncNode *, edge_type_t, uintptr_t, 0, model_malloc, model_calloc, model_free> edge_table;
+       ModelList<FuncNode *> out_edges;        /* FuncNodes that follow this node */
+       ModelList<FuncNode *> in_edges;         /* FuncNodes that comes before this node */
 };
 
 #endif /* __FUNCNODE_H__ */

diff --git a/history.cc b/history.cc
index 8a605fbfd8f2f06fc32b7219ef1a6b82683dd5e1..42a218e03d7b98ba692bb7bdfaf55925260fe781 100644 (file)
--- a/history.cc
+++ b/history.cc
@@ -42,9 +42,10 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
        }
 
        SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
+       func_act_lists->push_back( new action_list_t() );
 
+       uint32_t last_func_id = (*thrd_func_list)[id].back();
        (*thrd_func_list)[id].push_back(func_id);
-       func_act_lists->push_back( new action_list_t() );
 
        if ( func_nodes.size() <= func_id )
                resize_func_nodes( func_id + 1 );
@@ -52,6 +53,12 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
        FuncNode * func_node = func_nodes[func_id];
        func_node->init_predicate_tree_position(tid);
        func_node->init_inst_act_map(tid);
+
+       /* Add edges between FuncNodes */
+       if (last_func_id != 0) {
+               FuncNode * last_func_node = func_nodes[last_func_id];
+               add_edges_between(last_func_node, func_node);
+       }
 }
 
 /* @param func_id a non-zero value */
@@ -178,6 +185,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
        if (act->is_read()) {
                func_node->update_inst_act_map(tid, act);
 
+               // Update predicate tree position
                Fuzzer * fuzzer = model->get_execution()->getFuzzer();
                Predicate * selected_branch = fuzzer->get_selected_child_branch(tid);
                func_node->set_predicate_tree_position(tid, selected_branch);
@@ -225,6 +233,13 @@ void ModelHistory::set_new_exec_flag()
        }
 }
 
+/* Add edges between FuncNodes */
+void ModelHistory::add_edges_between(FuncNode * prev_node, FuncNode * next_node)
+{
+       prev_node->add_out_edge(next_node);
+       next_node->add_in_edge(prev_node);
+}
+
 void ModelHistory::print_write()
 {
 }

diff --git a/history.h b/history.h
index 0a51e6404826bda5407cbf41be96b8635051f5df..7a01d4027a150a1d8054f057e3c9854512d95ac4 100644 (file)
--- a/history.h
+++ b/history.h
@@ -51,6 +51,8 @@ private:
 
        /* Map a location to FuncNodes that may read from it */
        HashTable<void *, SnapList<FuncNode *> *, uintptr_t, 4> loc_func_nodes_map;
+
+       void add_edges_between(FuncNode * prev_node, FuncNode * next_node);
 };
 
 #endif /* __HISTORY_H__ */