From a4e6e66dfdeb8a5e792433c0cb90c01e6c0a3f92 Mon Sep 17 00:00:00 2001 From: weiyu Date: Mon, 16 Sep 2019 16:28:41 -0700 Subject: [PATCH] Construct the graph of methods based on the order that methods are called, rather than construct it as a call graph --- funcnode.cc | 20 +------------------- funcnode.h | 3 +-- history.cc | 47 +++++++++++++++++++++++++++-------------------- history.h | 3 ++- 4 files changed, 31 insertions(+), 42 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index c490ba22..93e6b09d 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -8,8 +8,7 @@ FuncNode::FuncNode(ModelHistory * history) : entry_insts(), predicate_tree_position(), edge_table(32), - out_edges(), - in_edges() + out_edges() { predicate_tree_entry = new Predicate(NULL, true); predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true); @@ -621,23 +620,6 @@ void FuncNode::add_out_edge(FuncNode * 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 a2037dc3..3a353fd8 100644 --- a/funcnode.h +++ b/funcnode.h @@ -58,7 +58,7 @@ public: inst_act_map_t * get_inst_act_map(thread_id_t tid); void add_out_edge(FuncNode * other); - void add_in_edge(FuncNode * other); + ModelList * get_out_edges() { return &out_edges; } void print_predicate_tree(); void print_val_loc_map(); @@ -109,7 +109,6 @@ private: /* Store the relation between this FuncNode and other FuncNodes */ HashTable edge_table; ModelList out_edges; /* FuncNodes that follow this node */ - ModelList in_edges; /* FuncNodes that comes before this node */ }; #endif /* __FUNCNODE_H__ */ diff --git a/history.cc b/history.cc index 42a218e0..cb5307a9 100644 --- a/history.cc +++ b/history.cc @@ -14,8 +14,9 @@ ModelHistory::ModelHistory() : func_map(), func_map_rev(), func_nodes(), - write_history(), // snapshot data structure - loc_func_nodes_map() // shapshot data structure + write_history(), // snapshot data structure + loc_func_nodes_map(), // shapshot data structure + thrd_last_entered_func() // snapshot data structure {} void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) @@ -29,22 +30,26 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) if ( thrd_func_list->size() <= id ) { uint oldsize = thrd_func_list->size(); thrd_func_list->resize( id + 1 ); + thrd_func_act_lists->resize( id + 1 ); + for (uint i = oldsize; i < id + 1; i++) { new (&(*thrd_func_list)[i]) func_id_list_t(); // push 0 as a dummy function id to a void seg fault (*thrd_func_list)[i].push_back(0); - } - thrd_func_act_lists->resize( id + 1 ); - for (uint i = oldsize; i < id + 1; i++) { (*thrd_func_act_lists)[i] = new SnapList(); } } + while ( thrd_last_entered_func.size() <= id ) { + thrd_last_entered_func.push_back(0); // 0 is a dummy function id + } + SnapList * 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(); + uint32_t last_entered_func_id = thrd_last_entered_func[id]; + thrd_last_entered_func[id] = func_id; (*thrd_func_list)[id].push_back(func_id); if ( func_nodes.size() <= func_id ) @@ -55,8 +60,8 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t 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]; + if (last_entered_func_id != 0) { + FuncNode * last_func_node = func_nodes[last_entered_func_id]; add_edges_between(last_func_node, func_node); } } @@ -237,11 +242,23 @@ void ModelHistory::set_new_exec_flag() 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() +void ModelHistory::dump_func_node_graph() { + model_print("digraph func_node_graph {\n"); + for (uint i = 1; i < func_nodes.size(); i++) { + FuncNode * node = func_nodes[i]; + ModelList * out_edges = node->get_out_edges(); + + model_print("\"%p\" [label=\"%s\"]\n", node, node->get_func_name()); + mllnode * it; + for (it = out_edges->begin(); it != NULL; it = it->getNext()) { + FuncNode * other = it->getVal(); + model_print("\"%p\" -> \"%p\"\n", node, other); + } + } + model_print("}\n"); } void ModelHistory::print_func_node() @@ -258,15 +275,5 @@ void ModelHistory::print_func_node() FuncInst *inst = it->getVal(); model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position()); } -/* - func_inst_list_mt * inst_list = funcNode->get_inst_list(); - - model_print("function %s has following actions\n", funcNode->get_func_name()); - func_inst_list_mt::iterator it; - for (it = inst_list->begin(); it != inst_list->end(); it++) { - FuncInst *inst = *it; - model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position()); - } -*/ } } diff --git a/history.h b/history.h index 7a01d402..ee07ba4f 100644 --- a/history.h +++ b/history.h @@ -32,7 +32,7 @@ public: void add_to_loc_func_nodes_map(void * location, FuncNode * node); void set_new_exec_flag(); - void print_write(); + void dump_func_node_graph(); void print_func_node(); MEMALLOC @@ -52,6 +52,7 @@ private: /* Map a location to FuncNodes that may read from it */ HashTable *, uintptr_t, 4> loc_func_nodes_map; + SnapVector thrd_last_entered_func; void add_edges_between(FuncNode * prev_node, FuncNode * next_node); }; -- 2.34.1