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 /** Commit changes to the cyclegraph. */
 144 void CycleGraph::commitChanges() {
 145         rollbackvector.resize(0);
 146         rmwrollbackvector.resize(0);
 147         oldCycles=hasCycles;
 148 }
 149
 150 /** Rollback changes to the previous commit. */
 151 void CycleGraph::rollbackChanges() {
 152         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 153                 rollbackvector[i]->popEdge();
 154         }
 155
 156         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 157                 rmwrollbackvector[i]->clearRMW();
 158         }
 159
 160         hasCycles = oldCycles;
 161         rollbackvector.resize(0);
 162         rmwrollbackvector.resize(0);
 163 }
 164
 165 /** @returns whether a CycleGraph contains cycles. */
 166 bool CycleGraph::checkForCycles() {
 167         return hasCycles;
 168 }
 169
 170 /**
 171  * Constructor for a CycleNode.
 172  * @param modelaction The ModelAction for this node
 173  */
 174 CycleNode::CycleNode(const ModelAction *modelaction) :
 175         action(modelaction),
 176         hasRMW(NULL)
 177 {
 178 }
 179
 180 /** @returns a vector of the edges from a CycleNode. */
 181 std::vector<CycleNode *> * CycleNode::getEdges() {
 182         return &edges;
 183 }
 184
 185 /**
 186  * Adds an edge from this CycleNode to another CycleNode.
 187  * @param node The node to which we add a directed edge
 188  */
 189 void CycleNode::addEdge(CycleNode *node) {
 190         edges.push_back(node);
 191 }
 192
 193 /** @returns the RMW CycleNode that reads from the current CycleNode */
 194 CycleNode * CycleNode::getRMW() {
 195         return hasRMW;
 196 }
 197
 198 /**
 199  * Set a RMW action node that reads from the current CycleNode.
 200  * @param node The RMW that reads from the current node
 201  * @return True, if this node already was read by another RMW; false otherwise
 202  * @see CycleGraph::addRMWEdge
 203  */
 204 bool CycleNode::setRMW(CycleNode *node) {
 205         if (hasRMW!=NULL)
 206                 return true;
 207         hasRMW=node;
 208         return false;
 209 }