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(fromnode);
  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 /**
 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, false);
 163 }
 164
 165 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to, bool forceedge)
 166 {
 167         ASSERT(from);
 168         ASSERT(to);
 169
 170         CycleNode *fromnode = getNode(from);
 171         CycleNode *tonode = getNode(to);
 172
 173         addNodeEdge(fromnode, tonode, forceedge);
 174 }
 175
 176 #if SUPPORT_MOD_ORDER_DUMP
 177
 178 static void print_node(FILE *file, const CycleNode *node, int label)
 179 {
 180         const ModelAction *act = node->getAction();
 181         modelclock_t idx = act->get_seq_number();
 182         fprintf(file, "N%u", idx);
 183         if (label)
 184                 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
 185 }
 186
 187 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
 188 {
 189         print_node(file, from, 0);
 190         fprintf(file, " -> ");
 191         print_node(file, to, 0);
 192         if (prop && strlen(prop))
 193                 fprintf(file, " [%s]", prop);
 194         fprintf(file, ";\n");
 195 }
 196
 197 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
 198 {
 199         print_node(file, getNode(act), 1);
 200 }
 201
 202 void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop)
 203 {
 204         CycleNode *fromnode = getNode(from);
 205         CycleNode *tonode = getNode(to);
 206
 207         print_edge(file, fromnode, tonode, prop);
 208 }
 209
 210 void CycleGraph::dumpNodes(FILE *file) const
 211 {
 212         for (unsigned int i = 0;i < nodeList.size();i++) {
 213                 CycleNode *n = nodeList[i];
 214                 print_node(file, n, 1);
 215                 fprintf(file, ";\n");
 216                 if (n->getRMW())
 217                         print_edge(file, n, n->getRMW(), "style=dotted");
 218                 for (unsigned int j = 0;j < n->getNumEdges();j++)
 219                         print_edge(file, n, n->getEdge(j), NULL);
 220         }
 221 }
 222
 223 void CycleGraph::dumpGraphToFile(const char *filename) const
 224 {
 225         char buffer[200];
 226         sprintf(buffer, "%s.dot", filename);
 227         FILE *file = fopen(buffer, "w");
 228         fprintf(file, "digraph %s {\n", filename);
 229         dumpNodes(file);
 230         fprintf(file, "}\n");
 231         fclose(file);
 232 }
 233 #endif
 234
 235 /**
 236  * Checks whether one CycleNode can reach another.
 237  * @param from The CycleNode from which to begin exploration
 238  * @param to The CycleNode to reach
 239  * @return True, @a from can reach @a to; otherwise, false
 240  */
 241 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 242 {
 243         return to->cv->synchronized_since(from->action);
 244 }
 245
 246 /**
 247  * Checks whether one ModelAction can reach another ModelAction
 248  * @param from The ModelAction from which to begin exploration
 249  * @param to The ModelAction to reach
 250  * @return True, @a from can reach @a to; otherwise, false
 251  */
 252 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
 253 {
 254         CycleNode *fromnode = getNode_noCreate(from);
 255         CycleNode *tonode = getNode_noCreate(to);
 256
 257         if (!fromnode || !tonode)
 258                 return false;
 259
 260         return checkReachable(fromnode, tonode);
 261 }
 262
 263 /**
 264  * @brief Constructor for a CycleNode
 265  * @param act The ModelAction for this node
 266  */
 267 CycleNode::CycleNode(const ModelAction *act) :
 268         action(act),
 269         hasRMW(NULL),
 270         cv(new ClockVector(NULL, act))
 271 {
 272 }
 273
 274 /**
 275  * @param i The index of the edge to return
 276  * @returns The CycleNode edge indexed by i
 277  */
 278 CycleNode * CycleNode::getEdge(unsigned int i) const
 279 {
 280         return edges[i];
 281 }
 282
 283 /** @returns The number of edges leaving this CycleNode */
 284 unsigned int CycleNode::getNumEdges() const
 285 {
 286         return edges.size();
 287 }
 288
 289 /**
 290  * @brief Remove a (forward) edge from this CycleNode
 291  * @return The CycleNode which was popped, if one exists; otherwise NULL
 292  */
 293 CycleNode * CycleNode::removeEdge()
 294 {
 295         if (edges.empty())
 296                 return NULL;
 297
 298         CycleNode *ret = edges.back();
 299         edges.pop_back();
 300         return ret;
 301 }
 302
 303 /**
 304  * Adds an edge from this CycleNode to another CycleNode.
 305  * @param node The node to which we add a directed edge
 306  * @return True if this edge is a new edge; false otherwise
 307  */
 308 void CycleNode::addEdge(CycleNode *node)
 309 {
 310         for (unsigned int i = 0;i < edges.size();i++)
 311                 if (edges[i] == node)
 312                         return;
 313         edges.push_back(node);
 314 }
 315
 316 /** @returns the RMW CycleNode that reads from the current CycleNode */
 317 CycleNode * CycleNode::getRMW() const
 318 {
 319         return hasRMW;
 320 }
 321
 322 /**
 323  * Set a RMW action node that reads from the current CycleNode.
 324  * @param node The RMW that reads from the current node
 325  * @return True, if this node already was read by another RMW; false otherwise
 326  * @see CycleGraph::addRMWEdge
 327  */
 328 bool CycleNode::setRMW(CycleNode *node)
 329 {
 330         if (hasRMW != NULL)
 331                 return true;
 332         hasRMW = node;
 333         return false;
 334 }