From 5379cc6b0f28d0563a51ad2f2069db83ec33ccac Mon Sep 17 00:00:00 2001 From: weiyu Date: Tue, 6 Aug 2019 19:02:42 -0700 Subject: [PATCH] Split FuncNode::get_or_add_inst into two separate functions. Call add_inst inside process_action so that func_insts corresponding to ATOMIC RMWRCAS actions are created before those actions are converted to ATOMIC RMWR or ATOMIC READ --- funcnode.cc | 123 +++++++++++++++++++++++++++++++++++++--------------- funcnode.h | 3 +- history.cc | 22 ++++++---- 3 files changed, 102 insertions(+), 46 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index 44c69e22..a0f1f33b 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -11,11 +11,12 @@ FuncNode::FuncNode() : {} /* Check whether FuncInst with the same type, position, and location - * as act has been added to func_inst_map or not. If so, return it; - * if not, add it and return it. + * as act has been added to func_inst_map or not. If not, add it. * - * @return FuncInst with the same type, position, and location as act */ -FuncInst * FuncNode::get_or_add_inst(ModelAction *act) + * Note: currently, actions with the same position are filtered out by process_action, + * so the collision list of FuncInst is not used. May remove it later. + */ +void FuncNode::add_inst(ModelAction *act) { ASSERT(act); const char * position = act->get_position(); @@ -24,7 +25,7 @@ FuncInst * FuncNode::get_or_add_inst(ModelAction *act) * actions are not tagged with their source line numbers */ if (position == NULL) - return NULL; + return; if ( func_inst_map.contains(position) ) { FuncInst * inst = func_inst_map.get(position); @@ -33,29 +34,56 @@ FuncInst * FuncNode::get_or_add_inst(ModelAction *act) // model_print("action with a different type occurs at line number %s\n", position); FuncInst * func_inst = inst->search_in_collision(act); - if (func_inst != NULL) { - // return the FuncInst found in the collision list - return func_inst; - } + if (func_inst != NULL) + return; func_inst = new FuncInst(act, this); inst->get_collisions()->push_back(func_inst); inst_list.push_back(func_inst); // delete? - - return func_inst; } - return inst; + return; } FuncInst * func_inst = new FuncInst(act, this); func_inst_map.put(position, func_inst); inst_list.push_back(func_inst); +} - return func_inst; +/* Get the FuncInst with the same type, position, and location + * as act + * + * @return FuncInst with the same type, position, and location as act */ +FuncInst * FuncNode::get_inst(ModelAction *act) +{ + ASSERT(act); + const char * position = act->get_position(); + + /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK + * actions are not tagged with their source line numbers + */ + if (position == NULL) + return NULL; + + FuncInst * inst = func_inst_map.get(position); + if (inst == NULL) + return NULL; + + action_type inst_type = inst->get_type(); + action_type act_type = act->get_type(); + + // else if branch: an RMWRCAS action is converted to a RMW or READ action + if (inst_type == act_type) + return inst; + else if (inst_type == ATOMIC_RMWRCAS && + (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) + return inst; + + return NULL; } + void FuncNode::add_entry_inst(FuncInst * inst) { if (inst == NULL) @@ -88,18 +116,15 @@ void FuncNode::update_tree(action_list_t * act_list) for (sllnode * it = act_list->begin(); it != NULL; it = it->getNext()) { ModelAction * act = it->getVal(); - FuncInst * func_inst = get_or_add_inst(act); + FuncInst * func_inst = get_inst(act); if (func_inst == NULL) continue; inst_list.push_back(func_inst); -/* if (!predicate_tree_initialized) { - model_print("position: %s ", act->get_position()); - act->print(); - } -*/ +// model_print("position: %s ", act->get_position()); +// act->print(); if (func_inst->is_read()) { read_inst_list.push_back(func_inst); @@ -200,12 +225,11 @@ void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTablesize() == 0) return; -/* if (predicate_tree_initialized) { return; } predicate_tree_initialized = true; -*/ + // maybe restrict the size of hashtable to save calloc time HashTable loc_inst_map(64); @@ -233,28 +257,55 @@ void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTablegetNext(); while (it != NULL) { FuncInst * curr_inst = it->getVal(); - bool child_found = false; + bool branch_found = false; - /* check if a child with the same func_inst and corresponding predicate exists */ - ModelVector * children = curr_pred->get_children(); - for (uint i = 0; i < children->size(); i++) { - Predicate * child = (*children)[i]; - if (child->get_func_inst() != curr_inst) + /* check if a branch with the same func_inst and corresponding predicate exists */ + ModelVector * branches = curr_pred->get_children(); + for (uint i = 0; i < branches->size(); i++) { + Predicate * branch = (*branches)[i]; + if (branch->get_func_inst() != curr_inst) continue; - PredExprSet * pred_expressions = child->get_pred_expressions(); + PredExprSet * pred_expressions = branch->get_pred_expressions(); - /* no predicate, follow the only child */ + /* no predicate, follow the only branch */ if (pred_expressions->getSize() == 0) { - model_print("no predicate exists: "); - curr_inst->print(); - curr_pred = child; - child_found = true; + model_print("no predicate exists: "); curr_inst->print(); + curr_pred = branch; + branch_found = true; break; } + + PredExprSetIter * pred_expr_it = pred_expressions->iterator(); + while (pred_expr_it->hasNext()) { + pred_expr * pred_expression = pred_expr_it->next(); + uint64_t last_read, curr_read; + FuncInst * last_inst; + bool equality; + + switch(pred_expression->token) { + case EQUALITY: + last_inst = loc_inst_map.get(curr_inst->get_location()); + last_read = read_val_map->get(last_inst); + curr_read = read_val_map->get(curr_inst); + equality = (last_read == curr_read); + if (equality == pred_expression->value) { + curr_pred = branch; + model_print("predicate: token: %d, location: %p, value: %d - ", pred_expression->token, pred_expression->location, pred_expression->value); curr_inst->print(); + branch_found = true; + } + break; + case NULLITY: + break; + default: + model_print("unkown predicate token\n"); + break; + } + } + } - if (!child_found) { + if (!branch_found) { if ( loc_inst_map.contains(curr_inst->get_location()) ) { Predicate * new_pred1 = new Predicate(curr_inst); new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true); @@ -283,8 +334,8 @@ void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTablegetNext(); } -// model_print("function %s\n", func_name); -// print_predicate_tree(); + model_print("function %s\n", func_name); + print_predicate_tree(); } diff --git a/funcnode.h b/funcnode.h index a4412c6c..2fe70860 100644 --- a/funcnode.h +++ b/funcnode.h @@ -21,7 +21,8 @@ public: void set_func_id(uint32_t id) { func_id = id; } void set_func_name(const char * name) { func_name = name; } - FuncInst * get_or_add_inst(ModelAction *act); + void add_inst(ModelAction *act); + FuncInst * get_inst(ModelAction *act); HashTable * getFuncInstMap() { return &func_inst_map; } func_inst_list_mt * get_inst_list() { return &inst_list; } diff --git a/history.cc b/history.cc index 0a25caf5..89d11119 100644 --- a/history.cc +++ b/history.cc @@ -128,18 +128,22 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) add_to_write_history(act->get_location(), act->get_write_value()); /* add to curr_inst_list */ - action_list_t * curr_act_list = func_act_lists->back(); - ASSERT(curr_act_list != NULL); + bool second_part_of_rmw = act->is_rmwc() || act->is_rmw(); + if (!second_part_of_rmw) { + action_list_t * curr_act_list = func_act_lists->back(); + ASSERT(curr_act_list != NULL); - ModelAction * last_act; - if (curr_act_list->size() != 0) - last_act = curr_act_list->back(); + ModelAction * last_act; + if (curr_act_list->size() != 0) + last_act = curr_act_list->back(); - /* do not add actions with the same sequence number twice */ - if (last_act != NULL && last_act->get_seq_number() == act->get_seq_number()) - return; + // do not add actions with the same sequence number twice + if (last_act != NULL && last_act->get_seq_number() == act->get_seq_number()) + return; - curr_act_list->push_back(act); + curr_act_list->push_back(act); + func_node->add_inst(act); + } } /* return the FuncNode given its func_id */ -- 2.34.1