loc_act_map(128),
predicate_tree_position(),
predicate_leaves(),
+ leaves_tmp_storage(),
+ weight_debug_vec(),
+ failed_predicates(),
edge_table(32),
out_edges()
{
return;
HashTable<void *, value_set_t *, uintptr_t, 0> * write_history = history->getWriteHistory();
+ HashSet<ModelAction *, uintptr_t, 2> write_actions;
/* build inst_list from act_list for later processing */
func_inst_list_t inst_list;
for (sllnode<ModelAction *> * it = act_list->begin();it != NULL;it = it->getNext()) {
ModelAction * act = it->getVal();
+
+ // Use the original action type and decrement ref count
+ // so that actions may be deleted by Execution::collectActions
+ if (act->get_original_type() != ATOMIC_NOP && act->get_swap_flag() == false)
+ act->use_original_type();
+
+ act->decr_read_ref_count();
+
+ if (act->is_read()) {
+ // For every read or rmw actions in this list, the reads_from was marked, and not deleted.
+ // So it is safe to call get_reads_from
+ ModelAction * rf = act->get_reads_from();
+ if (rf->get_original_type() != ATOMIC_NOP && rf->get_swap_flag() == false)
+ rf->use_original_type();
+
+ rf->decr_read_ref_count();
+ }
+
FuncInst * func_inst = get_inst(act);
void * loc = act->get_location();
}
}
-// model_print("function %s\n", func_name);
-// print_val_loc_map();
-
update_inst_tree(&inst_list);
update_predicate_tree(&rw_act_list);
+ // Revert back action types and free
+ for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL;) {
+ ModelAction * act = it->getVal();
+ // Do iteration early in case we delete read actions
+ it = it->getNext();
+
+ // Collect write actions and reads_froms
+ if (act->is_read()) {
+ if (act->is_rmw()) {
+ write_actions.add(act);
+ }
+
+ ModelAction * rf = act->get_reads_from();
+ write_actions.add(rf);
+ } else if (act->is_write()) {
+ write_actions.add(act);
+ }
+
+ // Revert back action types
+ if (act->is_read()) {
+ ModelAction * rf = act->get_reads_from();
+ if (rf->get_swap_flag() == true)
+ rf->use_original_type();
+ }
+
+ if (act->get_swap_flag() == true)
+ act->use_original_type();
+
+ // Free read actions
+ if (act->is_read()) {
+ if (act->is_rmw()) {
+ // Do nothing. Its reads_from can not be READY_FREE
+ } else {
+ ModelAction *rf = act->get_reads_from();
+ if (rf->is_free()) {
+ model_print("delete read %d; %p\n", act->get_seq_number(), act);
+ delete act;
+ }
+ }
+ }
+ }
+
+ // Free write actions if possible
+ HSIterator<ModelAction *, uintptr_t, 2> * it = write_actions.iterator();
+ while (it->hasNext()) {
+ ModelAction * act = it->next();
+
+ if (act->is_free() && act->get_read_ref_count() == 0)
+ delete act;
+ }
+ delete it;
+
// print_predicate_tree();
}
inst_pred_map.reset();
inst_id_map.reset();
+ // Clear the set of leaves encountered in this path
+ leaves_tmp_storage.clear();
+
sllnode<ModelAction *> *it = act_list->begin();
Predicate * curr_pred = predicate_tree_entry;
while (it != NULL) {
Predicate * old_pred = inst_pred_map.get(next_inst);
Predicate * back_pred = old_pred->get_parent();
+ // For updating weights
+ leaves_tmp_storage.push_back(curr_pred);
+
+ // Add to the set of backedges
curr_pred->add_backedge(back_pred);
curr_pred = back_pred;
continue;
curr_pred->set_exit(predicate_tree_exit);
}
+ leaves_tmp_storage.push_back(curr_pred);
update_predicate_tree_weight();
}
* @return true if branch found, false otherwise.
*/
bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst,
-ModelAction * next_act, Predicate ** unset_predicate)
+ ModelAction * next_act, Predicate ** unset_predicate)
{
/* Check if a branch with func_inst and corresponding predicate exists */
bool branch_found = false;
bool equality;
switch(pred_expression->token) {
- case NOPREDICATE:
- predicate_correct = true;
- break;
- case EQUALITY:
- FuncInst * to_be_compared;
- ModelAction * last_act;
+ 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);
+ 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;
+ 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:
+ 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;
- model_print("unkown predicate token\n");
- break;
+ 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;
/* Infer predicate expressions, which are generated in FuncNode::generate_predicates */
void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act,
-SnapVector<struct half_pred_expr *> * half_pred_expressions)
+ SnapVector<struct half_pred_expr *> * half_pred_expressions)
{
void * loc = next_act->get_location();
half_pred_expressions->push_back(expression);
}
}
+
+ delete loc_it;
}
} else {
// next_inst is not single location
/* Able to generate complex predicates when there are multiple predciate expressions */
void FuncNode::generate_predicates(Predicate * curr_pred, FuncInst * next_inst,
-SnapVector<struct half_pred_expr *> * half_pred_expressions)
+ SnapVector<struct half_pred_expr *> * half_pred_expressions)
{
if (half_pred_expressions->size() == 0) {
Predicate * new_pred = new Predicate(next_inst);
bool FuncNode::amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act)
{
ModelVector<Predicate *> * children = curr_pred->get_children();
- ASSERT(children->size() == 1);
- // there should only be only child
- Predicate * unset_pred = (*children)[0];
+ 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;
+ }
+ }
+
uint64_t read_val = next_act->get_reads_from_value();
// only generate NULLITY predicate when it is actually NULL.
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)
}
_neighbors->add(new_loc);
}
+
+ delete loc_it;
}
/* Every time a thread enters a function, set its position to the predicate tree entry */
return -1;
}
+void FuncNode::add_failed_predicate(Predicate * pred)
+{
+ failed_predicates.add(pred);
+}
+
/* Implement quick sort to sort leaves before assigning base scores */
-static int partition(SnapVector<Predicate *> * arr, int low, int high)
+template<typename _Tp>
+static int partition(ModelVector<_Tp *> * arr, int low, int high)
{
- unsigned int pivot = (*arr)[high]->get_depth();
+ 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];
+ for (int j = low;j <= high - 1;j ++) {
+ if ( (*arr)[j] -> get_depth() < pivot ) {
+ i ++;
+ _Tp * tmp = (*arr)[i];
(*arr)[i] = (*arr)[j];
(*arr)[j] = tmp;
}
}
- Predicate * tmp = (*arr)[i + 1];
+ _Tp * tmp = (*arr)[i + 1];
(*arr)[i + 1] = (*arr)[high];
(*arr)[high] = tmp;
}
/* Implement quick sort to sort leaves before assigning base scores */
-static void quickSort(SnapVector<Predicate *> * arr, int low, int high)
+template<typename _Tp>
+static void quickSort(ModelVector<_Tp *> * arr, int low, int high)
{
if (low < high) {
int pi = partition(arr, low, high);
void FuncNode::assign_initial_weight()
{
PredSetIter * it = predicate_leaves.iterator();
- SnapVector<Predicate *> leaves;
+ leaves_tmp_storage.clear();
+
while (it->hasNext()) {
Predicate * pred = it->next();
- double weight = 100.0 / sqrt(pred->get_expl_count() + 1);
+ double weight = 100.0 / sqrt(pred->get_expl_count() + pred->get_fail_count() + 1);
pred->set_weight(weight);
- leaves.push_back(pred);
+ leaves_tmp_storage.push_back(pred);
}
+ delete it;
- quickSort(&leaves, 0, leaves.size() - 1);
+ quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1);
// assign scores for internal nodes;
- while ( !leaves.empty() ) {
- Predicate * leaf = leaves.back();
- leaves.pop_back();
+ while ( !leaves_tmp_storage.empty() ) {
+ Predicate * leaf = leaves_tmp_storage.back();
+ leaves_tmp_storage.pop_back();
Predicate * curr = leaf->get_parent();
while (curr != NULL) {
double weight_sum = 0;
bool has_unassigned_node = false;
- for (uint i = 0; i < children->size(); i++) {
+ for (uint i = 0;i < children->size();i++) {
Predicate * child = (*children)[i];
// If a child has unassigned weight
if (marker == 2) {
// Predicate tree is initially built
assign_initial_weight();
- } else {
+ return;
+ }
+
+ weight_debug_vec.clear();
+
+ PredSetIter * it = failed_predicates.iterator();
+ while (it->hasNext()) {
+ Predicate * pred = it->next();
+ leaves_tmp_storage.push_back(pred);
+ }
+ delete it;
+ failed_predicates.reset();
+
+ quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1);
+ for (uint i = 0;i < leaves_tmp_storage.size();i++) {
+ Predicate * pred = leaves_tmp_storage[i];
+ double weight = 100.0 / sqrt(pred->get_expl_count() + pred->get_fail_count() + 1);
+ pred->set_weight(weight);
+ }
+
+ // Update weights in internal nodes
+ while ( !leaves_tmp_storage.empty() ) {
+ Predicate * leaf = leaves_tmp_storage.back();
+ leaves_tmp_storage.pop_back();
+
+ Predicate * curr = leaf->get_parent();
+ while (curr != NULL) {
+ ModelVector<Predicate *> * 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];
+
+ double weight = child->get_weight();
+ if (weight != 0)
+ weight_sum += weight;
+ else if ( predicate_leaves.contains(child) ) {
+ // If this child is a leaf
+ double weight = 100.0 / sqrt(child->get_expl_count() + 1);
+ child->set_weight(weight);
+ weight_sum += weight;
+ } else {
+ has_unassigned_node = true;
+ weight_debug_vec.push_back(child); // For debugging purpose
+ break;
+ }
+ }
+
+ 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();
+ }
+ }
+ for (uint i = 0;i < weight_debug_vec.size();i++) {
+ Predicate * tmp = weight_debug_vec[i];
+ ASSERT( tmp->get_weight() != 0 );
}
}
projects / c11tester.git / blobdiff