cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3
   4 /** Initializes a CycleGraph object. */
   5 CycleGraph::CycleGraph() {
   6         hasCycles=false;
   7 }
   8
   9 CycleGraph::~CycleGraph() {
  10 }
  11
  12 /** Returns the CycleNode for a given ModelAction. */
  13 CycleNode * CycleGraph::getNode(const ModelAction * action) {
  14         CycleNode *node=actionToNode.get(action);
  15         if (node==NULL) {
  16                 node=new CycleNode(action);
  17                 actionToNode.put(action, node);
  18         }
  19         return node;
  20 }
  21
  22 /**
  23  * Adds an edge between two ModelActions.  The ModelAction to happens after the
  24  * ModelAction from.
  25  */
  26 void CycleGraph::addEdge(const ModelAction *to, const ModelAction *from) {
  27         CycleNode *fromnode=getNode(from);
  28         CycleNode *tonode=getNode(to);
  29
  30         if (!hasCycles) {
  31                 // Check for Cycles
  32                 hasCycles=checkReachable(tonode, fromnode);
  33         }
  34         fromnode->addEdge(tonode);
  35
  36         CycleNode * rmwnode=fromnode->getRMW();
  37
  38         //If the fromnode has a rmwnode that is not the tonode, we
  39         //should add an edge between its rmwnode and the tonode
  40
  41         if (rmwnode!=NULL&&rmwnode!=tonode) {
  42                 if (!hasCycles) {
  43                         // Check for Cycles
  44                         hasCycles=checkReachable(tonode, rmwnode);
  45                 }
  46                 rmwnode->addEdge(tonode);
  47         }
  48 }
  49
  50 /** Handles special case of a RMW action.  The ModelAction rmw reads
  51  *  from the ModelAction from.  The key differences are: (1) no write
  52  *  can occur in between the rmw and the from action.  Only one RMW
  53  *  action can read from a given write.
  54  */
  55 void CycleGraph::addRMWEdge(const ModelAction *rmw, const ModelAction * from) {
  56         CycleNode *fromnode=getNode(from);
  57         CycleNode *rmwnode=getNode(rmw);
  58
  59         /* Two RMW actions cannot read from the same write. */
  60         if (fromnode->setRMW(rmwnode)) {
  61                 hasCycles=true;
  62         }
  63
  64         /* Transfer all outgoing edges from the from node to the rmw node */
  65         /* This process cannot add a cycle because rmw should not have any
  66                  incoming edges yet.*/
  67         std::vector<CycleNode *> * edges=fromnode->getEdges();
  68         for(unsigned int i=0;i<edges->size();i++) {
  69                 CycleNode * tonode=(*edges)[i];
  70                 rmwnode->addEdge(tonode);
  71         }
  72
  73         fromnode->addEdge(rmwnode);
  74 }
  75
  76
  77 /** Checks whether the first CycleNode can reach the second one. */
  78 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
  79         std::vector<CycleNode *> queue;
  80         HashTable<CycleNode *, CycleNode *, uintptr_t, 4> discovered;
  81
  82         queue.push_back(from);
  83         discovered.put(from, from);
  84         while(!queue.empty()) {
  85                 CycleNode * node=queue.back();
  86                 queue.pop_back();
  87                 if (node==to)
  88                         return true;
  89
  90                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
  91                         CycleNode *next=(*node->getEdges())[i];
  92                         if (!discovered.contains(next)) {
  93                                 discovered.put(next,next);
  94                                 queue.push_back(next);
  95                         }
  96                 }
  97         }
  98         return false;
  99 }
 100
 101 /** Returns whether a CycleGraph contains cycles. */
 102 bool CycleGraph::checkForCycles() {
 103         return hasCycles;
 104 }
 105
 106 /** Constructor for a CycleNode. */
 107 CycleNode::CycleNode(const ModelAction *modelaction) {
 108         action=modelaction;
 109         hasRMW=NULL;
 110 }
 111
 112 /** Returns a vector of the edges from a CycleNode. */
 113 std::vector<CycleNode *> * CycleNode::getEdges() {
 114         return &edges;
 115 }
 116
 117 /** Adds an edge to a CycleNode. */
 118 void CycleNode::addEdge(CycleNode * node) {
 119         edges.push_back(node);
 120 }
 121
 122 /** Get the RMW CycleNode that reads from the current CycleNode. */
 123 CycleNode* CycleNode::getRMW() {
 124         return hasRMW;
 125 }
 126
 127 /** Set a RMW action node that reads from the current CycleNode. */
 128 bool CycleNode::setRMW(CycleNode * node) {
 129         CycleNode * oldhasRMW=hasRMW;
 130         hasRMW=node;
 131         return (oldhasRMW!=NULL);
 132 }