From: weiyu Date: Thu, 8 Aug 2019 23:16:58 +0000 (-0700) Subject: add a dummy predicate entry node to make code simpler; back edges are also added X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=commitdiff_plain;h=f8d348f04f665e97cb461a03b9a468769bf8343e add a dummy predicate entry node to make code simpler; back edges are also added --- diff --git a/funcnode.cc b/funcnode.cc index 7c146550..7adc5376 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -3,12 +3,12 @@ FuncNode::FuncNode() : predicate_tree_initialized(false), + predicate_tree_entry(new Predicate(NULL, true)), func_inst_map(), inst_list(), entry_insts(), thrd_read_map(), - predicate_tree_entry(), - inst_pred_map() + predicate_tree_backedges() {} /* Check whether FuncInst with the same type, position, and location @@ -231,35 +231,37 @@ void FuncNode::update_predicate_tree(func_inst_list_t * inst_list, HashTable loc_inst_map(64); + HashTable loc_inst_map(128); + /* map a FuncInst to the parent of its predicate */ + HashTable inst_pred_map(128); sllnode *it = inst_list->begin(); - FuncInst * entry_inst = it->getVal(); - - /* get the unique Predicate pointer, assuming entry instructions have no predicate expression */ - Predicate * curr_pred = NULL; - PredSetIter * pit = predicate_tree_entry.iterator(); - while (pit->hasNext()) { - Predicate * p = pit->next(); - if (p->get_func_inst() == entry_inst) { - curr_pred = p; - break; - } - } - if (curr_pred == NULL) { - curr_pred = new Predicate(entry_inst); - curr_pred->set_entry_predicate(); - predicate_tree_entry.add(curr_pred); - } - - loc_inst_map.put(entry_inst->get_location(), entry_inst); + Predicate * curr_pred = predicate_tree_entry; - it = it->getNext(); while (it != NULL) { FuncInst * curr_inst = it->getVal(); + Predicate * old_pred = curr_pred; bool branch_found = follow_branch(&curr_pred, curr_inst, read_val_map, &loc_inst_map); + // check back edges + if (!branch_found) { + Predicate * back_pred = curr_pred->get_backedge(); + if (back_pred != NULL) { + curr_pred = back_pred; + continue; + } + + if (inst_pred_map.contains(curr_inst)) { + back_pred = inst_pred_map.get(curr_inst); + curr_pred->set_backedge(back_pred); + curr_pred = back_pred; + continue; + } + } + + if (!inst_pred_map.contains(curr_inst)) + inst_pred_map.put(curr_inst, old_pred); + if (!branch_found) { if ( loc_inst_map.contains(curr_inst->get_location()) ) { Predicate * new_pred1 = new Predicate(curr_inst); @@ -268,9 +270,10 @@ void FuncNode::update_predicate_tree(func_inst_list_t * inst_list, HashTableadd_predicate(EQUALITY, curr_inst->get_location(), false); - /* TODO: add to inst_pred_map */ curr_pred->add_child(new_pred1); curr_pred->add_child(new_pred2); + //new_pred1->add_parent(curr_pred); + //new_pred2->add_parent(curr_pred); FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location()); uint64_t last_read = read_val_map->get(last_inst); @@ -281,17 +284,18 @@ void FuncNode::update_predicate_tree(func_inst_list_t * inst_list, HashTableadd_child(new_pred); + //new_pred->add_parent(curr_pred); + curr_pred = new_pred; } } loc_inst_map.put(curr_inst->get_location(), curr_inst); - it = it->getNext(); } -// model_print("function %s\n", func_name); -// print_predicate_tree(); + model_print("function %s\n", func_name); + print_predicate_tree(); } /* Given curr_pred and next_inst, find the branch following curr_pred that contains next_inst and the correct predicate @@ -353,12 +357,7 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, void FuncNode::print_predicate_tree() { model_print("digraph function_%s {\n", func_name); - PredSetIter * it = predicate_tree_entry.iterator(); - - while (it->hasNext()) { - Predicate * p = it->next(); - p->print_pred_subtree(); - } + predicate_tree_entry->print_pred_subtree(); model_print("}\n"); // end of graph } diff --git a/funcnode.h b/funcnode.h index 58fcc7a0..bfb3fac7 100644 --- a/funcnode.h +++ b/funcnode.h @@ -47,6 +47,7 @@ private: uint32_t func_id; const char * func_name; bool predicate_tree_initialized; + Predicate * predicate_tree_entry; // a dummy node whose children are the real entries /* Use source line number as the key of hashtable, to check if * atomic operation with this line number has been added or not @@ -61,11 +62,7 @@ private: /* Store the values read by atomic read actions per memory location for each thread */ ModelVector thrd_read_map; - - PredSet predicate_tree_entry; - - /* A FuncInst may correspond to multiple Predicates, so collect them into a PredSet */ - HashTable inst_pred_map; + HashTable predicate_tree_backedges; }; #endif /* __FUNCNODE_H__ */ diff --git a/predicate.cc b/predicate.cc index 9726fb3a..6b83d225 100644 --- a/predicate.cc +++ b/predicate.cc @@ -1,10 +1,11 @@ #include "predicate.h" -Predicate::Predicate(FuncInst * func_inst) : +Predicate::Predicate(FuncInst * func_inst, bool is_entry) : func_inst(func_inst), - entry_predicate(false), + entry_predicate(is_entry), pred_expressions(), - children() + children(), + parents() {} unsigned int pred_expr_hash(struct pred_expr * expr) @@ -35,10 +36,22 @@ void Predicate::add_child(Predicate * child) children.push_back(child); } +void Predicate::add_parent(Predicate * parent) +{ + /* check duplication? */ + parents.push_back(parent); +} + void Predicate::print_predicate() { model_print("\"%p\" [shape=box, label=\"\n", this); + if (entry_predicate) { + model_print("entry node\"];\n"); + return; + } + func_inst->print(); + PredExprSetIter * it = pred_expressions.iterator(); if (pred_expressions.getSize() == 0) @@ -59,4 +72,7 @@ void Predicate::print_pred_subtree() child->print_pred_subtree(); model_print("\"%p\" -> \"%p\"\n", this, child); } + + if (backedge != NULL) + model_print("\"%p\" -> \"%p\"[style=dashed, color=grey]\n", this, backedge); } diff --git a/predicate.h b/predicate.h index 33b2203f..c4390f11 100644 --- a/predicate.h +++ b/predicate.h @@ -34,14 +34,19 @@ struct pred_expr { class Predicate { public: - Predicate(FuncInst * func_inst); + Predicate(FuncInst * func_inst, bool is_entry = false); ~Predicate(); FuncInst * get_func_inst() { return func_inst; } PredExprSet * get_pred_expressions() { return &pred_expressions; } void add_predicate(token_t token, void * location, bool value); void add_child(Predicate * child); + void add_parent(Predicate * parent); + void set_backedge(Predicate * back_pred) { backedge = back_pred; } + ModelVector * get_children() { return &children; } + ModelVector * get_parents() { return &parents; } + Predicate * get_backedge() { return backedge; } bool is_entry_predicate() { return entry_predicate; } void set_entry_predicate() { entry_predicate = true; } @@ -56,6 +61,9 @@ private: /* may have multiple predicates */ PredExprSet pred_expressions; ModelVector children; + ModelVector parents; + /* assume almost one back edge exists */ + Predicate * backedge; }; #endif /* __PREDICATE_H__ */