From be2b5266d974c5a043955f0fe29cd3d89aab7072 Mon Sep 17 00:00:00 2001 From: weiyu Date: Wed, 11 Dec 2019 16:46:38 -0800 Subject: [PATCH] Fix a bug in predicate.cc and declare 3 hashtables in funcnode.h as non-snapshotted memory to avoid repeatedly constructing and destructing them --- funcnode.cc | 43 +++++++++++++++++++++++++++---------------- funcnode.h | 15 +++++++++++++-- history.cc | 4 +--- predicate.cc | 24 ++++++++++++------------ predicate.h | 2 +- 5 files changed, 54 insertions(+), 34 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index 5bb73b98..ab386286 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -15,6 +15,9 @@ FuncNode::FuncNode(ModelHistory * history) : func_inst_map(), inst_list(), entry_insts(), + inst_pred_map(128), + inst_id_map(128), + loc_act_map(128), predicate_tree_position(), predicate_leaves(), edge_table(32), @@ -264,16 +267,12 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) return; incr_marker(); - - /* Map a FuncInst to the its predicate */ - HashTable inst_pred_map(128); - - // Number FuncInsts to detect loops - HashTable inst_id_map(128); uint32_t inst_counter = 0; - /* Only need to store the locations of read actions */ - HashTable loc_act_map(128); + // Clear hashtables + loc_act_map.reset(); /* Only need to store the locations of read actions */ + inst_pred_map.reset(); + inst_id_map.reset(); sllnode *it = act_list->begin(); Predicate * curr_pred = predicate_tree_entry; @@ -318,7 +317,7 @@ 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; } @@ -342,6 +341,8 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) // Exit predicate is unset yet curr_pred->set_exit(predicate_tree_exit); } + + update_predicate_tree_weight(); } /* Given curr_pred and next_inst, find the branch following curr_pred that @@ -419,15 +420,14 @@ 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) { void * loc = next_act->get_location(); if (next_inst->is_read()) { /* read + rmw */ - if ( loc_act_map->contains(loc) ) { - ModelAction * last_act = loc_act_map->get(loc); + if ( loc_act_map.contains(loc) ) { + ModelAction * last_act = loc_act_map.get(loc); 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); @@ -438,8 +438,8 @@ 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); + if (loc_act_map.contains(neighbor)) { + ModelAction * last_act = loc_act_map.get(neighbor); FuncInst * last_inst = get_inst(last_act); struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst); @@ -770,13 +770,14 @@ static void quickSort(SnapVector * arr, int low, int high) } } -void FuncNode::assign_base_score() +void FuncNode::assign_initial_weight() { PredSetIter * it = predicate_leaves.iterator(); SnapVector leaves; while (it->hasNext()) { Predicate * pred = it->next(); - pred->set_weight(1); + double weight = 100.0 / sqrt(pred->get_expl_count() + 1); + pred->set_weight(weight); leaves.push_back(pred); } @@ -822,6 +823,16 @@ void FuncNode::assign_base_score() } } +void FuncNode::update_predicate_tree_weight() +{ + if (marker == 2) { + // Predicate tree is initially built + assign_initial_weight(); + } else { + + } +} + void FuncNode::print_predicate_tree() { model_print("digraph function_%s {\n", func_name); diff --git a/funcnode.h b/funcnode.h index ecb270b0..b3e80741 100644 --- a/funcnode.h +++ b/funcnode.h @@ -60,7 +60,6 @@ public: ModelList * get_out_edges() { return &out_edges; } int compute_distance(FuncNode * target, int max_step = MAX_DIST); - void assign_base_score(); void print_predicate_tree(); MEMALLOC @@ -87,7 +86,16 @@ private: /* Possible entry atomic actions in this function */ func_inst_list_mt entry_insts; - void infer_predicates(FuncInst * next_inst, ModelAction * next_act, HashTable * loc_act_map, SnapVector * half_pred_expressions); + /* Map a FuncInst to the its predicate when updating predicate trees */ + HashTable inst_pred_map; + + /* Number FuncInsts to detect loops when updating predicate trees */ + HashTable inst_id_map; + + /* Delect read actions at the same locations when updating predicate trees */ + HashTable loc_act_map; + + void infer_predicates(FuncInst * next_inst, ModelAction * next_act, SnapVector * half_pred_expressions); void generate_predicates(Predicate * curr_pred, FuncInst * next_inst, SnapVector * half_pred_expressions); bool amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act); @@ -117,6 +125,9 @@ private: /* FuncNodes that follow this node */ ModelList out_edges; + + void assign_initial_weight(); + void update_predicate_tree_weight(); }; #endif /* __FUNCNODE_H__ */ diff --git a/history.cc b/history.cc index f1060ca9..7e5166fd 100644 --- a/history.cc +++ b/history.cc @@ -200,7 +200,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) if (curr_pred) { // Follow child - curr_pred = curr_pred->get_single_child(curr_inst); + curr_pred = curr_pred->follow_write_child(curr_inst); } func_node->set_predicate_tree_position(tid, curr_pred); } @@ -565,8 +565,6 @@ void ModelHistory::print_func_node() /* function id starts with 1 */ for (uint32_t i = 1;i < func_nodes.size();i++) { FuncNode * func_node = func_nodes[i]; - - func_node->assign_base_score(); func_node->print_predicate_tree(); /* diff --git a/predicate.cc b/predicate.cc index b2c6e605..9ef02988 100644 --- a/predicate.cc +++ b/predicate.cc @@ -78,22 +78,22 @@ void Predicate::copy_predicate_expr(Predicate * other) } } -/* Return the single child branch of this predicate. - * Return NULL if this predicate has no children. +/* Follow the child if any child whose FuncInst matches with inst + * + * @param inst must be an ATOMIC_WRITE FuncInst + * @return NULL if no such child is found. */ -Predicate * Predicate::get_single_child(FuncInst * inst) +Predicate * Predicate::follow_write_child(FuncInst * inst) { - int size = children.size(); - if (size == 0) - return NULL; + ASSERT(inst->get_type() == ATOMIC_WRITE); - /* Should only have one child */ - ASSERT(size == 1); - Predicate * child = children[0]; - - ASSERT(child->get_func_inst() == inst); + for (uint i = 0; i < children.size(); i++) { + Predicate * child = children[i]; + if (child->get_func_inst() == inst) + return child; + } - return child; + return NULL; } /* Evaluate predicate expressions against the given inst_act_map */ diff --git a/predicate.h b/predicate.h index 8b1e7c81..8afc24be 100644 --- a/predicate.h +++ b/predicate.h @@ -28,7 +28,7 @@ public: void set_weight(double weight_) { weight = weight_; } void copy_predicate_expr(Predicate * other); - Predicate * get_single_child(FuncInst * inst); + Predicate * follow_write_child(FuncInst * inst); ModelVector * get_children() { return &children; } Predicate * get_parent() { return parent; } Predicate * get_exit() { return exit; } -- 2.34.1