cyclegraph.cc

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