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),
return;
incr_marker();
-
- /* Map a FuncInst to the its predicate */
- HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
-
- // Number FuncInsts to detect loops
- HashTable<FuncInst *, uint32_t, uintptr_t, 0> inst_id_map(128);
uint32_t inst_counter = 0;
- /* Only need to store the locations of read actions */
- HashTable<void *, ModelAction *, uintptr_t, 0> 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<ModelAction *> *it = act_list->begin();
Predicate * curr_pred = predicate_tree_entry;
// Generate new branches
if (!branch_found) {
SnapVector<struct half_pred_expr *> 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;
}
// 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
/* Infer predicate expressions, which are generated in FuncNode::generate_predicates */
void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act,
-HashTable<void *, ModelAction *, uintptr_t, 0> * loc_act_map,
SnapVector<struct half_pred_expr *> * 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);
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);
}
}
-void FuncNode::assign_base_score()
+void FuncNode::assign_initial_weight()
{
PredSetIter * it = predicate_leaves.iterator();
SnapVector<Predicate *> 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);
}
}
}
+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);
ModelList<FuncNode *> * 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
/* Possible entry atomic actions in this function */
func_inst_list_mt entry_insts;
- void infer_predicates(FuncInst * next_inst, ModelAction * next_act, HashTable<void *, ModelAction *, uintptr_t, 0> * loc_act_map, SnapVector<struct half_pred_expr *> * half_pred_expressions);
+ /* Map a FuncInst to the its predicate when updating predicate trees */
+ HashTable<FuncInst *, Predicate *, uintptr_t, 0, model_malloc, model_calloc, model_free> inst_pred_map;
+
+ /* Number FuncInsts to detect loops when updating predicate trees */
+ HashTable<FuncInst *, uint32_t, uintptr_t, 0, model_malloc, model_calloc, model_free> inst_id_map;
+
+ /* Delect read actions at the same locations when updating predicate trees */
+ HashTable<void *, ModelAction *, uintptr_t, 0, model_malloc, model_calloc, model_free> loc_act_map;
+
+ void infer_predicates(FuncInst * next_inst, ModelAction * next_act, SnapVector<struct half_pred_expr *> * half_pred_expressions);
void generate_predicates(Predicate * curr_pred, FuncInst * next_inst, SnapVector<struct half_pred_expr *> * half_pred_expressions);
bool amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act);
/* FuncNodes that follow this node */
ModelList<FuncNode *> out_edges;
+
+ void assign_initial_weight();
+ void update_predicate_tree_weight();
};
#endif /* __FUNCNODE_H__ */
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);
}
/* 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();
/*
}
}
-/* 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 */
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<Predicate *> * get_children() { return &children; }
Predicate * get_parent() { return parent; }
Predicate * get_exit() { return exit; }