X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=funcnode.cc;h=663447bf17fed96f8eea6e8cb02e48d84595c828;hp=d328a4c5d24f6753fe0faf9338e153bc7284072a;hb=57748ff26d916528ba0df0b1d2c699a901386d5f;hpb=70acabc306bc3014b3698e394908faf23a66a0b8 diff --git a/funcnode.cc b/funcnode.cc index d328a4c5..663447bf 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -1,8 +1,17 @@ +#include "action.h" +#include "history.h" #include "funcnode.h" +#include "funcinst.h" +#include "predicate.h" +#include "concretepredicate.h" + +#include "model.h" +#include FuncNode::FuncNode(ModelHistory * history) : history(history), exit_count(0), + marker(1), func_inst_map(), inst_list(), entry_insts(), @@ -13,13 +22,16 @@ FuncNode::FuncNode(ModelHistory * history) : predicate_tree_entry = new Predicate(NULL, true); predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true); - // Memories that are reclaimed after each execution + predicate_tree_exit = new Predicate(NULL, false, true); + predicate_tree_exit->alloc_pre_exit_predicates(); + predicate_tree_exit->set_depth(MAX_DEPTH); + + /* Snapshot data structures below */ action_list_buffer = new SnapList(); read_locations = new loc_set_t(); write_locations = new loc_set_t(); - val_loc_map = new HashTable(); + val_loc_map = new HashTable(); loc_may_equal_map = new HashTable(); - thrd_inst_act_map = new SnapVector(); //values_may_read_from = new value_set_t(); } @@ -27,26 +39,17 @@ FuncNode::FuncNode(ModelHistory * history) : /* Reallocate snapshotted memories when new executions start */ void FuncNode::set_new_exec_flag() { - for (mllnode * it = inst_list.begin(); it != NULL; it = it->getNext()) { - FuncInst * inst = it->getVal(); - inst->unset_location(); - } - action_list_buffer = new SnapList(); read_locations = new loc_set_t(); write_locations = new loc_set_t(); - val_loc_map = new HashTable(); + val_loc_map = new HashTable(); loc_may_equal_map = new HashTable(); - thrd_inst_act_map = new SnapVector(); //values_may_read_from = new value_set_t(); } /* Check whether FuncInst with the same type, position, and location * as act has been added to func_inst_map or not. If not, add it. - * - * 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) { @@ -59,27 +62,54 @@ void FuncNode::add_inst(ModelAction *act) if (position == NULL) return; - if ( func_inst_map.contains(position) ) { - FuncInst * inst = func_inst_map.get(position); + FuncInst * func_inst = func_inst_map.get(position); - ASSERT(inst->get_type() == act->get_type()); + /* This position has not been inserted into hashtable before */ + if (func_inst == NULL) { + func_inst = create_new_inst(act); + func_inst_map.put(position, func_inst); + return; + } - // locations are set to NULL when new executions start - if (inst->get_location() == NULL) - inst->set_location(act->get_location()); + /* Volatile variables that use ++ or -- syntax may result in read and write actions with the same position */ + if (func_inst->get_type() != act->get_type()) { + FuncInst * collision_inst = func_inst->search_in_collision(act); + + if (collision_inst == NULL) { + collision_inst = create_new_inst(act); + func_inst->add_to_collision(collision_inst); + return; + } else { + func_inst = collision_inst; + } + } - if (inst->get_location() != act->get_location()) - inst->not_single_location(); + ASSERT(func_inst->get_type() == act->get_type()); + int curr_execution_number = model->get_execution_number(); - return; + /* Reset locations when new executions start */ + if (func_inst->get_execution_number() != curr_execution_number) { + func_inst->set_location(act->get_location()); + func_inst->set_execution_number(curr_execution_number); } + /* Mark the memory location of such inst as not unique */ + if (func_inst->get_location() != act->get_location()) + func_inst->not_single_location(); +} + +FuncInst * FuncNode::create_new_inst(ModelAction * act) +{ FuncInst * func_inst = new FuncInst(act, this); + int exec_num = model->get_execution_number(); + func_inst->set_execution_number(exec_num); - 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 * @@ -102,14 +132,18 @@ FuncInst * FuncNode::get_inst(ModelAction *act) 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) + if (inst_type == act_type) { return inst; + } + /* RMWRCAS actions are converted to RMW or READ actions */ else if (inst_type == ATOMIC_RMWRCAS && - (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) + (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) { return inst; - - return NULL; + } + /* Return the FuncInst in the collision list */ + else { + return inst->search_in_collision(act); + } } @@ -119,7 +153,7 @@ void FuncNode::add_entry_inst(FuncInst * inst) return; mllnode * it; - for (it = entry_insts.begin(); it != NULL; it = it->getNext()) { + for (it = entry_insts.begin();it != NULL;it = it->getNext()) { if (inst == it->getVal()) return; } @@ -128,7 +162,7 @@ void FuncNode::add_entry_inst(FuncInst * inst) } /** - * @brief Convert ModelAdtion list to FuncInst list + * @brief Convert ModelAdtion list to FuncInst list * @param act_list A list of ModelActions */ void FuncNode::update_tree(action_list_t * act_list) @@ -136,13 +170,13 @@ void FuncNode::update_tree(action_list_t * act_list) if (act_list == NULL || act_list->size() == 0) return; - HashTable * write_history = history->getWriteHistory(); + HashTable * write_history = history->getWriteHistory(); /* build inst_list from act_list for later processing */ func_inst_list_t inst_list; action_list_t rw_act_list; - for (sllnode * it = act_list->begin(); it != NULL; it = it->getNext()) { + for (sllnode * it = act_list->begin();it != NULL;it = it->getNext()) { ModelAction * act = it->getVal(); FuncInst * func_inst = get_inst(act); void * loc = act->get_location(); @@ -160,7 +194,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()) { @@ -178,7 +211,7 @@ void FuncNode::update_tree(action_list_t * act_list) read_locations->add(loc); value_set_t * write_values = write_history->get(loc); add_to_val_loc_map(write_values, loc); - history->update_loc_func_nodes_map(loc, this); + history->update_loc_rd_func_nodes_map(loc, this); } } } @@ -192,7 +225,7 @@ void FuncNode::update_tree(action_list_t * act_list) // print_predicate_tree(); } -/** +/** * @brief Link FuncInsts in inst_list - add one FuncInst to another's predecessors and successors * @param inst_list A list of FuncInsts */ @@ -230,6 +263,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); @@ -239,16 +274,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) { @@ -276,7 +311,6 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) curr_pred->add_backedge(back_pred); curr_pred = back_pred; - continue; } } @@ -296,27 +330,31 @@ 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++); it = it->getNext(); + curr_pred->incr_expl_count(); + } + + if (curr_pred->get_exit() == NULL) { + // Exit predicate is unset yet + curr_pred->set_exit(predicate_tree_exit); } } /* Given curr_pred and next_inst, find the branch following curr_pred that - * contains next_inst and the correct predicate. + * 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 */ + /* 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++) { + for (uint i = 0;i < branches->size();i++) { Predicate * branch = (*branches)[i]; if (branch->get_func_inst() != next_inst) continue; @@ -324,6 +362,7 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, Model /* Check against predicate expressions */ bool predicate_correct = true; PredExprSet * pred_expressions = branch->get_pred_expressions(); + PredExprSetIter * pred_expr_it = pred_expressions->iterator(); /* Only read and rmw actions my have unset predicate expressions */ if (pred_expressions->getSize() == 0) { @@ -331,26 +370,34 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, Model unset_predicates->push_back(branch); } - SnapVector concrete_exprs = branch->evaluate(inst_act_map); - for (uint i = 0; i < concrete_exprs.size(); i++) { - struct concrete_pred_expr concrete = concrete_exprs[i]; - uint64_t next_read; + while (pred_expr_it->hasNext()) { + pred_expr * pred_expression = pred_expr_it->next(); + uint64_t last_read, next_read; bool equality; - switch (concrete.token) { + switch(pred_expression->token) { case NOPREDICATE: predicate_correct = true; break; case EQUALITY: + FuncInst * to_be_compared; + ModelAction * last_act; + + to_be_compared = pred_expression->func_inst; + 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(); - equality = (next_read == concrete.value); - if (equality != concrete.equality) + equality = (last_read == next_read); + if (equality != pred_expression->value) predicate_correct = false; + break; case NULLITY: next_read = next_act->get_reads_from_value(); - equality = ((void*)next_read == NULL); - if (equality != concrete.equality) + // TODO: implement likely to be null + equality = ( (void*) (next_read & 0xffffffff) == NULL); + if (equality != pred_expression->value) predicate_correct = false; break; default: @@ -372,8 +419,8 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, Model /* Infer predicate expressions, which are generated in FuncNode::generate_predicates */ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, - HashTable * loc_act_map, - SnapVector * half_pred_expressions) +HashTable * loc_act_map, +SnapVector * half_pred_expressions) { void * loc = next_act->get_location(); @@ -384,7 +431,7 @@ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, FuncInst * last_inst = get_inst(last_act); struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst); half_pred_expressions->push_back(expression); - } else if ( next_inst->is_single_location() ){ + } else if ( next_inst->is_single_location() ) { loc_set_t * loc_may_equal = loc_may_equal_map->get(loc); if (loc_may_equal != NULL) { @@ -418,7 +465,7 @@ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, /* Able to generate complex predicates when there are multiple predciate expressions */ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, - SnapVector * half_pred_expressions) +SnapVector * half_pred_expressions) { if (half_pred_expressions->size() == 0) { Predicate * new_pred = new Predicate(next_inst); @@ -446,11 +493,11 @@ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, predicates[0]->add_predicate_expr(half_expr->token, half_expr->func_inst, true); predicates[1]->add_predicate_expr(half_expr->token, half_expr->func_inst, false); - for (uint i = 1; i < half_pred_expressions->size(); i++) { + for (uint i = 1;i < half_pred_expressions->size();i++) { half_expr = (*half_pred_expressions)[i]; uint old_size = predicates.size(); - for (uint j = 0; j < old_size; j++) { + for (uint j = 0;j < old_size;j++) { Predicate * pred = predicates[j]; Predicate * new_pred = new Predicate(next_inst); new_pred->copy_predicate_expr(pred); @@ -462,14 +509,14 @@ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, } } - for (uint i = 0; i < predicates.size(); i++) { + for (uint i = 0;i < predicates.size();i++) { Predicate * pred= predicates[i]; (*curr_pred)->add_child(pred); pred->set_parent(*curr_pred); } /* Free memories allocated by infer_predicate */ - for (uint i = 0; i < half_pred_expressions->size(); i++) { + for (uint i = 0;i < half_pred_expressions->size();i++) { struct half_pred_expr * tmp = (*half_pred_expressions)[i]; snapshot_free(tmp); } @@ -579,13 +626,14 @@ Predicate * FuncNode::get_predicate_tree_position(thread_id_t tid) void FuncNode::init_inst_act_map(thread_id_t tid) { int thread_id = id_to_int(tid); + SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); uint old_size = thrd_inst_act_map->size(); if (thrd_inst_act_map->size() <= (uint) thread_id) { uint new_size = thread_id + 1; thrd_inst_act_map->resize(new_size); - for (uint i = old_size; i < new_size; i++) + for (uint i = old_size;i < new_size;i++) (*thrd_inst_act_map)[i] = new inst_act_map_t(128); } } @@ -594,6 +642,8 @@ void FuncNode::init_inst_act_map(thread_id_t tid) void FuncNode::reset_inst_act_map(thread_id_t tid) { int thread_id = id_to_int(tid); + SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + inst_act_map_t * map = (*thrd_inst_act_map)[thread_id]; map->reset(); } @@ -601,6 +651,8 @@ void FuncNode::reset_inst_act_map(thread_id_t tid) void FuncNode::update_inst_act_map(thread_id_t tid, ModelAction * read_act) { int thread_id = id_to_int(tid); + SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + inst_act_map_t * map = (*thrd_inst_act_map)[thread_id]; FuncInst * read_inst = get_inst(read_act); map->put(read_inst, read_act); @@ -609,6 +661,8 @@ void FuncNode::update_inst_act_map(thread_id_t tid, ModelAction * read_act) inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid) { int thread_id = id_to_int(tid); + SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + return (*thrd_inst_act_map)[thread_id]; } @@ -628,28 +682,116 @@ void FuncNode::add_out_edge(FuncNode * other) } } -void FuncNode::print_predicate_tree() +/* Compute the distance between this FuncNode and the target node. + * Return -1 if the target node is unreachable or the actual distance + * is greater than max_step. + */ +int FuncNode::compute_distance(FuncNode * target, int max_step) { - model_print("digraph function_%s {\n", func_name); - predicate_tree_entry->print_pred_subtree(); - model_print("}\n"); // end of graph + if (target == NULL) + return -1; + else if (target == this) + return 0; + + SnapList queue; + HashTable distances(128); + + queue.push_back(this); + distances.put(this, 0); + + while (!queue.empty()) { + FuncNode * curr = queue.front(); + queue.pop_front(); + int dist = distances.get(curr); + + if (max_step <= dist) + return -1; + + ModelList * outEdges = curr->get_out_edges(); + mllnode * it; + for (it = outEdges->begin();it != NULL;it = it->getNext()) { + FuncNode * out_node = it->getVal(); + + /* This node has not been visited before */ + if ( !distances.contains(out_node) ) { + if (out_node == target) + return dist + 1; + + queue.push_back(out_node); + distances.put(out_node, dist + 1); + } + } + } + + /* Target node is unreachable */ + return -1; } -void FuncNode::print_val_loc_map() +void FuncNode::assign_base_score() { -/* - value_set_iter * val_it = values_may_read_from->iterator(); - while (val_it->hasNext()) { - uint64_t value = val_it->next(); - model_print("val %llx: ", value); - - loc_set_t * locations = val_loc_map->get(value); - loc_set_iter * loc_it = locations->iterator(); - while (loc_it->hasNext()) { - void * location = loc_it->next(); - model_print("%p ", location); + SnapVector leaves; + SnapList queue; + queue.push_front(predicate_tree_entry); + + // assign leaf score + while ( !queue.empty() ) { + Predicate * node = queue.back(); + queue.pop_back(); + + ModelVector * children = node->get_children(); + if (children->empty()) { + node->set_weight(1); + leaves.push_back(node); } - model_print("\n"); + + for (uint i = 0; i < children->size(); i++) + queue.push_front( (*children)[i] ); } -*/ + + // assign scores for internal nodes; + while ( !leaves.empty() ) { + Predicate * leaf = leaves.back(); + leaves.pop_back(); + + Predicate * curr = leaf->get_parent(); + while (curr != NULL) { + if (curr->get_weight() != 0) { + // Has been exlpored + break; + } + + ModelVector * children = curr->get_children(); + double weight_sum = 0; + bool has_unassigned_node = false; + + for (uint i = 0; i < children->size(); i++) { + Predicate * child = (*children)[i]; + + // If a child has unassigned weight + double weight = child->get_weight(); + if (weight == 0) { + has_unassigned_node = true; + break; + } else + weight_sum += weight; + } + + if (!has_unassigned_node) { + double average_weight = (double) weight_sum / (double) children->size(); + double weight = average_weight * pow(0.9, curr->get_depth()); + curr->set_weight(weight); + } else + break; + + curr = curr->get_parent(); + } + } +} + +void FuncNode::print_predicate_tree() +{ + model_print("digraph function_%s {\n", func_name); + predicate_tree_entry->print_pred_subtree(); + predicate_tree_exit->print_predicate(); + model_print("}\n"); // end of graph }