From f8d348f04f665e97cb461a03b9a468769bf8343e Mon Sep 17 00:00:00 2001
From: weiyu <weiyuluo1232@gmail.com>
Date: Thu, 8 Aug 2019 16:16:58 -0700
Subject: [PATCH] add a dummy predicate entry node to make code simpler; back
edges are also added
---
funcnode.cc | 67 ++++++++++++++++++++++++++--------------------------
funcnode.h | 7 ++----
predicate.cc | 22 ++++++++++++++---
predicate.h | 10 +++++++-
4 files changed, 63 insertions(+), 43 deletions(-)
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<Fun
}
predicate_tree_initialized = true;
*/
- // maybe restrict the size of hashtable to save calloc time
- HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(64);
+ HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(128);
+ /* map a FuncInst to the parent of its predicate */
+ HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
sllnode<FuncInst *> *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, HashTable<Fun
Predicate * new_pred2 = new Predicate(curr_inst);
new_pred2->add_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, HashTable<Fun
} else {
Predicate * new_pred = new Predicate(curr_inst);
curr_pred->add_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<read_map_t *> thrd_read_map;
-
- PredSet predicate_tree_entry;
-
- /* A FuncInst may correspond to multiple Predicates, so collect them into a PredSet */
- HashTable<FuncInst *, PredSet *, uintptr_t, 0, model_malloc, model_calloc, model_free> inst_pred_map;
+ HashTable<FuncInst *, Predicate *, uintptr_t, 0, model_malloc, model_calloc, model_free> 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<Predicate *> * get_children() { return &children; }
+ ModelVector<Predicate *> * 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<Predicate *> children;
+ ModelVector<Predicate *> parents;
+ /* assume almost one back edge exists */
+ Predicate * backedge;
};
#endif /* __PREDICATE_H__ */
--
2.34.1