1 #include "cyclegraph.h"
4 #include "threads-model.h"
5 #include "clockvector.h"
7 /** Initializes a CycleGraph object. */
8 CycleGraph::CycleGraph() :
9 queue(new SnapVector<const CycleNode *>())
13 /** CycleGraph destructor */
14 CycleGraph::~CycleGraph()
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
24 void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
26 actionToNode.put(act, node);
27 #if SUPPORT_MOD_ORDER_DUMP
28 nodeList.push_back(node);
32 /** @return The corresponding CycleNode, if exists; otherwise NULL */
33 CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
35 return actionToNode.get(act);
39 * @brief Returns the CycleNode corresponding to a given ModelAction
41 * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
43 * @param action The ModelAction to find a node for
44 * @return The CycleNode paired with this action
46 CycleNode * CycleGraph::getNode(ModelAction *action)
48 CycleNode *node = getNode_noCreate(action);
50 node = new CycleNode(action);
51 putNode(action, node);
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
62 void CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode, bool forceedge)
64 //quick check whether edge is redundant
65 if (checkReachable(fromnode, tonode) && !forceedge) {
70 * If the fromnode has a rmwnode, we should
71 * follow its RMW chain to add an edge at the end.
73 while (fromnode->getRMW()) {
74 CycleNode *nextnode = fromnode->getRMW();
75 if (nextnode == tonode)
80 fromnode->addEdge(tonode); //Add edge to edgeSrcNode
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();
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);
99 * @brief Add an edge between a write and the RMW which reads from it
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.
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
110 void CycleGraph::addRMWEdge(ModelAction *from, ModelAction *rmw)
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());
120 fromnode->setRMW(rmwnode);
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
126 * (2) the fromnode is the new node and therefore it should not
127 * have any outgoing edges.
129 for (unsigned int i = 0;i < fromnode->getNumEdges();i++) {
130 CycleNode *tonode = fromnode->getEdge(i);
131 if (tonode != rmwnode) {
132 rmwnode->addEdge(tonode);
134 tonode->removeInEdge(fromnode);
136 fromnode->edges.clear();
138 addNodeEdge(fromnode, rmwnode, true);
141 void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, ModelAction *to) {
142 for(sllnode<ModelAction*> * it = edgeset->begin();it!=NULL;) {
143 ModelAction *act = it->getVal();
144 CycleNode *node = getNode(act);
145 sllnode<ModelAction*> * it2 = it;
148 ModelAction *act2 = it2->getVal();
149 CycleNode *node2 = getNode(act2);
150 if (checkReachable(node, node2)) {
151 it = edgeset->erase(it);
153 } else if (checkReachable(node2, node)) {
154 it2 = edgeset->erase(it2);
165 for(sllnode<ModelAction*> *it = edgeset->begin();it!=NULL;it=it->getNext()) {
166 ModelAction *from = it->getVal();
167 addEdge(from, to, from->get_tid() == to->get_tid());
172 * @brief Adds an edge between objects
174 * This function will add an edge between any two objects which can be
175 * associated with a CycleNode. That is, if they have a CycleGraph::getNode
178 * The object to is ordered after the object from.
180 * @param to The edge points to this object, of type T
181 * @param from The edge comes from this object, of type U
182 * @return True, if new edge(s) are added; otherwise false
185 void CycleGraph::addEdge(ModelAction *from, ModelAction *to)
190 CycleNode *fromnode = getNode(from);
191 CycleNode *tonode = getNode(to);
193 addNodeEdge(fromnode, tonode, false);
196 void CycleGraph::addEdge(ModelAction *from, ModelAction *to, bool forceedge)
201 CycleNode *fromnode = getNode(from);
202 CycleNode *tonode = getNode(to);
204 addNodeEdge(fromnode, tonode, forceedge);
207 #if SUPPORT_MOD_ORDER_DUMP
209 static void print_node(FILE *file, const CycleNode *node, int label)
211 const ModelAction *act = node->getAction();
212 modelclock_t idx = act->get_seq_number();
213 fprintf(file, "N%u", idx);
215 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
218 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
220 print_node(file, from, 0);
221 fprintf(file, " -> ");
222 print_node(file, to, 0);
223 if (prop && strlen(prop))
224 fprintf(file, " [%s]", prop);
225 fprintf(file, ";\n");
228 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
230 print_node(file, getNode(act), 1);
233 void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop)
235 CycleNode *fromnode = getNode(from);
236 CycleNode *tonode = getNode(to);
238 print_edge(file, fromnode, tonode, prop);
241 void CycleGraph::dumpNodes(FILE *file) const
243 for (unsigned int i = 0;i < nodeList.size();i++) {
244 CycleNode *n = nodeList[i];
245 print_node(file, n, 1);
246 fprintf(file, ";\n");
248 print_edge(file, n, n->getRMW(), "style=dotted");
249 for (unsigned int j = 0;j < n->getNumEdges();j++)
250 print_edge(file, n, n->getEdge(j), NULL);
254 void CycleGraph::dumpGraphToFile(const char *filename) const
257 sprintf(buffer, "%s.dot", filename);
258 FILE *file = fopen(buffer, "w");
259 fprintf(file, "digraph %s {\n", filename);
261 fprintf(file, "}\n");
267 * Checks whether one CycleNode can reach another.
268 * @param from The CycleNode from which to begin exploration
269 * @param to The CycleNode to reach
270 * @return True, @a from can reach @a to; otherwise, false
272 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
274 return to->cv->synchronized_since(from->action);
278 * Checks whether one ModelAction can reach another ModelAction
279 * @param from The ModelAction from which to begin exploration
280 * @param to The ModelAction to reach
281 * @return True, @a from can reach @a to; otherwise, false
283 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
285 CycleNode *fromnode = getNode_noCreate(from);
286 CycleNode *tonode = getNode_noCreate(to);
288 if (!fromnode || !tonode)
291 return checkReachable(fromnode, tonode);
294 void CycleGraph::freeAction(const ModelAction * act) {
295 CycleNode *cn = actionToNode.remove(act);
296 for(unsigned int i=0;i<cn->edges.size();i++) {
297 CycleNode *dst = cn->edges[i];
298 dst->removeInEdge(cn);
300 for(unsigned int i=0;i<cn->inedges.size();i++) {
301 CycleNode *src = cn->inedges[i];
308 * @brief Constructor for a CycleNode
309 * @param act The ModelAction for this node
311 CycleNode::CycleNode(ModelAction *act) :
314 cv(new ClockVector(NULL, act))
318 CycleNode::~CycleNode() {
322 void CycleNode::removeInEdge(CycleNode *src) {
323 for(unsigned int i=0;i < inedges.size();i++) {
324 if (inedges[i] == src) {
325 inedges[i] = inedges[inedges.size()-1];
332 void CycleNode::removeEdge(CycleNode *dst) {
333 for(unsigned int i=0;i < edges.size();i++) {
334 if (edges[i] == dst) {
335 edges[i] = edges[edges.size()-1];
343 * @param i The index of the edge to return
344 * @returns The CycleNode edge indexed by i
346 CycleNode * CycleNode::getEdge(unsigned int i) const
351 /** @returns The number of edges leaving this CycleNode */
352 unsigned int CycleNode::getNumEdges() const
358 * @param i The index of the edge to return
359 * @returns The CycleNode edge indexed by i
361 CycleNode * CycleNode::getInEdge(unsigned int i) const
366 /** @returns The number of edges leaving this CycleNode */
367 unsigned int CycleNode::getNumInEdges() const
369 return inedges.size();
373 * Adds an edge from this CycleNode to another CycleNode.
374 * @param node The node to which we add a directed edge
375 * @return True if this edge is a new edge; false otherwise
377 void CycleNode::addEdge(CycleNode *node)
379 for (unsigned int i = 0;i < edges.size();i++)
380 if (edges[i] == node)
382 edges.push_back(node);
383 node->inedges.push_back(this);
386 /** @returns the RMW CycleNode that reads from the current CycleNode */
387 CycleNode * CycleNode::getRMW() const
393 * Set a RMW action node that reads from the current CycleNode.
394 * @param node The RMW that reads from the current node
395 * @return True, if this node already was read by another RMW; false otherwise
396 * @see CycleGraph::addRMWEdge
398 bool CycleNode::setRMW(CycleNode *node)