X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=funcnode.cc;h=188ed173c3c0bfda3bc60fad06c7d781fc4f5fbc;hp=c24449ff908a5f348bf4d4ceb2a53219d5a9d7d2;hb=9a2ba97d13c76e9048ba7c499b3cbca0d02a84ca;hpb=493376d8483562a85a590b9dfa890a27669ca6b4 diff --git a/funcnode.cc b/funcnode.cc index c24449ff..188ed173 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -1,22 +1,21 @@ #include "funcnode.h" -#include -#include "common.h" FuncNode::FuncNode() : predicate_tree_initialized(false), + predicate_tree_entry(new Predicate(NULL, true)), func_inst_map(), inst_list(), entry_insts(), - thrd_read_map(), - predicate_tree_entry() + thrd_read_map() {} /* 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(); @@ -25,7 +24,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); @@ -34,29 +33,58 @@ 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; + +// ASSERT(inst->get_location() == act->get_location()); + + 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) @@ -84,32 +112,26 @@ void FuncNode::update_tree(action_list_t * act_list) /* build inst_list from act_list for later processing */ func_inst_list_t inst_list; - func_inst_list_t read_inst_list; - HashTable read_val_map; + action_list_t read_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); - read_val_map.put(func_inst, act->get_reads_from_value()); - } + if (func_inst->is_read()) + read_act_list.push_back(act); } update_inst_tree(&inst_list); - init_predicate_tree(&read_inst_list, &read_val_map); + update_predicate_tree(&read_act_list); } /** @@ -172,13 +194,13 @@ void FuncNode::store_read(ModelAction * act, uint32_t tid) uint64_t FuncNode::query_last_read(void * location, uint32_t tid) { if (thrd_read_map.size() <= tid) - return 0xdeadbeef; + return VALUE_NONE; read_map_t * read_map = thrd_read_map[tid]; /* last read value not found */ if ( !read_map->contains(location) ) - return 0xdeadbeef; + return VALUE_NONE; uint64_t read_val = read_map->get(location); return read_val; @@ -196,74 +218,149 @@ void FuncNode::clear_read_map(uint32_t tid) thrd_read_map[tid]->reset(); } -void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTable * read_val_map) +void FuncNode::update_predicate_tree(action_list_t * act_list) { - if (inst_list == NULL || inst_list->size() == 0) + if (act_list == NULL || act_list->size() == 0) return; - +/* if (predicate_tree_initialized) { return; } - predicate_tree_initialized = true; +*/ + /* map a FuncInst to the parent of its predicate */ + HashTable inst_pred_map(128); + HashTable loc_act_map(128); - // maybe restrict the size of hashtable to save calloc time - HashTable loc_inst_map; - - sllnode *it = inst_list->begin(); - FuncInst * entry_inst = it->getVal(); - - /* entry instruction has no predicate expression */ - Predicate * curr_pred = new Predicate(entry_inst); - predicate_tree_entry.add(curr_pred); - loc_inst_map.put(entry_inst->get_location(), entry_inst); + sllnode *it = act_list->begin(); + Predicate * curr_pred = predicate_tree_entry; - it = it->getNext(); while (it != NULL) { - FuncInst * curr_inst = it->getVal(); - 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); - - Predicate * new_pred2 = new Predicate(curr_inst); - new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false); - - curr_pred->add_child(new_pred1); - curr_pred->add_child(new_pred2); - - FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location()); - - uint64_t last_read = read_val_map->get(last_inst); - if ( last_read == read_val_map->get(curr_inst) ) - curr_pred = new_pred1; - else - curr_pred = new_pred2; - } else { - Predicate * new_pred = new Predicate(curr_inst); - curr_pred->add_child(new_pred); - curr_pred = new_pred; + ModelAction * next_act = it->getVal(); + FuncInst * next_inst = get_inst(next_act); + Predicate * old_pred = curr_pred; + + bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &loc_act_map); + + // check back edges + if (!branch_found) { + Predicate * back_pred = curr_pred->get_backedge(); + if (back_pred != NULL) { + curr_pred = back_pred; + continue; + } + + if (inst_pred_map.contains(next_inst)) { + back_pred = inst_pred_map.get(next_inst); + curr_pred->set_backedge(back_pred); + curr_pred = back_pred; + continue; + } } - loc_inst_map.put(curr_inst->get_location(), curr_inst); + if (!inst_pred_map.contains(next_inst)) + inst_pred_map.put(next_inst, old_pred); + + if (!branch_found) { + if ( loc_act_map.contains(next_act->get_location()) ) { + Predicate * new_pred1 = new Predicate(next_inst); + new_pred1->add_predicate(EQUALITY, next_act->get_location(), true); + + Predicate * new_pred2 = new Predicate(next_inst); + new_pred2->add_predicate(EQUALITY, next_act->get_location(), false); + + curr_pred->add_child(new_pred1); + curr_pred->add_child(new_pred2); + //new_pred1->add_parent(curr_pred); + //new_pred2->add_parent(curr_pred); + + ModelAction * last_act = loc_act_map.get(next_act->get_location()); + uint64_t last_read = last_act->get_reads_from_value(); + uint64_t next_read = next_act->get_reads_from_value(); + + if ( last_read == next_read ) + curr_pred = new_pred1; + else + curr_pred = new_pred2; + } else { + Predicate * new_pred = new Predicate(next_inst); + curr_pred->add_child(new_pred); + //new_pred->add_parent(curr_pred); + + curr_pred = new_pred; + } + } + loc_act_map.put(next_act->get_location(), next_act); it = it->getNext(); } - model_print("function %s\n", func_name); - print_predicate_tree(); +// model_print("function %s\n", func_name); +// print_predicate_tree(); } +/* Given curr_pred and next_inst, find the branch following curr_pred that 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 * loc_act_map) +{ + /* check if a branch with func_inst and corresponding predicate exists */ + bool branch_found = false; + ModelVector * branches = (*curr_pred)->get_children(); + for (uint i = 0; i < branches->size(); i++) { + Predicate * branch = (*branches)[i]; + if (branch->get_func_inst() != next_inst) + continue; + + PredExprSet * pred_expressions = branch->get_pred_expressions(); + + /* no predicate, follow the only branch */ + if (pred_expressions->getSize() == 0) { +// model_print("no predicate exists: "); next_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, next_read; + ModelAction * last_act; + bool equality; + + switch(pred_expression->token) { + case EQUALITY: + last_act = loc_act_map->get(next_act->get_location()); + last_read = last_act->get_reads_from_value(); + next_read = next_act->get_reads_from_value(); + + equality = (last_read == next_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); next_inst->print(); + branch_found = true; + } + break; + case NULLITY: + break; + default: + model_print("unkown predicate token\n"); + break; + } + } + + } + + return branch_found; +} void FuncNode::print_predicate_tree() { model_print("digraph function_%s {\n", func_name); - HSIterator * it; - it = predicate_tree_entry.iterator(); - - while (it->hasNext()) { - Predicate * p = it->next(); - p->print_pred_subtree(); - } + predicate_tree_entry->print_pred_subtree(); model_print("}\n"); // end of graph }