lots of debugging here... finally working with my rmw example...

[model-checker.git] / cyclegraph.cc

diff --git a/cyclegraph.cc b/cyclegraph.cc
index 967b0763abbdcdba0ec35cdd2608cb0fa94caa13..0a3d8858e795849f16ab1cae667b2e34bb1367cc 100644 (file)
--- a/cyclegraph.cc
+++ b/cyclegraph.cc
@@ -1,10 +1,13 @@
 #include "cyclegraph.h"
 #include "action.h"
+#include "common.h"
 
 /** Initializes a CycleGraph object. */
 CycleGraph::CycleGraph() :
        hasCycles(false),
-       oldCycles(false)
+       oldCycles(false),
+       hasRMWViolation(false),
+       oldRMWViolation(false)
 {
 }
 
@@ -33,6 +36,9 @@ CycleNode * CycleGraph::getNode(const ModelAction *action) {
  * @param from The edge comes from this ModelAction
  */
 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
+       ASSERT(from);
+       ASSERT(to);
+
        CycleNode *fromnode=getNode(from);
        CycleNode *tonode=getNode(to);
 
@@ -49,7 +55,11 @@ void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
        //If the fromnode has a rmwnode that is not the tonode, we
        //should add an edge between its rmwnode and the tonode
 
-       if (rmwnode!=NULL&&rmwnode!=tonode) {
+       //If tonode is also a rmw, don't do this check as the execution is
+       //doomed and we'll catch the problem elsewhere, but we want to allow
+       //for the possibility of sending to's write value to rmwnode
+
+       if (rmwnode!=NULL&&!to->is_rmw()) {
                if (!hasCycles) {
                        // Check for Cycles
                        hasCycles=checkReachable(tonode, rmwnode);
@@ -65,26 +75,41 @@ void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
  *  action can read from a given write.
  */
 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) {
+       ASSERT(from);
+       ASSERT(rmw);
+
        CycleNode *fromnode=getNode(from);
        CycleNode *rmwnode=getNode(rmw);
 
        /* Two RMW actions cannot read from the same write. */
        if (fromnode->setRMW(rmwnode)) {
-               hasCycles=true;
+               hasRMWViolation=true;
        } else {
                rmwrollbackvector.push_back(fromnode);
        }
 
        /* Transfer all outgoing edges from the from node to the rmw node */
-       /* This process cannot add a cycle because rmw should not have any
-                incoming edges yet.*/
+       /* This process should not add a cycle because either: 
+        * (1) The rmw should not have any incoming edges yet if it is the
+        * new node or
+        * (2) the fromnode is the new node and therefore it should not 
+        * have any outgoing edges.
+        */
        std::vector<CycleNode *> * edges=fromnode->getEdges();
        for(unsigned int i=0;i<edges->size();i++) {
                CycleNode * tonode=(*edges)[i];
-               rollbackvector.push_back(rmwnode);
-               rmwnode->addEdge(tonode);
+               if (tonode!=rmwnode) {
+                       rollbackvector.push_back(rmwnode);
+                       rmwnode->addEdge(tonode);
+               }
        }
        rollbackvector.push_back(fromnode);
+
+       if (!hasCycles) {
+               // With promises we could be setting up a cycle here if we aren't
+               // careful...avoid it..
+               hasCycles=checkReachable(rmwnode, fromnode);
+       }
        fromnode->addEdge(rmwnode);
 }
 
@@ -133,11 +158,19 @@ bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
        return false;
 }
 
+void CycleGraph::startChanges() {
+       ASSERT(rollbackvector.size()==0);
+       ASSERT(rmwrollbackvector.size()==0);
+       ASSERT(oldCycles==hasCycles);
+       ASSERT(oldRMWViolation==hasRMWViolation);
+}
+
 /** Commit changes to the cyclegraph. */
 void CycleGraph::commitChanges() {
        rollbackvector.resize(0);
        rmwrollbackvector.resize(0);
        oldCycles=hasCycles;
+       oldRMWViolation=hasRMWViolation;
 }
 
 /** Rollback changes to the previous commit. */
@@ -151,6 +184,7 @@ void CycleGraph::rollbackChanges() {
        }
 
        hasCycles = oldCycles;
+       hasRMWViolation = oldRMWViolation;
        rollbackvector.resize(0);
        rmwrollbackvector.resize(0);
 }
@@ -160,6 +194,10 @@ bool CycleGraph::checkForCycles() {
        return hasCycles;
 }
 
+bool CycleGraph::checkForRMWViolation() {
+       return hasRMWViolation;
+}
+
 /**
  * Constructor for a CycleNode.
  * @param modelaction The ModelAction for this node