toward updating predicate trees every time a function exits

diff --git a/funcnode.cc b/funcnode.cc
index c24449ff908a5f348bf4d4ceb2a53219d5a9d7d2..44c69e22b09d4f2c322e7c90cf1db32e57433bc4 100644 (file)
--- a/funcnode.cc
+++ b/funcnode.cc
@@ -1,6 +1,5 @@
 #include "funcnode.h"
 #include <fcntl.h>
-#include "common.h"
 
 FuncNode::FuncNode() :
        predicate_tree_initialized(false),
@@ -201,47 +200,82 @@ void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTable<FuncI
        if (inst_list == NULL || inst_list->size() == 0)
                return;
 
+/*
        if (predicate_tree_initialized) {
                return;
        }
-
        predicate_tree_initialized = true;
-
+*/
        // maybe restrict the size of hashtable to save calloc time
-       HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map;
+       HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(64);
 
        sllnode<FuncInst *> *it = inst_list->begin();
        FuncInst * entry_inst = it->getVal();
 
-       /* entry instruction has no predicate expression */
-       Predicate * curr_pred = new Predicate(entry_inst);
-       predicate_tree_entry.add(curr_pred);
+       /* 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();
+               p->get_func_inst()->print();
+               if (p->get_func_inst() == entry_inst) {
+                       curr_pred = p;
+                       break;
+               }
+       }
+       if (curr_pred == NULL) {
+               curr_pred = new Predicate(entry_inst);
+               predicate_tree_entry.add(curr_pred);
+       }
+
        loc_inst_map.put(entry_inst->get_location(), entry_inst);
 
        it = it->getNext();
        while (it != NULL) {
                FuncInst * curr_inst = it->getVal();
-               if ( loc_inst_map.contains(curr_inst->get_location()) ) {
-                       Predicate * new_pred1 = new Predicate(curr_inst);
-                       new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true);
-
-                       Predicate * new_pred2 = new Predicate(curr_inst);
-                       new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false);
-
-                       curr_pred->add_child(new_pred1);
-                       curr_pred->add_child(new_pred2);
-
-                       FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location());
-
-                       uint64_t last_read = read_val_map->get(last_inst);
-                       if ( last_read == read_val_map->get(curr_inst) )
-                               curr_pred = new_pred1;
-                       else
-                               curr_pred = new_pred2;
-               } else {
-                       Predicate * new_pred = new Predicate(curr_inst);
-                       curr_pred->add_child(new_pred);
-                       curr_pred = new_pred;
+               bool child_found = false;
+
+               /* check if a child with the same func_inst and corresponding predicate exists */
+               ModelVector<Predicate *> * children = curr_pred->get_children();
+               for (uint i = 0; i < children->size(); i++) {
+                       Predicate * child = (*children)[i];
+                       if (child->get_func_inst() != curr_inst)
+                               continue;
+
+                       PredExprSet * pred_expressions = child->get_pred_expressions();
+
+                       /* no predicate, follow the only child */
+                       if (pred_expressions->getSize() == 0) {
+                               model_print("no predicate exists: ");
+                               curr_inst->print();
+                               curr_pred = child;
+                               child_found = true;
+                               break;
+                       }
+               }
+
+               if (!child_found) {
+                       if ( loc_inst_map.contains(curr_inst->get_location()) ) {
+                               Predicate * new_pred1 = new Predicate(curr_inst);
+                               new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true);
+
+                               Predicate * new_pred2 = new Predicate(curr_inst);
+                               new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false);
+
+                               curr_pred->add_child(new_pred1);
+                               curr_pred->add_child(new_pred2);
+
+                               FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location());
+                               uint64_t last_read = read_val_map->get(last_inst);
+                               if ( last_read == read_val_map->get(curr_inst) )
+                                       curr_pred = new_pred1;
+                               else
+                                       curr_pred = new_pred2;
+                       } else {
+                               Predicate * new_pred = new Predicate(curr_inst);
+                               curr_pred->add_child(new_pred);
+                               curr_pred = new_pred;
+                       }
                }
 
                loc_inst_map.put(curr_inst->get_location(), curr_inst);
@@ -249,16 +283,15 @@ void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTable<FuncI
                it = it->getNext();
        }
 
