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