cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3 #include "common.h"
   4
   5 /** Initializes a CycleGraph object. */
   6 CycleGraph::CycleGraph() :
   7         hasCycles(false),
   8         oldCycles(false),
   9         hasRMWViolation(false),
  10         oldRMWViolation(false)
  11 {
  12 }
  13
  14 /** CycleGraph destructor */
  15 CycleGraph::~CycleGraph() {
  16 }
  17
  18 /**
  19  * @brief Returns the CycleNode corresponding to a given ModelAction
  20  * @param action The ModelAction to find a node for
  21  * @return The CycleNode paired with this action
  22  */
  23 CycleNode * CycleGraph::getNode(const ModelAction *action) {
  24         CycleNode *node=actionToNode.get(action);
  25         if (node==NULL) {
  26                 node=new CycleNode(action);
  27                 actionToNode.put(action, node);
  28         }
  29         return node;
  30 }
  31
  32 /**
  33  * Adds an edge between two ModelActions. The ModelAction @a to is ordered
  34  * after the ModelAction @a from.
  35  * @param to The edge points to this ModelAction
  36  * @param from The edge comes from this ModelAction
  37  */
  38 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
  39         ASSERT(from);
  40         ASSERT(to);
  41
  42         CycleNode *fromnode=getNode(from);
  43         CycleNode *tonode=getNode(to);
  44
  45         if (!hasCycles) {
  46                 // Check for Cycles
  47                 hasCycles=checkReachable(tonode, fromnode);
  48         }
  49
  50         rollbackvector.push_back(fromnode);
  51         fromnode->addEdge(tonode);
  52
  53         CycleNode * rmwnode=fromnode->getRMW();
  54
  55         //If the fromnode has a rmwnode that is not the tonode, we
  56         //should add an edge between its rmwnode and the tonode
  57
  58         if (rmwnode!=NULL&&rmwnode!=tonode) {
  59                 if (!hasCycles) {
  60                         // Check for Cycles
  61                         hasCycles=checkReachable(tonode, rmwnode);
  62                 }
  63                 rollbackvector.push_back(rmwnode);
  64                 rmwnode->addEdge(tonode);
  65         }
  66 }
  67
  68 /** Handles special case of a RMW action.  The ModelAction rmw reads
  69  *  from the ModelAction from.  The key differences are: (1) no write
  70  *  can occur in between the rmw and the from action.  Only one RMW
  71  *  action can read from a given write.
  72  */
  73 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) {
  74         ASSERT(from);
  75         ASSERT(rmw);
  76
  77         CycleNode *fromnode=getNode(from);
  78         CycleNode *rmwnode=getNode(rmw);
  79
  80         /* Two RMW actions cannot read from the same write. */
  81         if (fromnode->setRMW(rmwnode)) {
  82                 hasRMWViolation=true;
  83         } else {
  84                 rmwrollbackvector.push_back(fromnode);
  85         }
  86
  87         /* Transfer all outgoing edges from the from node to the rmw node */
  88         /* This process should not add a cycle because either:
  89          * (1) The rmw should not have any incoming edges yet if it is the
  90          * new node or
  91          * (2) the fromnode is the new node and therefore it should not
  92          * have any outgoing edges.
  93          */
  94         std::vector<CycleNode *> * edges=fromnode->getEdges();
  95         for(unsigned int i=0;i<edges->size();i++) {
  96                 CycleNode * tonode=(*edges)[i];
  97                 rollbackvector.push_back(rmwnode);
  98                 rmwnode->addEdge(tonode);
  99         }
 100         rollbackvector.push_back(fromnode);
 101
 102         if (!hasCycles) {
 103                 // With promises we could be setting up a cycle here if we aren't
 104                 // careful...avoid it..
 105                 hasCycles=checkReachable(rmwnode, fromnode);
 106         }
 107         fromnode->addEdge(rmwnode);
 108 }
 109
 110 /**
 111  * Checks whether one ModelAction can reach another.
 112  * @param from The ModelAction from which to begin exploration
 113  * @param to The ModelAction to reach
 114  * @return True, @a from can reach @a to; otherwise, false
 115  */
 116 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) {
 117         CycleNode *fromnode = actionToNode.get(from);
 118         CycleNode *tonode = actionToNode.get(to);
 119
 120         if (!fromnode || !tonode)
 121                 return false;
 122
 123         return checkReachable(fromnode, tonode);
 124 }
 125
 126 /**
 127  * Checks whether one CycleNode can reach another.
 128  * @param from The CycleNode from which to begin exploration
 129  * @param to The CycleNode to reach
 130  * @return True, @a from can reach @a to; otherwise, false
 131  */
 132 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
 133         std::vector<CycleNode *> queue;
 134         HashTable<CycleNode *, CycleNode *, uintptr_t, 4> discovered;
 135
 136         queue.push_back(from);
 137         discovered.put(from, from);
 138         while(!queue.empty()) {
 139                 CycleNode * node=queue.back();
 140                 queue.pop_back();
 141                 if (node==to)
 142                         return true;
 143
 144                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
 145                         CycleNode *next=(*node->getEdges())[i];
 146                         if (!discovered.contains(next)) {
 147                                 discovered.put(next,next);
 148                                 queue.push_back(next);
 149                         }
 150                 }
 151         }
 152         return false;
 153 }
 154
 155 void CycleGraph::startChanges() {
 156         ASSERT(rollbackvector.size()==0);
 157         ASSERT(rmwrollbackvector.size()==0);
 158         ASSERT(oldCycles==hasCycles);
 159         ASSERT(oldRMWViolation==hasRMWViolation);
 160 }
 161
 162 /** Commit changes to the cyclegraph. */
 163 void CycleGraph::commitChanges() {
 164         rollbackvector.resize(0);
 165         rmwrollbackvector.resize(0);
 166         oldCycles=hasCycles;
 167         oldRMWViolation=hasRMWViolation;
 168 }
 169
 170 /** Rollback changes to the previous commit. */
 171 void CycleGraph::rollbackChanges() {
 172         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 173                 rollbackvector[i]->popEdge();
 174         }
 175
 176         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 177                 rmwrollbackvector[i]->clearRMW();
 178         }
 179
 180         hasCycles = oldCycles;
 181         hasRMWViolation = oldRMWViolation;
 182         rollbackvector.resize(0);
 183         rmwrollbackvector.resize(0);
 184 }
 185
 186 /** @returns whether a CycleGraph contains cycles. */
 187 bool CycleGraph::checkForCycles() {
 188         return hasCycles;
 189 }
 190
 191 bool CycleGraph::checkForRMWViolation() {
 192         return hasRMWViolation;
 193 }
 194
 195 /**
 196  * Constructor for a CycleNode.
 197  * @param modelaction The ModelAction for this node
 198  */
 199 CycleNode::CycleNode(const ModelAction *modelaction) :
 200         action(modelaction),
 201         hasRMW(NULL)
 202 {
 203 }
 204
 205 /** @returns a vector of the edges from a CycleNode. */
 206 std::vector<CycleNode *> * CycleNode::getEdges() {
 207         return &edges;
 208 }
 209
 210 /**
 211  * Adds an edge from this CycleNode to another CycleNode.
 212  * @param node The node to which we add a directed edge
 213  */
 214 void CycleNode::addEdge(CycleNode *node) {
 215         edges.push_back(node);
 216 }
 217
 218 /** @returns the RMW CycleNode that reads from the current CycleNode */
 219 CycleNode * CycleNode::getRMW() {
 220         return hasRMW;
 221 }
 222
 223 /**
 224  * Set a RMW action node that reads from the current CycleNode.
 225  * @param node The RMW that reads from the current node
 226  * @return True, if this node already was read by another RMW; false otherwise
 227  * @see CycleGraph::addRMWEdge
 228  */
 229 bool CycleNode::setRMW(CycleNode *node) {
 230         if (hasRMW!=NULL)
 231                 return true;
 232         hasRMW=node;
 233         return false;
 234 }