-       model_print("function %s\n", func_name);
-       print_predicate_tree();
+//     model_print("function %s\n", func_name);
+//     print_predicate_tree();
 }
 
 
 void FuncNode::print_predicate_tree()
 {
        model_print("digraph function_%s {\n", func_name);
-       HSIterator<Predicate *, uintptr_t, 0, model_malloc, model_calloc, model_free> * it;
-       it = predicate_tree_entry.iterator();
+       PredSetIter * it = predicate_tree_entry.iterator();
 
        while (it->hasNext()) {
                Predicate * p = it->next();

diff --git a/funcnode.h b/funcnode.h
index 61ab0593b7ed9a88465ae3fbc04eec7c8fc1fa3b..a4412c6ca45aa0bf1aca1ab12e1aa1ff3ccf119e 100644 (file)
--- a/funcnode.h
+++ b/funcnode.h
@@ -9,6 +9,7 @@
 
 typedef ModelList<FuncInst *> func_inst_list_mt;
 typedef HashTable<void *, uint64_t, uintptr_t, 4, model_malloc, model_calloc, model_free> read_map_t;
+typedef HSIterator<Predicate *, uintptr_t, 0, model_malloc, model_calloc, model_free> PredSetIter;
 
 class FuncNode {
 public:

diff --git a/hashset.h b/hashset.h
index 7f7febc657cfb36f5de99808b2938274bab73eb9..baf6d43e7d6c78e14fe2dcd3fbf5f7f2eeab07bf 100644 (file)
--- a/hashset.h
+++ b/hashset.h
@@ -18,9 +18,7 @@ struct LinkNode {
        LinkNode<_Key> *next;
 };
 
-template<typename _Key, typename _KeyInt, int _Shift, void *
-                                (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function
-                                                                                                                                                                                                                                                                                                                                                                                                                        )(_Key), bool (*equals)(_Key, _Key)>
+template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
 class HashSet;
 
 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >

diff --git a/history.cc b/history.cc
index 782da5a3b01690b59081f194ff15f74dade1868f..db5cbcac222697c4698001881050a519586ec2d7 100644 (file)
--- a/history.cc
+++ b/history.cc
@@ -113,9 +113,8 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
                resize_func_nodes( func_id + 1 );
 
        FuncNode * func_node = func_nodes[func_id];
-       ASSERT (func_node != NULL);
 
-       /* do not care actions without a position */
+       /* do not care about actions without a position */
        if (act->get_position() == NULL)
                return;
 
@@ -129,7 +128,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
 /* return the FuncNode given its func_id  */
 FuncNode * ModelHistory::get_func_node(uint32_t func_id)
 {
-       if (func_nodes.size() <= func_id)       // this node has not been added
+       if (func_nodes.size() <= func_id)       // this node has not been added to func_nodes
                return NULL;
 
        return func_nodes[func_id];

diff --git a/predicate.cc b/predicate.cc
index 42c63100f07a75b74118265010d1f9ffbf6e13a1..a5693c9b2fe6bdad79a5c7b956ca312da1a22837 100644 (file)
--- a/predicate.cc
+++ b/predicate.cc
@@ -2,7 +2,7 @@
 
 Predicate::Predicate(FuncInst * func_inst) :
        func_inst(func_inst),
-       predicates(),
+       pred_expressions(),
        children()
 {}
 
@@ -25,7 +25,7 @@ bool pred_expr_equal(struct pred_expr * p1, struct pred_expr * p2)
 void Predicate::add_predicate(token_t token, void * location, bool value)
 {
        struct pred_expr *ptr = new pred_expr(token, location, value);
-       predicates.add(ptr);
+       pred_expressions.add(ptr);
 }
 
 void Predicate::add_child(Predicate * child)
@@ -38,9 +38,9 @@ void Predicate::print_predicate()
 {
        model_print("\"%p\" [shape=box, label=\"%p\n", this, this);
        func_inst->print();
-       PredSetIter * it = predicates.iterator();
+       PredExprSetIter * it = pred_expressions.iterator();
 
-       if (predicates.getSize() == 0)
+       if (pred_expressions.getSize() == 0)
                model_print("no predicate\n");
 
        while (it->hasNext()) {

diff --git a/predicate.h b/predicate.h
index 6d0dbc4be4232e4a37e0537bde79894db83fecb5..3dfb8d5baba24ea1fc28518c5878e0fb916818e1 100644 (file)
--- a/predicate.h
+++ b/predicate.h
@@ -6,8 +6,8 @@
 
 unsigned int pred_expr_hash (struct pred_expr *);
 bool pred_expr_equal(struct pred_expr *, struct pred_expr *);
-typedef HashSet<struct pred_expr *, uintptr_t, 0, model_malloc, model_calloc, model_free, pred_expr_hash, pred_expr_equal> PredSet;
-typedef HSIterator<struct pred_expr *, uintptr_t, 0, model_malloc, model_calloc, model_free, pred_expr_hash, pred_expr_equal> PredSetIter;
+typedef HashSet<struct pred_expr *, uintptr_t, 0, model_malloc, model_calloc, model_free, pred_expr_hash, pred_expr_equal> PredExprSet;
+typedef HSIterator<struct pred_expr *, uintptr_t, 0, model_malloc, model_calloc, model_free, pred_expr_hash, pred_expr_equal> PredExprSetIter;
 
 typedef enum predicate_token {
        EQUALITY, NULLITY
@@ -38,9 +38,10 @@ public:
        ~Predicate();
 
        FuncInst * get_func_inst() { return func_inst; }
-       PredSet * get_predicates() { return &predicates; }
+       PredExprSet * get_pred_expressions() { return &pred_expressions; }
        void add_predicate(token_t token, void * location, bool value);
        void add_child(Predicate * child);
+       ModelVector<Predicate *> * get_children() { return &children; }
 
        void print_predicate();
        void print_pred_subtree();
@@ -49,7 +50,7 @@ public:
 private:
        FuncInst * func_inst;
        /* may have multiple precicates */
-       PredSet predicates;
+       PredExprSet pred_expressions;
        ModelVector<Predicate *> children;
 };