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, bool forceedge)
  63 {
  64         //quick check whether edge is redundant
  65         if (checkReachable(fromnode, tonode) && !forceedge) {
  66                 return;
  67         }
  68
  69         /*
  70          * If the fromnode has a rmwnode, we should
  71          * follow its RMW chain to add an edge at the end.
  72          */
  73         while (fromnode->getRMW()) {
  74                 CycleNode *nextnode = fromnode->getRMW();
  75                 if (nextnode == tonode)
  76                         break;
  77                 fromnode = nextnode;
  78         }
  79
  80         fromnode->addEdge(tonode);      //Add edge to edgeSrcNode
  81
  82         /* Propagate clock vector changes */
  83         if (tonode->cv->merge(fromnode->cv)) {
  84                 queue->push_back(tonode);
  85                 while(!queue->empty()) {
  86                         const CycleNode *node = queue->back();
  87                         queue->pop_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         /* We assume that this RMW has no RMW reading from it yet */
 118         ASSERT(!rmwnode->getRMW());
 119
 120         fromnode->setRMW(rmwnode);
 121
 122         /* Transfer all outgoing edges from the from node to the rmw node */
 123         /* This process should not add a cycle because either:
 124          * (1) The rmw should not have any incoming edges yet if it is the
 125          * new node or
 126          * (2) the fromnode is the new node and therefore it should not
 127          * have any outgoing edges.
 128          */
 129         for (unsigned int i = 0;i < fromnode->getNumEdges();i++) {
 130                 CycleNode *tonode = fromnode->getEdge(i);
 131                 if (tonode != rmwnode) {
 132                         rmwnode->addEdge(tonode);
 133                 }
 134         }
 135         fromnode->edges.clear();
 136
 137         addNodeEdge(fromnode, rmwnode, true);
 138 }
 139
 140 void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, const ModelAction *to) {
 141         for(sllnode<ModelAction*> * it = edgeset->begin();it!=NULL;) {
 142                 ModelAction *act = it->getVal();
 143                 CycleNode *node = getNode(act);
 144                 sllnode<ModelAction*> * it2 = it;
 145                 it2=it2->getNext();
 146                 for(;it2!=NULL; ) {
 147                         ModelAction *act2 = it2->getVal();
 148                         CycleNode *node2 = getNode(act2);
 149                         if (checkReachable(node, node2)) {
 150                                 it = edgeset->erase(it);
 151                                 goto endouterloop;
 152                         } else if (checkReachable(node2, node)) {
 153                                 it2 = edgeset->erase(it2);
 154                                 goto endinnerloop;
 155                         }
 156                         it2=it2->getNext();
 157 endinnerloop:
 158                         ;
 159                 }
 160                 it=it->getNext();
 161 endouterloop:
 162                 ;
 163         }
 164         for(sllnode<ModelAction*> *it = edgeset->begin();it!=NULL;it=it->getNext()) {
 165                 ModelAction *from = it->getVal();
 166                 addEdge(from, to, from->get_tid() == to->get_tid());
 167         }
 168 }
 169
 170 /**
 171  * @brief Adds an edge between objects
 172  *
 173  * This function will add an edge between any two objects which can be
 174  * associated with a CycleNode. That is, if they have a CycleGraph::getNode
 175  * implementation.
 176  *
 177  * The object to is ordered after the object from.
 178  *
 179  * @param to The edge points to this object, of type T
 180  * @param from The edge comes from this object, of type U
 181  * @return True, if new edge(s) are added; otherwise false
 182  */
 183
 184 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
 185 {
 186         ASSERT(from);
 187         ASSERT(to);
 188
 189         CycleNode *fromnode = getNode(from);
 190         CycleNode *tonode = getNode(to);
 191
 192         addNodeEdge(fromnode, tonode, false);
 193 }
 194
 195 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to, bool forceedge)
 196 {
 197         ASSERT(from);
 198         ASSERT(to);
 199
 200         CycleNode *fromnode = getNode(from);
 201         CycleNode *tonode = getNode(to);
 202
 203         addNodeEdge(fromnode, tonode, forceedge);
 204 }
 205
 206 #if SUPPORT_MOD_ORDER_DUMP
 207
 208 static void print_node(FILE *file, const CycleNode *node, int label)
 209 {
 210         const ModelAction *act = node->getAction();
 211         modelclock_t idx = act->get_seq_number();
 212         fprintf(file, "N%u", idx);
 213         if (label)
 214                 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
 215 }
 216
 217 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
 218 {
 219         print_node(file, from, 0);
 220         fprintf(file, " -> ");
 221         print_node(file, to, 0);
 222         if (prop && strlen(prop))
 223                 fprintf(file, " [%s]", prop);
 224         fprintf(file, ";\n");
 225 }
 226
 227 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
 228 {
 229         print_node(file, getNode(act), 1);
 230 }
 231
 232 void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop)
 233 {
 234         CycleNode *fromnode = getNode(from);
 235         CycleNode *tonode = getNode(to);
 236
 237         print_edge(file, fromnode, tonode, prop);
 238 }
 239
 240 void CycleGraph::dumpNodes(FILE *file) const
 241 {
 242         for (unsigned int i = 0;i < nodeList.size();i++) {
 243                 CycleNode *n = nodeList[i];
 244                 print_node(file, n, 1);
 245                 fprintf(file, ";\n");
 246                 if (n->getRMW())
 247                         print_edge(file, n, n->getRMW(), "style=dotted");
 248                 for (unsigned int j = 0;j < n->getNumEdges();j++)
 249                         print_edge(file, n, n->getEdge(j), NULL);
 250         }
 251 }
 252
 253 void CycleGraph::dumpGraphToFile(const char *filename) const
 254 {
 255         char buffer[200];
 256         sprintf(buffer, "%s.dot", filename);
 257         FILE *file = fopen(buffer, "w");
 258         fprintf(file, "digraph %s {\n", filename);
 259         dumpNodes(file);
 260         fprintf(file, "}\n");
 261         fclose(file);
 262 }
 263 #endif
 264
 265 /**
 266  * Checks whether one CycleNode can reach another.
 267  * @param from The CycleNode from which to begin exploration
 268  * @param to The CycleNode to reach
 269  * @return True, @a from can reach @a to; otherwise, false
 270  */
 271 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 272 {
 273         return to->cv->synchronized_since(from->action);
 274 }
 275
 276 /**
 277  * Checks whether one ModelAction can reach another ModelAction
 278  * @param from The ModelAction from which to begin exploration
 279  * @param to The ModelAction to reach
 280  * @return True, @a from can reach @a to; otherwise, false
 281  */
 282 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
 283 {
 284         CycleNode *fromnode = getNode_noCreate(from);
 285         CycleNode *tonode = getNode_noCreate(to);
 286
 287         if (!fromnode || !tonode)
 288                 return false;
 289
 290         return checkReachable(fromnode, tonode);
 291 }
 292
 293 /**
 294  * @brief Constructor for a CycleNode
 295  * @param act The ModelAction for this node
 296  */
 297 CycleNode::CycleNode(const ModelAction *act) :
 298         action(act),
 299         hasRMW(NULL),
 300         cv(new ClockVector(NULL, act))
 301 {
 302 }
 303
 304 /**
 305  * @param i The index of the edge to return
 306  * @returns The CycleNode edge indexed by i
 307  */
 308 CycleNode * CycleNode::getEdge(unsigned int i) const
 309 {
 310         return edges[i];
 311 }
 312
 313 /** @returns The number of edges leaving this CycleNode */
 314 unsigned int CycleNode::getNumEdges() const
 315 {
 316         return edges.size();
 317 }
 318
 319 /**
 320  * @brief Remove a (forward) edge from this CycleNode
 321  * @return The CycleNode which was popped, if one exists; otherwise NULL
 322  */
 323 CycleNode * CycleNode::removeEdge()
 324 {
 325         if (edges.empty())
 326                 return NULL;
 327
 328         CycleNode *ret = edges.back();
 329         edges.pop_back();
 330         return ret;
 331 }
 332
 333 /**
 334  * Adds an edge from this CycleNode to another CycleNode.
 335  * @param node The node to which we add a directed edge
 336  * @return True if this edge is a new edge; false otherwise
 337  */
 338 void CycleNode::addEdge(CycleNode *node)
 339 {
 340         for (unsigned int i = 0;i < edges.size();i++)
 341                 if (edges[i] == node)
 342                         return;
 343         edges.push_back(node);
 344 }
 345
 346 /** @returns the RMW CycleNode that reads from the current CycleNode */
 347 CycleNode * CycleNode::getRMW() const
 348 {
 349         return hasRMW;
 350 }
 351
 352 /**
 353  * Set a RMW action node that reads from the current CycleNode.
 354  * @param node The RMW that reads from the current node
 355  * @return True, if this node already was read by another RMW; false otherwise
 356  * @see CycleGraph::addRMWEdge
 357  */
 358 bool CycleNode::setRMW(CycleNode *node)
 359 {
 360         if (hasRMW != NULL)
 361                 return true;
 362         hasRMW = node;
 363         return false;
 364 }