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 cannot add a cycle because rmw should not have any
  89                  incoming edges yet.*/
  90         std::vector<CycleNode *> * edges=fromnode->getEdges();
  91         for(unsigned int i=0;i<edges->size();i++) {
  92                 CycleNode * tonode=(*edges)[i];
  93                 rollbackvector.push_back(rmwnode);
  94                 rmwnode->addEdge(tonode);
  95         }
  96         rollbackvector.push_back(fromnode);
  97         fromnode->addEdge(rmwnode);
  98 }
  99
 100 /**
 101  * Checks whether one ModelAction can reach another.
 102  * @param from The ModelAction from which to begin exploration
 103  * @param to The ModelAction to reach
 104  * @return True, @a from can reach @a to; otherwise, false
 105  */
 106 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) {
 107         CycleNode *fromnode = actionToNode.get(from);
 108         CycleNode *tonode = actionToNode.get(to);
 109
 110         if (!fromnode || !tonode)
 111                 return false;
 112
 113         return checkReachable(fromnode, tonode);
 114 }
 115
 116 /**
 117  * Checks whether one CycleNode can reach another.
 118  * @param from The CycleNode from which to begin exploration
 119  * @param to The CycleNode to reach
 120  * @return True, @a from can reach @a to; otherwise, false
 121  */
 122 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
 123         std::vector<CycleNode *> queue;
 124         HashTable<CycleNode *, CycleNode *, uintptr_t, 4> discovered;
 125
 126         queue.push_back(from);
 127         discovered.put(from, from);
 128         while(!queue.empty()) {
 129                 CycleNode * node=queue.back();
 130                 queue.pop_back();
 131                 if (node==to)
 132                         return true;
 133
 134                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
 135                         CycleNode *next=(*node->getEdges())[i];
 136                         if (!discovered.contains(next)) {
 137                                 discovered.put(next,next);
 138                                 queue.push_back(next);
 139                         }
 140                 }
 141         }
 142         return false;
 143 }
 144
 145 void CycleGraph::startChanges() {
 146         ASSERT(rollbackvector.size()==0);
 147         ASSERT(rmwrollbackvector.size()==0);
 148         ASSERT(oldCycles==hasCycles);
 149         ASSERT(oldRMWViolation==hasRMWViolation);
 150 }
 151
 152 /** Commit changes to the cyclegraph. */
 153 void CycleGraph::commitChanges() {
 154         rollbackvector.resize(0);
 155         rmwrollbackvector.resize(0);
 156         oldCycles=hasCycles;
 157         oldRMWViolation=hasRMWViolation;
 158 }
 159
 160 /** Rollback changes to the previous commit. */
 161 void CycleGraph::rollbackChanges() {
 162         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 163                 rollbackvector[i]->popEdge();
 164         }
 165
 166         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 167                 rmwrollbackvector[i]->clearRMW();
 168         }
 169
 170         hasCycles = oldCycles;
 171         hasRMWViolation = oldRMWViolation;
 172         rollbackvector.resize(0);
 173         rmwrollbackvector.resize(0);
 174 }
 175
 176 /** @returns whether a CycleGraph contains cycles. */
 177 bool CycleGraph::checkForCycles() {
 178         return hasCycles;
 179 }
 180
 181 bool CycleGraph::checkForRMWViolation() {
 182         return hasRMWViolation;
 183 }
 184
 185 /**
 186  * Constructor for a CycleNode.
 187  * @param modelaction The ModelAction for this node
 188  */
 189 CycleNode::CycleNode(const ModelAction *modelaction) :
 190         action(modelaction),
 191         hasRMW(NULL)
 192 {
 193 }
 194
 195 /** @returns a vector of the edges from a CycleNode. */
 196 std::vector<CycleNode *> * CycleNode::getEdges() {
 197         return &edges;
 198 }
 199
 200 /**
 201  * Adds an edge from this CycleNode to another CycleNode.
 202  * @param node The node to which we add a directed edge
 203  */
 204 void CycleNode::addEdge(CycleNode *node) {
 205         edges.push_back(node);
 206 }
 207
 208 /** @returns the RMW CycleNode that reads from the current CycleNode */
 209 CycleNode * CycleNode::getRMW() {
 210         return hasRMW;
 211 }
 212
 213 /**
 214  * Set a RMW action node that reads from the current CycleNode.
 215  * @param node The RMW that reads from the current node
 216  * @return True, if this node already was read by another RMW; false otherwise
 217  * @see CycleGraph::addRMWEdge
 218  */
 219 bool CycleNode::setRMW(CycleNode *node) {
 220         if (hasRMW!=NULL)
 221                 return true;
 222         hasRMW=node;
 223         return false;
 224 }