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