From d24f2b5cb874f2ebe2a27333a16721821ba737d4 Mon Sep 17 00:00:00 2001 From: weiyu Date: Thu, 10 Oct 2019 11:50:04 -0700 Subject: [PATCH] Avoid using a HashTable to associate FuncInsts with ModelActions; a slight improvement in performance --- funcinst.cc | 17 ++++++++++++++++- funcinst.h | 6 ++++++ funcnode.cc | 16 ++++++++-------- funcnode.h | 5 ++++- 4 files changed, 34 insertions(+), 10 deletions(-) diff --git a/funcinst.cc b/funcinst.cc index c89284a7..4fcf0e7c 100644 --- a/funcinst.cc +++ b/funcinst.cc @@ -3,7 +3,8 @@ FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) : single_location(true), - execution_number(model->get_execution_number()) + execution_number(model->get_execution_number()), + marker(0) /* The marker for FuncNode starts from 1 */ { ASSERT(act); ASSERT(func_node); @@ -46,6 +47,20 @@ bool FuncInst::add_succ(FuncInst * other) return true; } +void FuncInst::set_associated_act(ModelAction * act, uint32_t marker) +{ + associated_act = act; + this->marker = marker; +} + +ModelAction * FuncInst::get_associated_act(uint32_t marker) +{ + if (marker == this->marker) + return associated_act; + else + return NULL; +} + /* FuncInst * FuncInst::search_in_collision(ModelAction *act) { diff --git a/funcinst.h b/funcinst.h index ae3aa093..fe4adb48 100644 --- a/funcinst.h +++ b/funcinst.h @@ -39,6 +39,9 @@ public: void set_execution_number(int new_number) { execution_number = new_number; } int get_execution_number() { return execution_number; } + void set_associated_act(ModelAction * act, uint32_t marker); + ModelAction * get_associated_act(uint32_t marker); + void print(); MEMALLOC @@ -61,6 +64,9 @@ private: bool single_location; int execution_number; + ModelAction * associated_act; + uint32_t marker; + /* Currently not in use. May remove this field later * * collisions store a list of FuncInsts with the same position diff --git a/funcnode.cc b/funcnode.cc index 138f18fd..05974d78 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -10,6 +10,7 @@ FuncNode::FuncNode(ModelHistory * history) : history(history), exit_count(0), + marker(1), func_inst_map(), inst_list(), entry_insts(), @@ -163,7 +164,6 @@ void FuncNode::update_tree(action_list_t * act_list) write_locations->add(loc); history->update_loc_wr_func_nodes_map(loc, this); } - } if (act->is_read()) { @@ -233,6 +233,8 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) if (act_list == NULL || act_list->size() == 0) return; + incr_marker(); + /* Map a FuncInst to the its predicate */ HashTable inst_pred_map(128); @@ -242,16 +244,16 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) /* Only need to store the locations of read actions */ HashTable loc_act_map(128); - HashTable inst_act_map(128); sllnode *it = act_list->begin(); Predicate * curr_pred = predicate_tree_entry; while (it != NULL) { ModelAction * next_act = it->getVal(); FuncInst * next_inst = get_inst(next_act); + next_inst->set_associated_act(next_act, marker); SnapVector unset_predicates = SnapVector(); - bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &inst_act_map, &unset_predicates); + bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &unset_predicates); // A branch with unset predicate expression is detected if (!branch_found && unset_predicates.size() != 0) { @@ -299,7 +301,6 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) loc_act_map.put(next_act->get_location(), next_act); } - inst_act_map.put(next_inst, next_act); inst_pred_map.put(next_inst, curr_pred); if (!inst_id_map.contains(next_inst)) inst_id_map.put(next_inst, inst_counter++); @@ -312,9 +313,8 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) * contains next_inst and the correct predicate. * @return true if branch found, false otherwise. */ -bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act, - HashTable * inst_act_map, - SnapVector * unset_predicates) +bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, + ModelAction * next_act, SnapVector * unset_predicates) { /* Check if a branch with func_inst and corresponding predicate exists */ bool branch_found = false; @@ -349,7 +349,7 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, Model ModelAction * last_act; to_be_compared = pred_expression->func_inst; - last_act = inst_act_map->get(to_be_compared); + last_act = to_be_compared->get_associated_act(marker); last_read = last_act->get_reads_from_value(); next_read = next_act->get_reads_from_value(); diff --git a/funcnode.h b/funcnode.h index 04665c5c..7e7635ca 100644 --- a/funcnode.h +++ b/funcnode.h @@ -34,7 +34,7 @@ public: void update_tree(action_list_t * act_list); void update_inst_tree(func_inst_list_t * inst_list); void update_predicate_tree(action_list_t * act_list); - bool follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act, HashTable * inst_act_map, SnapVector * unset_predicates); + bool follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act, SnapVector * unset_predicates); void incr_exit_count() { exit_count++; } uint32_t get_exit_count() { return exit_count; } @@ -70,6 +70,9 @@ private: Predicate * predicate_tree_entry; // a dummy node whose children are the real entries uint32_t exit_count; + uint32_t marker; + + void incr_marker() { marker++; } /* Use source line number as the key of hashtable, to check if * atomic operation with this line number has been added or not -- 2.34.1