X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=funcnode.cc;h=55785fa89ca6060caab68d8a3d50710f43c073b2;hp=5bb73b9868765a534515dd461f6ed954e2911f93;hb=251ac4b4bf3a9f2d3cfacc1e6618200ca1c431ac;hpb=7d703e06ecec3abb3c173378e18ad6c28eb6f3d7 diff --git a/funcnode.cc b/funcnode.cc index 5bb73b98..55785fa8 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -6,17 +6,28 @@ #include "concretepredicate.h" #include "model.h" +#include "execution.h" +#include "newfuzzer.h" #include FuncNode::FuncNode(ModelHistory * history) : + func_id(0), + func_name(NULL), history(history), - exit_count(0), + inst_counter(1), marker(1), + exit_count(0), + thrd_markers(), + thrd_recursion_depth(), func_inst_map(), inst_list(), entry_insts(), - predicate_tree_position(), - predicate_leaves(), + thrd_inst_pred_maps(), + thrd_inst_id_maps(), + thrd_loc_inst_maps(), + likely_null_set(), + thrd_predicate_tree_position(), + thrd_predicate_trace(), edge_table(32), out_edges() { @@ -27,7 +38,6 @@ FuncNode::FuncNode(ModelHistory * history) : 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(); @@ -39,7 +49,6 @@ FuncNode::FuncNode(ModelHistory * history) : /* Reallocate snapshotted memories when new executions start */ void FuncNode::set_new_exec_flag() { - action_list_buffer = new SnapList(); read_locations = new loc_set_t(); write_locations = new loc_set_t(); val_loc_map = new HashTable(); @@ -146,7 +155,6 @@ FuncInst * FuncNode::get_inst(ModelAction *act) } } - void FuncNode::add_entry_inst(FuncInst * inst) { if (inst == NULL) @@ -161,68 +169,90 @@ void FuncNode::add_entry_inst(FuncInst * inst) entry_insts.push_back(inst); } +void FuncNode::function_entry_handler(thread_id_t tid) +{ + init_marker(tid); + init_local_maps(tid); + init_predicate_tree_data_structure(tid); +} + +void FuncNode::function_exit_handler(thread_id_t tid) +{ + int thread_id = id_to_int(tid); + + reset_local_maps(tid); + + thrd_recursion_depth[thread_id]--; + thrd_markers[thread_id]->pop_back(); + + Predicate * exit_pred = get_predicate_tree_position(tid); + if (exit_pred->get_exit() == NULL) { + // Exit predicate is unset yet + exit_pred->set_exit(predicate_tree_exit); + } + + update_predicate_tree_weight(tid); + reset_predicate_tree_data_structure(tid); + + exit_count++; + //model_print("exit count: %d\n", exit_count); + +// print_predicate_tree(); +} + /** * @brief Convert ModelAdtion list to FuncInst list * @param act_list A list of ModelActions */ -void FuncNode::update_tree(action_list_t * act_list) +void FuncNode::update_tree(ModelAction * act) { - if (act_list == NULL || act_list->size() == 0) + bool should_process = act->is_read() || act->is_write(); + if (!should_process) return; 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; +// func_inst_list_t inst_list; - 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(); + FuncInst * func_inst = get_inst(act); + void * loc = act->get_location(); - if (func_inst == NULL) - continue; + if (func_inst == NULL) + return; - inst_list.push_back(func_inst); - bool act_added = false; +// inst_list.push_back(func_inst); - if (act->is_write()) { - rw_act_list.push_back(act); - act_added = true; - if (!write_locations->contains(loc)) { - write_locations->add(loc); - history->update_loc_wr_func_nodes_map(loc, this); - } + if (act->is_write()) { + if (!write_locations->contains(loc)) { + write_locations->add(loc); + history->update_loc_wr_func_nodes_map(loc, this); } + } - if (act->is_read()) { - if (!act_added) - rw_act_list.push_back(act); - - /* If func_inst may only read_from a single location, then: - * - * The first time an action reads from some location, - * import all the values that have been written to this - * location from ModelHistory and notify ModelHistory - * that this FuncNode may read from this location. - */ - if (!read_locations->contains(loc) && func_inst->is_single_location()) { - read_locations->add(loc); - value_set_t * write_values = write_history->get(loc); - add_to_val_loc_map(write_values, loc); - history->update_loc_rd_func_nodes_map(loc, this); - } + if (act->is_read()) { + /* If func_inst may only read_from a single location, then: + * + * The first time an action reads from some location, + * import all the values that have been written to this + * location from ModelHistory and notify ModelHistory + * that this FuncNode may read from this location. + */ + if (!read_locations->contains(loc) && func_inst->is_single_location()) { + read_locations->add(loc); + value_set_t * write_values = write_history->get(loc); + add_to_val_loc_map(write_values, loc); + history->update_loc_rd_func_nodes_map(loc, this); } - } -// model_print("function %s\n", func_name); -// print_val_loc_map(); + // Keep a has-been-zero-set record + if ( likely_reads_from_null(act) ) + likely_null_set.put(func_inst, true); + } - update_inst_tree(&inst_list); - update_predicate_tree(&rw_act_list); +// update_inst_tree(&inst_list); TODO -// print_predicate_tree(); + update_predicate_tree(act); } /** @@ -258,59 +288,53 @@ void FuncNode::update_inst_tree(func_inst_list_t * inst_list) } } -void FuncNode::update_predicate_tree(action_list_t * act_list) +void FuncNode::update_predicate_tree(ModelAction * next_act) { - if (act_list == NULL || act_list->size() == 0) - return; - - incr_marker(); - - /* Map a FuncInst to the its predicate */ - HashTable inst_pred_map(128); + thread_id_t tid = next_act->get_tid(); + int thread_id = id_to_int(tid); + uint32_t this_marker = thrd_markers[thread_id]->back(); + int recursion_depth = thrd_recursion_depth[thread_id]; - // Number FuncInsts to detect loops - HashTable inst_id_map(128); - uint32_t inst_counter = 0; + loc_inst_map_t * loc_inst_map = thrd_loc_inst_maps[thread_id]->back(); + inst_pred_map_t * inst_pred_map = thrd_inst_pred_maps[thread_id]->back(); + inst_id_map_t * inst_id_map = thrd_inst_id_maps[thread_id]->back(); - /* Only need to store the locations of read actions */ - HashTable loc_act_map(128); + Predicate * curr_pred = get_predicate_tree_position(tid); + NewFuzzer * fuzzer = (NewFuzzer *)model->get_execution()->getFuzzer(); + Predicate * selected_branch = fuzzer->get_selected_child_branch(tid); - sllnode *it = act_list->begin(); - Predicate * curr_pred = predicate_tree_entry; - while (it != NULL) { - ModelAction * next_act = it->getVal(); + bool amended; + while (true) { 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, &unset_predicates); + Predicate * unset_predicate = NULL; + bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &unset_predicate); // A branch with unset predicate expression is detected - if (!branch_found && unset_predicates.size() != 0) { - ASSERT(unset_predicates.size() == 1); - Predicate * one_branch = unset_predicates[0]; - - bool amended = amend_predicate_expr(curr_pred, next_inst, next_act); + if (!branch_found && unset_predicate != NULL) { + amended = amend_predicate_expr(curr_pred, next_inst, next_act); if (amended) continue; else { - curr_pred = one_branch; + curr_pred = unset_predicate; branch_found = true; } } // Detect loops - if (!branch_found && inst_id_map.contains(next_inst)) { + if (!branch_found && inst_id_map->contains(next_inst)) { FuncInst * curr_inst = curr_pred->get_func_inst(); - uint32_t curr_id = inst_id_map.get(curr_inst); - uint32_t next_id = inst_id_map.get(next_inst); + uint32_t curr_id = inst_id_map->get(curr_inst); + uint32_t next_id = inst_id_map->get(next_inst); if (curr_id >= next_id) { - Predicate * old_pred = inst_pred_map.get(next_inst); + Predicate * old_pred = inst_pred_map->get(next_inst); Predicate * back_pred = old_pred->get_parent(); + // Add to the set of backedges curr_pred->add_backedge(back_pred); curr_pred = back_pred; + continue; } } @@ -318,29 +342,38 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) // Generate new branches if (!branch_found) { SnapVector half_pred_expressions; - infer_predicates(next_inst, next_act, &loc_act_map, &half_pred_expressions); + infer_predicates(next_inst, next_act, &half_pred_expressions); generate_predicates(curr_pred, next_inst, &half_pred_expressions); continue; } - if (next_act->is_write()) + if (next_act->is_write()) { curr_pred->set_write(true); + } if (next_act->is_read()) { - loc_act_map.put(next_act->get_location(), next_act); + /* Only need to store the locations of read actions */ + loc_inst_map->put(next_act->get_location(), next_inst); } - inst_pred_map.put(next_inst, curr_pred); - if (!inst_id_map.contains(next_inst)) - inst_id_map.put(next_inst, inst_counter++); + inst_pred_map->put(next_inst, curr_pred); + set_predicate_tree_position(tid, 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(); + add_predicate_to_trace(tid, curr_pred); + if (next_act->is_read()) + next_inst->set_associated_read(tid, recursion_depth, this_marker, next_act->get_reads_from_value()); + + break; } - if (curr_pred->get_exit() == NULL) { - // Exit predicate is unset yet - curr_pred->set_exit(predicate_tree_exit); + // A check + if (next_act->is_read()) { +// if (selected_branch != NULL && !amended) +// ASSERT(selected_branch == curr_pred); } } @@ -349,10 +382,12 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) * @return true if branch found, false otherwise. */ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, -ModelAction * next_act, SnapVector * unset_predicates) + ModelAction * next_act, Predicate ** unset_predicate) { /* Check if a branch with func_inst and corresponding predicate exists */ bool branch_found = false; + thread_id_t tid = next_act->get_tid(); + ModelVector * branches = (*curr_pred)->get_children(); for (uint i = 0;i < branches->size();i++) { Predicate * branch = (*branches)[i]; @@ -362,51 +397,59 @@ ModelAction * next_act, SnapVector * unset_predicates) /* 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) { predicate_correct = false; - unset_predicates->push_back(branch); + + if (*unset_predicate == NULL) + *unset_predicate = branch; + else + ASSERT(false); + + continue; } + 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; bool equality; 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 = (last_read == next_read); - if (equality != pred_expression->value) - predicate_correct = false; - - break; - case NULLITY: - next_read = next_act->get_reads_from_value(); - // TODO: implement likely to be null - equality = ( (void*) (next_read & 0xffffffff) == NULL); - if (equality != pred_expression->value) - predicate_correct = false; - break; - default: + case NOPREDICATE: + predicate_correct = true; + break; + case EQUALITY: + FuncInst * to_be_compared; + to_be_compared = pred_expression->func_inst; + + last_read = get_associated_read(tid, to_be_compared); + if (last_read == VALUE_NONE) + predicate_correct = false; + // ASSERT(last_read != VALUE_NONE); + + next_read = next_act->get_reads_from_value(); + equality = (last_read == next_read); + if (equality != pred_expression->value) predicate_correct = false; - model_print("unkown predicate token\n"); - break; + + break; + case NULLITY: + // TODO: implement likely to be null + equality = likely_reads_from_null(next_act); + if (equality != pred_expression->value) + predicate_correct = false; + break; + default: + predicate_correct = false; + model_print("unkown predicate token\n"); + break; } } + delete pred_expr_it; + if (predicate_correct) { *curr_pred = branch; branch_found = true; @@ -419,16 +462,16 @@ ModelAction * next_act, SnapVector * unset_predicates) /* 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) + SnapVector * half_pred_expressions) { void * loc = next_act->get_location(); + int thread_id = id_to_int(next_act->get_tid()); + loc_inst_map_t * loc_inst_map = thrd_loc_inst_maps[thread_id]->back(); if (next_inst->is_read()) { /* read + rmw */ - if ( loc_act_map->contains(loc) ) { - ModelAction * last_act = loc_act_map->get(loc); - FuncInst * last_inst = get_inst(last_act); + if ( loc_inst_map->contains(loc) ) { + FuncInst * last_inst = loc_inst_map->get(loc); 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() ) { @@ -438,25 +481,24 @@ SnapVector * half_pred_expressions) loc_set_iter * loc_it = loc_may_equal->iterator(); while (loc_it->hasNext()) { void * neighbor = loc_it->next(); - if (loc_act_map->contains(neighbor)) { - ModelAction * last_act = loc_act_map->get(neighbor); - FuncInst * last_inst = get_inst(last_act); + if (loc_inst_map->contains(neighbor)) { + FuncInst * last_inst = loc_inst_map->get(neighbor); struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst); half_pred_expressions->push_back(expression); } } - } - } else { - // next_inst is not single location - uint64_t read_val = next_act->get_reads_from_value(); - // only infer NULLITY predicate when it is actually NULL. - if ( (void*)read_val == NULL) { - struct half_pred_expr * expression = new half_pred_expr(NULLITY, NULL); - half_pred_expressions->push_back(expression); + delete loc_it; } } + + // next_inst is not single location and has been null + bool likely_null = likely_null_set.contains(next_inst); + if ( !next_inst->is_single_location() && likely_null ) { + struct half_pred_expr * expression = new half_pred_expr(NULLITY, NULL); + half_pred_expressions->push_back(expression); + } } else { /* Pure writes */ // TODO: do anything here? @@ -465,17 +507,13 @@ SnapVector * half_pred_expressions) /* 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); curr_pred->add_child(new_pred); new_pred->set_parent(curr_pred); - /* Maintain predicate leaves */ - predicate_leaves.add(new_pred); - predicate_leaves.remove(curr_pred); - /* entry predicates and predicates containing pure write actions * have no predicate expressions */ if ( curr_pred->is_entry_predicate() ) @@ -517,14 +555,8 @@ SnapVector * half_pred_expressions) Predicate * pred= predicates[i]; curr_pred->add_child(pred); pred->set_parent(curr_pred); - - /* Add new predicate leaves */ - predicate_leaves.add(pred); } - /* Remove predicate node that has children */ - predicate_leaves.remove(curr_pred); - /* Free memories allocated by infer_predicate */ for (uint i = 0;i < half_pred_expressions->size();i++) { struct half_pred_expr * tmp = (*half_pred_expressions)[i]; @@ -535,12 +567,21 @@ SnapVector * half_pred_expressions) /* Amend predicates that contain no predicate expressions. Currenlty only amend with NULLITY predicates */ bool FuncNode::amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act) { - // there should only be only child - Predicate * unset_pred = curr_pred->get_children()->back(); - uint64_t read_val = next_act->get_reads_from_value(); + ModelVector * children = curr_pred->get_children(); + + Predicate * unset_pred = NULL; + for (uint i = 0;i < children->size();i++) { + Predicate * child = (*children)[i]; + if (child->get_func_inst() == next_inst) { + unset_pred = child; + break; + } + } + + bool likely_null = likely_null_set.contains(next_inst); // only generate NULLITY predicate when it is actually NULL. - if ( !next_inst->is_single_location() && (void*)read_val == NULL ) { + if ( !next_inst->is_single_location() && likely_null ) { Predicate * new_pred = new Predicate(next_inst); curr_pred->add_child(new_pred); @@ -579,6 +620,8 @@ void FuncNode::add_to_val_loc_map(value_set_t * values, void * loc) uint64_t val = it->next(); add_to_val_loc_map(val, loc); } + + delete it; } void FuncNode::update_loc_may_equal_map(void * new_loc, loc_set_t * old_locations) @@ -607,73 +650,150 @@ void FuncNode::update_loc_may_equal_map(void * new_loc, loc_set_t * old_location } _neighbors->add(new_loc); } + + delete loc_it; } -/* Every time a thread enters a function, set its position to the predicate tree entry */ -void FuncNode::init_predicate_tree_position(thread_id_t tid) +bool FuncNode::likely_reads_from_null(ModelAction * read) { - int thread_id = id_to_int(tid); - if (predicate_tree_position.size() <= (uint) thread_id) - predicate_tree_position.resize(thread_id + 1); + uint64_t read_val = read->get_reads_from_value(); + if ( (void *)(read_val && 0xffffffff) == NULL ) + return true; - predicate_tree_position[thread_id] = predicate_tree_entry; + return false; } void FuncNode::set_predicate_tree_position(thread_id_t tid, Predicate * pred) { int thread_id = id_to_int(tid); - predicate_tree_position[thread_id] = pred; + ModelVector * stack = thrd_predicate_tree_position[thread_id]; + (*stack)[stack->size() - 1] = pred; } /* @return The position of a thread in a predicate tree */ Predicate * FuncNode::get_predicate_tree_position(thread_id_t tid) { int thread_id = id_to_int(tid); - return predicate_tree_position[thread_id]; + return thrd_predicate_tree_position[thread_id]->back(); +} + +void FuncNode::add_predicate_to_trace(thread_id_t tid, Predicate * pred) +{ + int thread_id = id_to_int(tid); + thrd_predicate_trace[thread_id]->back()->push_back(pred); +} + +void FuncNode::init_marker(thread_id_t tid) +{ + marker++; + + int thread_id = id_to_int(tid); + int old_size = thrd_markers.size(); + + if (old_size < thread_id + 1) { + thrd_markers.resize(thread_id + 1); + + for (int i = old_size;i < thread_id + 1;i++) { + thrd_markers[i] = new ModelVector(); + thrd_recursion_depth.push_back(-1); + } + } + + thrd_markers[thread_id]->push_back(marker); + thrd_recursion_depth[thread_id]++; +} + +uint64_t FuncNode::get_associated_read(thread_id_t tid, FuncInst * inst) +{ + int thread_id = id_to_int(tid); + int recursion_depth = thrd_recursion_depth[thread_id]; + uint marker = thrd_markers[thread_id]->back(); + + return inst->get_associated_read(tid, recursion_depth, marker); } -/* Make sure elements of thrd_inst_act_map are initialized properly when threads enter functions */ -void FuncNode::init_inst_act_map(thread_id_t tid) +/* Make sure elements of maps are initialized properly when threads enter functions */ +void FuncNode::init_local_maps(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(); + int old_size = thrd_loc_inst_maps.size(); + + if (old_size < thread_id + 1) { + int new_size = thread_id + 1; + + thrd_loc_inst_maps.resize(new_size); + thrd_inst_id_maps.resize(new_size); + thrd_inst_pred_maps.resize(new_size); + + for (int i = old_size;i < new_size;i++) { + thrd_loc_inst_maps[i] = new ModelVector; + thrd_inst_id_maps[i] = new ModelVector; + thrd_inst_pred_maps[i] = new ModelVector; + } + } - if (thrd_inst_act_map->size() <= (uint) thread_id) { - uint new_size = thread_id + 1; - thrd_inst_act_map->resize(new_size); + ModelVector * map = thrd_loc_inst_maps[thread_id]; + int index = thrd_recursion_depth[thread_id]; - for (uint i = old_size;i < new_size;i++) - (*thrd_inst_act_map)[i] = new inst_act_map_t(128); + // If there are recursive calls, push more hashtables into the vector. + if (map->size() < (uint) index + 1) { + thrd_loc_inst_maps[thread_id]->push_back(new loc_inst_map_t(64)); + thrd_inst_id_maps[thread_id]->push_back(new inst_id_map_t(64)); + thrd_inst_pred_maps[thread_id]->push_back(new inst_pred_map_t(64)); } + + ASSERT(map->size() == (uint) index + 1); } -/* Reset elements of thrd_inst_act_map when threads exit functions */ -void FuncNode::reset_inst_act_map(thread_id_t tid) +/* Reset elements of maps when threads exit functions */ +void FuncNode::reset_local_maps(thread_id_t tid) { int thread_id = id_to_int(tid); - SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + int index = thrd_recursion_depth[thread_id]; + + // When recursive call ends, keep only one hashtable in the vector + if (index > 0) { + delete thrd_loc_inst_maps[thread_id]->back(); + delete thrd_inst_id_maps[thread_id]->back(); + delete thrd_inst_pred_maps[thread_id]->back(); - inst_act_map_t * map = (*thrd_inst_act_map)[thread_id]; - map->reset(); + thrd_loc_inst_maps[thread_id]->pop_back(); + thrd_inst_id_maps[thread_id]->pop_back(); + thrd_inst_pred_maps[thread_id]->pop_back(); + } else { + thrd_loc_inst_maps[thread_id]->back()->reset(); + thrd_inst_id_maps[thread_id]->back()->reset(); + thrd_inst_pred_maps[thread_id]->back()->reset(); + } } -void FuncNode::update_inst_act_map(thread_id_t tid, ModelAction * read_act) +void FuncNode::init_predicate_tree_data_structure(thread_id_t tid) { int thread_id = id_to_int(tid); - SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + int old_size = thrd_predicate_tree_position.size(); + + if (old_size < thread_id + 1) { + thrd_predicate_tree_position.resize(thread_id + 1); + thrd_predicate_trace.resize(thread_id + 1); + + for (int i = old_size;i < thread_id + 1;i++) { + thrd_predicate_tree_position[i] = new ModelVector(); + thrd_predicate_trace[i] = new ModelVector(); + } + } - inst_act_map_t * map = (*thrd_inst_act_map)[thread_id]; - FuncInst * read_inst = get_inst(read_act); - map->put(read_inst, read_act); + thrd_predicate_tree_position[thread_id]->push_back(predicate_tree_entry); + thrd_predicate_trace[thread_id]->push_back(new predicate_trace_t()); } -inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid) +void FuncNode::reset_predicate_tree_data_structure(thread_id_t tid) { int thread_id = id_to_int(tid); - SnapVector * thrd_inst_act_map = history->getThrdInstActMap(func_id); + thrd_predicate_tree_position[thread_id]->pop_back(); - return (*thrd_inst_act_map)[thread_id]; + // Free memories allocated in init_predicate_tree_data_structure + delete thrd_predicate_trace[thread_id]->back(); + thrd_predicate_trace[thread_id]->pop_back(); } /* Add FuncNodes that this node may follow */ @@ -703,6 +823,7 @@ int FuncNode::compute_distance(FuncNode * target, int max_step) else if (target == this) return 0; + // Be careful with memory SnapList queue; HashTable distances(128); @@ -737,87 +858,29 @@ int FuncNode::compute_distance(FuncNode * target, int max_step) return -1; } -/* Implement quick sort to sort leaves before assigning base scores */ -static int partition(SnapVector * arr, int low, int high) -{ - unsigned int pivot = (*arr)[high]->get_depth(); - int i = low - 1; - - for (int j = low; j <= high - 1; j++) { - if ( (*arr)[j]->get_depth() < pivot ) { - i++; - Predicate *tmp = (*arr)[i]; - (*arr)[i] = (*arr)[j]; - (*arr)[j] = tmp; - } - } - - Predicate * tmp = (*arr)[i + 1]; - (*arr)[i + 1] = (*arr)[high]; - (*arr)[high] = tmp; - - return i + 1; -} - -/* Implement quick sort to sort leaves before assigning base scores */ -static void quickSort(SnapVector * arr, int low, int high) +void FuncNode::update_predicate_tree_weight(thread_id_t tid) { - if (low < high) { - int pi = partition(arr, low, high); + predicate_trace_t * trace = thrd_predicate_trace[id_to_int(tid)]->back(); - quickSort(arr, low, pi - 1); - quickSort(arr, pi + 1, high); - } -} - -void FuncNode::assign_base_score() -{ - PredSetIter * it = predicate_leaves.iterator(); - SnapVector leaves; - while (it->hasNext()) { - Predicate * pred = it->next(); - pred->set_weight(1); - leaves.push_back(pred); - } - - quickSort(&leaves, 0, leaves.size() - 1); - - // assign scores for internal nodes; - while ( !leaves.empty() ) { - Predicate * leaf = leaves.back(); - leaves.pop_back(); + // Update predicate weights based on prediate trace + for (int i = trace->size() - 1;i >= 0;i--) { + Predicate * node = (*trace)[i]; + ModelVector * children = node->get_children(); - 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++) { + if (children->size() == 0) { + double weight = 100.0 / sqrt(node->get_expl_count() + node->get_fail_count() + 1); + node->set_weight(weight); + } else { + double weight_sum = 0.0; + 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; + 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(); + double average_weight = (double) weight_sum / (double) children->size(); + double weight = average_weight * pow(0.9, node->get_depth()); + node->set_weight(weight); } } }