improve complexity

diff --git a/cyclegraph.cc b/cyclegraph.cc
index 47951d4eb645b8f181b3afe6e5cc01ad49260dc4..adafb0e126779ab6da734f18cf937de9509c0aea 100644 (file)
--- a/cyclegraph.cc
+++ b/cyclegraph.cc
@@ -137,6 +137,36 @@ void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
        addNodeEdge(fromnode, rmwnode, true);
 }
 
+void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, const ModelAction *to) {
+       for(SnapList<ModelAction*>::iterator it = edgeset->begin();it!=edgeset->end();) {
+               ModelAction *act = *it;
+               CycleNode *node = getNode(act);
+               SnapList<ModelAction*>::iterator it2 = it;
+               it2++;
+               for(;it2!=edgeset->end(); ) {
+                       ModelAction *act2 = *it;
+                       CycleNode *node2 = getNode(act2);
+                       if (checkReachable(node, node2)) {
+                               it = edgeset->erase(it);
+                               goto endouterloop;
+                       } else if (checkReachable(node2, node)) {
+                               it2 = edgeset->erase(it2);
+                               goto endinnerloop;
+                       }
+                       it2++;
+endinnerloop:
+                       ;
+               }
+               it++;
+endouterloop:
+               ;
+       }
+       for(SnapList<ModelAction*>::iterator it = edgeset->begin();it!=edgeset->end();it++) {
+               ModelAction *from = *it;
+               addEdge(from, to, from->get_tid() == to->get_tid());
+       }
+}
+
 /**
  * @brief Adds an edge between objects
  *

diff --git a/cyclegraph.h b/cyclegraph.h
index e2b586403994b5573c863d4825857e7945d28c8d..3ea4e3bbd2c9382562c39ca7ce05754d2b61301c 100644 (file)
--- a/cyclegraph.h
+++ b/cyclegraph.h
@@ -23,6 +23,7 @@ class CycleGraph {
 public:
        CycleGraph();
        ~CycleGraph();
+       void addEdges(SnapList<ModelAction *> * edgeset, const ModelAction *to);
        void addEdge(const ModelAction *from, const ModelAction *to);
        void addEdge(const ModelAction *from, const ModelAction *to, bool forceedge);
        void addRMWEdge(const ModelAction *from, const ModelAction *rmw);

diff --git a/execution.cc b/execution.cc
index 422b82a988255d4b7b1125ec75d7f6f8f21159f0..ac3ecbc00e069abd7a53ebbf8d6d70168bf14c97 100644 (file)
--- a/execution.cc
+++ b/execution.cc
@@ -910,12 +910,14 @@ void ModelExecution::w_modification_order(ModelAction *curr)
        unsigned int i;
        ASSERT(curr->is_write());
 
+       SnapList<ModelAction *> edgeset;
+
        if (curr->is_seqcst()) {
                /* We have to at least see the last sequentially consistent write,
                         so we are initialized. */
                ModelAction *last_seq_cst = get_last_seq_cst_write(curr);
                if (last_seq_cst != NULL) {
-                       mo_graph->addEdge(last_seq_cst, curr);
+                       edgeset.push_back(last_seq_cst);
                }
        }
 
@@ -932,7 +934,6 @@ void ModelExecution::w_modification_order(ModelAction *curr)
                /* Iterate over actions in thread, starting from most recent */
                action_list_t *list = &(*thrd_lists)[i];
                action_list_t::reverse_iterator rit;
-               bool force_edge = false;
                for (rit = list->rbegin();rit != list->rend();rit++) {
                        ModelAction *act = *rit;
                        if (act == curr) {
@@ -947,7 +948,6 @@ void ModelExecution::w_modification_order(ModelAction *curr)
                                 * 3) If normal write, we need to look at earlier actions, so
                                 * continue processing list.
                                 */
-                               force_edge = true;
                                if (curr->is_rmw()) {
                                        if (curr->get_reads_from() != NULL)
                                                break;
@@ -960,7 +960,7 @@ void ModelExecution::w_modification_order(ModelAction *curr)
                        /* C++, Section 29.3 statement 7 */
                        if (last_sc_fence_thread_before && act->is_write() &&
                                        *act < *last_sc_fence_thread_before) {
-                               mo_graph->addEdge(act, curr, force_edge);
+                               edgeset.push_back(act);
                                break;
                        }
 
@@ -976,15 +976,17 @@ void ModelExecution::w_modification_order(ModelAction *curr)
                                 *   readfrom(act) --mo--> act
                                 */
                                if (act->is_write())
-                                       mo_graph->addEdge(act, curr, force_edge);
+                                       edgeset.push_back(act);
                                else if (act->is_read()) {
                                        //if previous read accessed a null, just keep going
-                                       mo_graph->addEdge(act->get_reads_from(), curr, force_edge);
+                                       edgeset.push_back(act);
                                }
                                break;
                        }
                }
        }
+       mo_graph->addEdges(&edgeset, curr);
+
 }
 
 /**