From 9ade2b8c5ec2fc4bd6a556a37cccf896912367bf Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky@uci.edu>
Date: Sat, 27 Jul 2019 23:11:11 -0700
Subject: [PATCH] improve complexity

---
 cyclegraph.cc | 30 ++++++++++++++++++++++++++++++
 cyclegraph.h  |  1 +
 execution.cc  | 14 ++++++++------
 3 files changed, 39 insertions(+), 6 deletions(-)

diff --git a/cyclegraph.cc b/cyclegraph.cc
index 47951d4e..adafb0e1 100644
--- 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 e2b58640..3ea4e3bb 100644
--- 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 422b82a9..ac3ecbc0 100644
--- 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);
+
 }
 
 /**
-- 
2.34.1