cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3 #include "common.h"
   4 #include "threads-model.h"
   5 #include "clockvector.h"
   6
   7 /** Initializes a CycleGraph object. */
   8 CycleGraph::CycleGraph() :
   9         queue(new SnapVector<const CycleNode *>())
  10 {
  11 }
  12
  13 /** CycleGraph destructor */
  14 CycleGraph::~CycleGraph()
  15 {
  16         delete queue;
  17 }
  18
  19 /**
  20  * Add a CycleNode to the graph, corresponding to a store ModelAction
  21  * @param act The write action that should be added
  22  * @param node The CycleNode that corresponds to the store
  23  */
  24 void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
  25 {
  26         actionToNode.put(act, node);
  27 #if SUPPORT_MOD_ORDER_DUMP
  28         nodeList.push_back(node);
  29 #endif
  30 }
  31
  32 /** @return The corresponding CycleNode, if exists; otherwise NULL */
  33 CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
  34 {
  35         return actionToNode.get(act);
  36 }
  37
  38 /**
  39  * @brief Returns the CycleNode corresponding to a given ModelAction
  40  *
  41  * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
  42  *
  43  * @param action The ModelAction to find a node for
  44  * @return The CycleNode paired with this action
  45  */
  46 CycleNode * CycleGraph::getNode(const ModelAction *action)
  47 {
  48         CycleNode *node = getNode_noCreate(action);
  49         if (node == NULL) {
  50                 node = new CycleNode(action);
  51                 putNode(action, node);
  52         }
  53         return node;
  54 }
  55
  56 /**
  57  * Adds an edge between two CycleNodes.
  58  * @param fromnode The edge comes from this CycleNode
  59  * @param tonode The edge points to this CycleNode
  60  * @return True, if new edge(s) are added; otherwise false
  61  */
  62 void CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
  63 {
  64         //quick check whether edge is redundant
  65         if (checkReachable(fromnode, tonode))
  66                 return;
  67
  68         CycleNode *edgeSrcNode = fromnode;
  69
  70         /*
  71          * If the fromnode has a rmwnode, we should
  72          * follow its RMW chain to add an edge at the end.
  73          */
  74         CycleNode *rmwnode = fromnode->getRMW();
  75         if (rmwnode) {
  76                 while (rmwnode->getRMW())
  77                         rmwnode = rmwnode->getRMW();
  78                 edgeSrcNode = rmwnode;
  79         }
  80
  81         edgeSrcNode->addEdge(tonode);   //Add edge to edgeSrcNode
  82
  83         /* Propagate clock vector changes */
  84         if (tonode->cv->merge(edgeSrcNode->cv)) {
  85                 queue->push_back(edgeSrcNode);
  86                 while(!queue->empty()) {
  87                         const CycleNode *node = queue->back();
  88                         unsigned int numedges = node->getNumEdges();
  89                         for(unsigned int i = 0;i < numedges;i++) {
  90                                 CycleNode * enode = node->getEdge(i);
  91                                 if (enode->cv->merge(node->cv))
  92                                         queue->push_back(enode);
  93                         }
  94                 }
  95         }
  96 }
  97
  98 /**
  99  * @brief Add an edge between a write and the RMW which reads from it
 100  *
 101  * Handles special case of a RMW action, where the ModelAction rmw reads from
 102  * the ModelAction from. The key differences are:
 103  *  -# No write can occur in between the @a rmw and @a from actions.
 104  *  -# Only one RMW action can read from a given write.
 105  *
 106  * @param from The edge comes from this ModelAction
 107  * @param rmw The edge points to this ModelAction; this action must read from
 108  * the ModelAction from
 109  */
 110 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
 111 {
 112         ASSERT(from);
 113         ASSERT(rmw);
 114
 115         CycleNode *fromnode = getNode(from);
 116         CycleNode *rmwnode = getNode(rmw);
 117
 118         /* We assume that this RMW has no RMW reading from it yet */
 119         ASSERT(!rmwnode->getRMW());
 120
 121         fromnode->setRMW(rmwnode);
 122
 123         /* Transfer all outgoing edges from the from node to the rmw node */
 124         /* This process should not add a cycle because either:
 125          * (1) The rmw should not have any incoming edges yet if it is the
 126          * new node or
 127          * (2) the fromnode is the new node and therefore it should not
 128          * have any outgoing edges.
 129          */
 130         for (unsigned int i = 0;i < fromnode->getNumEdges();i++) {
 131                 CycleNode *tonode = fromnode->getEdge(i);
 132                 if (tonode != rmwnode) {
 133                         rmwnode->addEdge(tonode);
 134                 }
 135         }
 136
 137         addNodeEdge(fromnode, rmwnode);
 138 }
 139
 140 /**
 141  * @brief Adds an edge between objects
 142  *
 143  * This function will add an edge between any two objects which can be
 144  * associated with a CycleNode. That is, if they have a CycleGraph::getNode
 145  * implementation.
 146  *
 147  * The object to is ordered after the object from.
 148  *
 149  * @param to The edge points to this object, of type T
 150  * @param from The edge comes from this object, of type U
 151  * @return True, if new edge(s) are added; otherwise false
 152  */
 153
 154 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
 155 {
 156         ASSERT(from);
 157         ASSERT(to);
 158
 159         CycleNode *fromnode = getNode(from);
 160         CycleNode *tonode = getNode(to);
 161
 162         addNodeEdge(fromnode, tonode);
 163 }
 164
 165 #if SUPPORT_MOD_ORDER_DUMP
 166
 167 static void print_node(FILE *file, const CycleNode *node, int label)
 168 {
 169         const ModelAction *act = node->getAction();
 170         modelclock_t idx = act->get_seq_number();
 171         fprintf(file, "N%u", idx);
 172         if (label)
 173                 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
 174 }
 175
 176 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
 177 {
 178         print_node(file, from, 0);
 179         fprintf(file, " -> ");
 180         print_node(file, to, 0);
 181         if (prop && strlen(prop))
 182                 fprintf(file, " [%s]", prop);
 183         fprintf(file, ";\n");
 184 }
 185
 186 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
 187 {
 188         print_node(file, getNode(act), 1);
 189 }
 190
 191 void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop)
 192 {
 193         CycleNode *fromnode = getNode(from);
 194         CycleNode *tonode = getNode(to);
 195
 196         print_edge(file, fromnode, tonode, prop);
 197 }
 198
 199 void CycleGraph::dumpNodes(FILE *file) const
 200 {
 201         for (unsigned int i = 0;i < nodeList.size();i++) {
 202                 CycleNode *n = nodeList[i];
 203                 print_node(file, n, 1);
 204                 fprintf(file, ";\n");
 205                 if (n->getRMW())
 206                         print_edge(file, n, n->getRMW(), "style=dotted");
 207                 for (unsigned int j = 0;j < n->getNumEdges();j++)
 208                         print_edge(file, n, n->getEdge(j), NULL);
 209         }
 210 }
 211
 212 void CycleGraph::dumpGraphToFile(const char *filename) const
 213 {
 214         char buffer[200];
 215         sprintf(buffer, "%s.dot", filename);
 216         FILE *file = fopen(buffer, "w");
 217         fprintf(file, "digraph %s {\n", filename);
 218         dumpNodes(file);
 219         fprintf(file, "}\n");
 220         fclose(file);
 221 }
 222 #endif
 223
 224 /**
 225  * Checks whether one CycleNode can reach another.
 226  * @param from The CycleNode from which to begin exploration
 227  * @param to The CycleNode to reach
 228  * @return True, @a from can reach @a to; otherwise, false
 229  */
 230 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 231 {
 232         return to->cv->synchronized_since(from->action);
 233 }
 234
 235 /**
 236  * Checks whether one ModelAction can reach another ModelAction
 237  * @param from The ModelAction from which to begin exploration
 238  * @param to The ModelAction to reach
 239  * @return True, @a from can reach @a to; otherwise, false
 240  */
 241 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
 242 {
 243         CycleNode *fromnode = getNode_noCreate(from);
 244         CycleNode *tonode = getNode_noCreate(to);
 245
 246         if (!fromnode || !tonode)
 247                 return false;
 248
 249         return checkReachable(fromnode, tonode);
 250 }
 251
 252 /**
 253  * @brief Constructor for a CycleNode
 254  * @param act The ModelAction for this node
 255  */
 256 CycleNode::CycleNode(const ModelAction *act) :
 257         action(act),
 258         hasRMW(NULL),
 259         cv(new ClockVector(NULL, act))
 260 {
 261 }
 262
 263 /**
 264  * @param i The index of the edge to return
 265  * @returns The CycleNode edge indexed by i
 266  */
 267 CycleNode * CycleNode::getEdge(unsigned int i) const
 268 {
 269         return edges[i];
 270 }
 271
 272 /** @returns The number of edges leaving this CycleNode */
 273 unsigned int CycleNode::getNumEdges() const
 274 {
 275         return edges.size();
 276 }
 277
 278 /**
 279  * @brief Remove a (forward) edge from this CycleNode
 280  * @return The CycleNode which was popped, if one exists; otherwise NULL
 281  */
 282 CycleNode * CycleNode::removeEdge()
 283 {
 284         if (edges.empty())
 285                 return NULL;
 286
 287         CycleNode *ret = edges.back();
 288         edges.pop_back();
 289         return ret;
 290 }
 291
 292 /**
 293  * Adds an edge from this CycleNode to another CycleNode.
 294  * @param node The node to which we add a directed edge
 295  * @return True if this edge is a new edge; false otherwise
 296  */
 297 void CycleNode::addEdge(CycleNode *node)
 298 {
 299         for (unsigned int i = 0;i < edges.size();i++)
 300                 if (edges[i] == node)
 301                         return;
 302         edges.push_back(node);
 303 }
 304
 305 /** @returns the RMW CycleNode that reads from the current CycleNode */
 306 CycleNode * CycleNode::getRMW() const
 307 {
 308         return hasRMW;
 309 }
 310
 311 /**
 312  * Set a RMW action node that reads from the current CycleNode.
 313  * @param node The RMW that reads from the current node
 314  * @return True, if this node already was read by another RMW; false otherwise
 315  * @see CycleGraph::addRMWEdge
 316  */
 317 bool CycleNode::setRMW(CycleNode *node)
 318 {
 319         if (hasRMW != NULL)
 320                 return true;
 321         hasRMW = node;
 322         return false;
 323 }