/builds/2mk6rsew/0/parcoach/parcoach/src/aSSA/andersen/ConstraintSolving.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | #include "parcoach/andersen/Andersen.h" |
2 | | #include "parcoach/andersen/CycleDetector.h" |
3 | | #include "parcoach/andersen/SparseBitVectorGraph.h" |
4 | | |
5 | | #include "llvm/ADT/DenseMap.h" |
6 | | #include "llvm/ADT/DenseSet.h" |
7 | | #include "llvm/ADT/SmallSet.h" |
8 | | #include "llvm/ADT/iterator_range.h" |
9 | | #include "llvm/Support/CommandLine.h" |
10 | | #include "llvm/Support/raw_ostream.h" |
11 | | |
12 | | #include <map> |
13 | | #include <queue> |
14 | | |
15 | | using namespace llvm; |
16 | | |
17 | | cl::opt<bool> EnableHCD("enable-hcd", |
18 | | cl::desc("Enable the hybrid cycle detection algorithm"), |
19 | | cl::init(true)); |
20 | | cl::opt<bool> EnableLCD("enable-lcd", |
21 | | cl::desc("Enable the lazy cycle detection algorithm"), |
22 | | cl::init(true)); |
23 | | |
24 | | namespace { |
25 | | |
26 | | // This class represent the constraint graph |
27 | | class ConstraintGraphNode { |
28 | | private: |
29 | | NodeIndex idx; |
30 | | |
31 | | // We use set rather than SmallSet because we need the capability of iteration |
32 | | typedef std::set<NodeIndex> NodeSet; |
33 | | NodeSet copyEdges, loadEdges, storeEdges; |
34 | | |
35 | 109k | bool insertCopyEdge(NodeIndex dst) { return copyEdges.insert(dst).second; } |
36 | 0 | bool removeCopyEdge(NodeIndex dst) { return copyEdges.erase(dst); } |
37 | 24.9k | bool insertLoadEdge(NodeIndex dst) { return loadEdges.insert(dst).second; } |
38 | 0 | bool removeLoadEdge(NodeIndex dst) { return loadEdges.erase(dst); } |
39 | 12.6k | bool insertStoreEdge(NodeIndex dst) { return storeEdges.insert(dst).second; } |
40 | 0 | bool removeStoreEdge(NodeIndex dst) { return storeEdges.erase(dst); } |
41 | 0 | bool isEmpty() const { |
42 | 0 | return copyEdges.empty() && loadEdges.empty() && storeEdges.empty(); |
43 | 0 | } |
44 | | |
45 | 0 | void mergeEdges(ConstraintGraphNode const &other) { |
46 | 0 | copyEdges.insert(other.copyEdges.begin(), other.copyEdges.end()); |
47 | 0 | loadEdges.insert(other.loadEdges.begin(), other.loadEdges.end()); |
48 | 0 | storeEdges.insert(other.storeEdges.begin(), other.storeEdges.end()); |
49 | 0 | } |
50 | | |
51 | 41.8k | ConstraintGraphNode(NodeIndex i) : idx(i) {} |
52 | | |
53 | | public: |
54 | | typedef NodeSet::iterator iterator; |
55 | | typedef NodeSet::const_iterator const_iterator; |
56 | | |
57 | 0 | NodeIndex getNodeIndex() const { return idx; } |
58 | | |
59 | 0 | bool replaceCopyEdge(NodeIndex oldIdx, NodeIndex newIdx) { |
60 | 0 | return removeCopyEdge(oldIdx) && insertCopyEdge(newIdx); |
61 | 0 | } |
62 | 0 | bool replaceLoadEdge(NodeIndex oldIdx, NodeIndex newIdx) { |
63 | 0 | return removeLoadEdge(oldIdx) && insertLoadEdge(newIdx); |
64 | 0 | } |
65 | 0 | bool replaceStoreEdge(NodeIndex oldIdx, NodeIndex newIdx) { |
66 | 0 | return removeStoreEdge(oldIdx) && insertStoreEdge(newIdx); |
67 | 0 | } |
68 | | |
69 | 39.2k | iterator begin() { return copyEdges.begin(); } |
70 | 39.2k | iterator end() { return copyEdges.end(); } |
71 | 7.14k | const_iterator begin() const { return copyEdges.begin(); } |
72 | 7.14k | const_iterator end() const { return copyEdges.end(); } |
73 | | |
74 | 51.9k | const_iterator load_begin() const { return loadEdges.begin(); } |
75 | 51.9k | const_iterator load_end() const { return loadEdges.end(); } |
76 | 51.9k | llvm::iterator_range<const_iterator> loads() const { |
77 | 51.9k | return llvm::iterator_range<const_iterator>(load_begin(), load_end()); |
78 | 51.9k | } |
79 | | |
80 | 51.9k | const_iterator store_begin() const { return storeEdges.begin(); } |
81 | 51.9k | const_iterator store_end() const { return storeEdges.end(); } |
82 | 51.9k | llvm::iterator_range<const_iterator> stores() const { |
83 | 51.9k | return llvm::iterator_range<const_iterator>(store_begin(), store_end()); |
84 | 51.9k | } |
85 | | |
86 | | friend class ConstraintGraph; |
87 | | }; |
88 | | |
89 | | class ConstraintGraph { |
90 | | private: |
91 | | typedef std::map<NodeIndex, ConstraintGraphNode> NodeMapTy; |
92 | | NodeMapTy graph; |
93 | | |
94 | | public: |
95 | | typedef NodeMapTy::iterator iterator; |
96 | | typedef NodeMapTy::const_iterator const_iterator; |
97 | | |
98 | 1.76k | ConstraintGraph() {} |
99 | | |
100 | 109k | bool insertCopyEdge(NodeIndex src, NodeIndex dst) { |
101 | 109k | auto itr = graph.find(src); |
102 | 109k | if (itr == graph.end()) { |
103 | 22.2k | ConstraintGraphNode srcNode(src); |
104 | 22.2k | srcNode.insertCopyEdge(dst); |
105 | 22.2k | graph.insert(std::make_pair(src, std::move(srcNode))); |
106 | 22.2k | return true; |
107 | 22.2k | } else |
108 | 87.4k | return (itr->second).insertCopyEdge(dst); |
109 | 109k | } |
110 | | |
111 | 24.9k | bool insertLoadEdge(NodeIndex src, NodeIndex dst) { |
112 | 24.9k | auto itr = graph.find(src); |
113 | 24.9k | if (itr == graph.end()) { |
114 | 140 | ConstraintGraphNode srcNode(src); |
115 | 140 | srcNode.insertLoadEdge(dst); |
116 | 140 | graph.insert(std::make_pair(src, std::move(srcNode))); |
117 | 140 | return true; |
118 | 140 | } else |
119 | 24.7k | return (itr->second).insertLoadEdge(dst); |
120 | 24.9k | } |
121 | | |
122 | 12.6k | bool insertStoreEdge(NodeIndex src, NodeIndex dst) { |
123 | 12.6k | auto itr = graph.find(src); |
124 | 12.6k | if (itr == graph.end()) { |
125 | 12.5k | ConstraintGraphNode srcNode(src); |
126 | 12.5k | srcNode.insertStoreEdge(dst); |
127 | 12.5k | graph.insert(std::make_pair(src, std::move(srcNode))); |
128 | 12.5k | return true; |
129 | 12.5k | } else |
130 | 88 | return (itr->second).insertStoreEdge(dst); |
131 | 12.6k | } |
132 | | |
133 | 0 | void mergeNodes(NodeIndex dst, NodeIndex src) { |
134 | 0 | auto itr = graph.find(src); |
135 | 0 | if (itr == graph.end()) |
136 | 0 | return; |
137 | | |
138 | 0 | ConstraintGraphNode const &srcNode = itr->second; |
139 | 0 | itr = graph.find(dst); |
140 | 0 | if (itr == graph.end()) { |
141 | 0 | ConstraintGraphNode dstNode(dst); |
142 | 0 | graph.insert(std::make_pair(dst, srcNode)); |
143 | 0 | } else |
144 | 0 | (itr->second).mergeEdges(srcNode); |
145 | 0 | } |
146 | | |
147 | 0 | void deleteNode(NodeIndex idx) { graph.erase(idx); } |
148 | | |
149 | 154k | ConstraintGraphNode *getNodeWithIndex(NodeIndex idx) { |
150 | 154k | auto itr = graph.find(idx); |
151 | 154k | if (itr == graph.end()) |
152 | 94.2k | return nullptr; |
153 | 60.5k | else |
154 | 60.5k | return &(itr->second); |
155 | 154k | } |
156 | | |
157 | 7.14k | ConstraintGraphNode *getOrInsertNode(NodeIndex idx) { |
158 | 7.14k | auto itr = graph.find(idx); |
159 | 7.14k | if (itr == graph.end()) { |
160 | 6.92k | ConstraintGraphNode newNode(idx); |
161 | 6.92k | itr = graph.insert(std::make_pair(idx, newNode)).first; |
162 | 6.92k | } |
163 | 7.14k | return &(itr->second); |
164 | 7.14k | } |
165 | | |
166 | 0 | iterator begin() { return graph.begin(); } |
167 | 0 | iterator end() { return graph.end(); } |
168 | 0 | const_iterator begin() const { return graph.begin(); } |
169 | 0 | const_iterator end() const { return graph.end(); } |
170 | | }; |
171 | | |
172 | | } // namespace |
173 | | |
174 | | // Specialize the AnderGraphTraits for ConstraintGraph |
175 | | template <> class AndersGraphTraits<ConstraintGraph> { |
176 | | public: |
177 | | typedef ConstraintGraphNode NodeType; |
178 | | typedef MapValueIterator<ConstraintGraph::const_iterator> NodeIterator; |
179 | | typedef ConstraintGraphNode::iterator ChildIterator; |
180 | | |
181 | 7.14k | static inline ChildIterator child_begin(NodeType const *n) { |
182 | 7.14k | return n->begin(); |
183 | 7.14k | } |
184 | 7.14k | static inline ChildIterator child_end(NodeType const *n) { return n->end(); } |
185 | | |
186 | 0 | static inline NodeIterator node_begin(ConstraintGraph const *g) { |
187 | 0 | return NodeIterator(g->begin()); |
188 | 0 | } |
189 | 0 | static inline NodeIterator node_end(ConstraintGraph const *g) { |
190 | 0 | return NodeIterator(g->end()); |
191 | 0 | } |
192 | | }; |
193 | | |
194 | | namespace { |
195 | | |
196 | | void collapseNodes(NodeIndex dst, NodeIndex src, AndersNodeFactory &nodeFactory, |
197 | | std::map<NodeIndex, AndersPtsSet> &ptsGraph, |
198 | 0 | ConstraintGraph &constraintGraph) { |
199 | 0 | if (dst == src) |
200 | 0 | return; |
201 | | |
202 | | // Node merge |
203 | 0 | nodeFactory.mergeNode(dst, src); |
204 | 0 | if (ptsGraph.count(src)) |
205 | 0 | ptsGraph[dst].unionWith(ptsGraph[src]); |
206 | 0 | constraintGraph.mergeNodes(dst, src); |
207 | | |
208 | | // We don't need the node cycleIdx any more |
209 | 0 | ptsGraph.erase(src); |
210 | 0 | constraintGraph.deleteNode(src); |
211 | 0 | } |
212 | | |
213 | | // The worklist for our analysis |
214 | | class AndersWorkList { |
215 | | private: |
216 | | // The FIFO queue |
217 | | std::queue<NodeIndex> list; |
218 | | // Avoid duplicate entries in FIFO queue |
219 | | llvm::SmallSet<NodeIndex, 16> set; |
220 | | |
221 | | public: |
222 | 3.52k | AndersWorkList() {} |
223 | 133k | void enqueue(NodeIndex elem) { |
224 | 133k | if (!set.count(elem)) { |
225 | 108k | list.push(elem); |
226 | 108k | set.insert(elem); |
227 | 108k | } |
228 | 133k | } |
229 | 108k | NodeIndex dequeue() { |
230 | 108k | assert(!list.empty() && "Trying to dequeue an empty queue!"); |
231 | 108k | NodeIndex ret = list.front(); |
232 | 108k | list.pop(); |
233 | 108k | set.erase(ret); |
234 | 108k | return ret; |
235 | 108k | } |
236 | 125k | bool isEmpty() const { return list.empty(); } |
237 | | }; |
238 | | |
239 | | // The technique used here is described in "The Ant and the Grasshopper: Fast |
240 | | // and Accurate Pointer Analysis for Millions of Lines of Code. In Programming |
241 | | // Language Design and Implementation (PLDI), June 2007." It is known as the |
242 | | // "HCD" (Hybrid Cycle Detection) algorithm. It is called a hybrid because it |
243 | | // performs an offline analysis and uses its results during the solving (online) |
244 | | // phase. This is just the offline portion |
245 | | class OfflineCycleDetector : public CycleDetector<SparseBitVectorGraph> { |
246 | | private: |
247 | | // The node factory |
248 | | AndersNodeFactory &nodeFactory; |
249 | | |
250 | | // The offline constraint graph |
251 | | SparseBitVectorGraph offlineGraph; |
252 | | // If a mapping <p, q> is in this map, it means that *p and q are in the same |
253 | | // cycle in the offline constraint graph, and anything that p points to during |
254 | | // the online constraint solving phase can be immediately collapse with q |
255 | | DenseMap<NodeIndex, NodeIndex> collapseMap; |
256 | | // Holds the pairs of VAR nodes that we are going to merge together |
257 | | DenseMap<NodeIndex, NodeIndex> mergeMap; |
258 | | // Used to collect the scc nodes on a cycle |
259 | | SparseBitVector<> scc; |
260 | | |
261 | | // Return the node index of the "ref node" (used to represent *n) of n. |
262 | | // We won't actually create that ref node. We cannot use the NodeIndex of that |
263 | | // refNode to index into nodeFactory |
264 | 37.5k | NodeIndex getRefNodeIndex(NodeIndex n) const { |
265 | 37.5k | return n + nodeFactory.getNumNodes(); |
266 | 37.5k | } |
267 | | |
268 | | void buildOfflineConstraintGraph( |
269 | 1.76k | std::vector<AndersConstraint> const &constraints) { |
270 | 140k | for (auto const &c : constraints) { |
271 | 140k | NodeIndex srcTgt = nodeFactory.getMergeTarget(c.getSrc()); |
272 | 140k | NodeIndex dstTgt = nodeFactory.getMergeTarget(c.getDest()); |
273 | 140k | switch (c.getType()) { |
274 | 45.9k | case AndersConstraint::ADDR_OF: |
275 | 45.9k | break; |
276 | 24.9k | case AndersConstraint::LOAD: { |
277 | 24.9k | offlineGraph.insertEdge(getRefNodeIndex(srcTgt), dstTgt); |
278 | 24.9k | break; |
279 | 0 | } |
280 | 12.6k | case AndersConstraint::STORE: { |
281 | 12.6k | offlineGraph.insertEdge(srcTgt, getRefNodeIndex(dstTgt)); |
282 | 12.6k | break; |
283 | 0 | } |
284 | 56.8k | case AndersConstraint::COPY: { |
285 | 56.8k | offlineGraph.insertEdge(srcTgt, dstTgt); |
286 | 56.8k | break; |
287 | 0 | } |
288 | 140k | } |
289 | 140k | } |
290 | 1.76k | } |
291 | | |
292 | 39.6k | NodeType *getRep(NodeIndex idx) override { |
293 | 39.6k | return offlineGraph.getOrInsertNode(idx); |
294 | 39.6k | } |
295 | | |
296 | | // Specify how to process the non-rep nodes if a cycle is found |
297 | | void processNodeOnCycle(NodeType const *node, |
298 | 0 | NodeType const *repNode) override { |
299 | 0 | scc.set(node->getNodeIndex()); |
300 | 0 | } |
301 | | |
302 | | // Specify how to process the rep nodes if a cycle is found |
303 | 25.8k | void processCycleRepNode(NodeType const *node) override { |
304 | | // A trivial cycle is not interesting |
305 | 25.8k | if (scc.count() == 0) |
306 | 25.8k | return; |
307 | | |
308 | 0 | scc.set(node->getNodeIndex()); |
309 | | |
310 | | // The representative is the first non-ref node |
311 | 0 | NodeIndex repNode = scc.find_first(); |
312 | 0 | assert(repNode < nodeFactory.getNumNodes() && |
313 | 0 | "The SCC didn't have a non-Ref node!"); |
314 | 0 | for (auto itr = ++scc.begin(), ite = scc.end(); itr != ite; ++itr) { |
315 | 0 | NodeIndex cycleNode = *itr; |
316 | 0 | if (cycleNode > nodeFactory.getNumNodes()) |
317 | | // For REF nodes, insert it to the collapse map |
318 | 0 | collapseMap[cycleNode - nodeFactory.getNumNodes()] = repNode; |
319 | 0 | else |
320 | | // For VAR nodes, insert it to the merge map |
321 | | // We don't merge the nodes immediately to avoid affecting the DFS |
322 | 0 | mergeMap[cycleNode] = repNode; |
323 | 0 | } |
324 | |
|
325 | 0 | scc.clear(); |
326 | 0 | } |
327 | | |
328 | | public: |
329 | | OfflineCycleDetector(std::vector<AndersConstraint> const &cs, |
330 | | AndersNodeFactory &n) |
331 | 1.76k | : nodeFactory(n) { |
332 | | // Build the offline constraint graph first before we move on |
333 | 1.76k | buildOfflineConstraintGraph(cs); |
334 | 1.76k | } |
335 | | |
336 | 1.76k | void run() override { |
337 | 1.76k | runOnGraph(&offlineGraph); |
338 | | |
339 | | // Merge the nodes in mergeMap |
340 | 1.76k | for (auto const &mapping : mergeMap) |
341 | 0 | nodeFactory.mergeNode(mapping.second, mapping.first); |
342 | | |
343 | | // We don't need these structures any more. The only thing we keep should be |
344 | | // those info that are necessary to answer collapsing target queries |
345 | 1.76k | mergeMap.clear(); |
346 | 1.76k | offlineGraph.releaseMemory(); |
347 | 1.76k | releaseSCCMemory(); |
348 | 1.76k | } |
349 | | |
350 | | // Return InvalidIndex if no collapse target found |
351 | 39.2k | NodeIndex getCollapseTarget(NodeIndex n) { |
352 | 39.2k | auto itr = collapseMap.find(n); |
353 | 39.2k | if (itr == collapseMap.end()) |
354 | 39.2k | return AndersNodeFactory::InvalidIndex; |
355 | 0 | else |
356 | 0 | return itr->second; |
357 | 39.2k | } |
358 | | }; |
359 | | |
360 | | void buildConstraintGraph(ConstraintGraph &cGraph, |
361 | | std::vector<AndersConstraint> const &constraints, |
362 | | AndersNodeFactory &nodeFactory, |
363 | 1.76k | std::map<NodeIndex, AndersPtsSet> &ptsGraph) { |
364 | 140k | for (auto const &c : constraints) { |
365 | 140k | NodeIndex srcTgt = nodeFactory.getMergeTarget(c.getSrc()); |
366 | 140k | NodeIndex dstTgt = nodeFactory.getMergeTarget(c.getDest()); |
367 | 140k | switch (c.getType()) { |
368 | 45.9k | case AndersConstraint::ADDR_OF: { |
369 | | // We don't want to replace src with srcTgt because, after all, the |
370 | | // address of a variable is NOT the same as the address of another |
371 | | // variable |
372 | 45.9k | ptsGraph[dstTgt].insert(c.getSrc()); |
373 | 45.9k | break; |
374 | 0 | } |
375 | 24.9k | case AndersConstraint::LOAD: { |
376 | 24.9k | cGraph.insertLoadEdge(srcTgt, dstTgt); |
377 | 24.9k | break; |
378 | 0 | } |
379 | 12.6k | case AndersConstraint::STORE: { |
380 | 12.6k | cGraph.insertStoreEdge(dstTgt, srcTgt); |
381 | 12.6k | break; |
382 | 0 | } |
383 | 56.8k | case AndersConstraint::COPY: { |
384 | 56.8k | cGraph.insertCopyEdge(srcTgt, dstTgt); |
385 | 56.8k | break; |
386 | 0 | } |
387 | 140k | } |
388 | 140k | } |
389 | 1.76k | } |
390 | | |
391 | | class OnlineCycleDetector : public CycleDetector<ConstraintGraph> { |
392 | | private: |
393 | | AndersNodeFactory &nodeFactory; |
394 | | ConstraintGraph &constraintGraph; |
395 | | std::map<NodeIndex, AndersPtsSet> &ptsGraph; |
396 | | DenseSet<NodeIndex> const &candidates; |
397 | | |
398 | 7.14k | NodeType *getRep(NodeIndex idx) override { |
399 | 7.14k | return constraintGraph.getOrInsertNode(nodeFactory.getMergeTarget(idx)); |
400 | 7.14k | } |
401 | | // Specify how to process the non-rep nodes if a cycle is found |
402 | | void processNodeOnCycle(NodeType const *node, |
403 | 0 | NodeType const *repNode) override { |
404 | 0 | NodeIndex repIdx = nodeFactory.getMergeTarget(repNode->getNodeIndex()); |
405 | 0 | NodeIndex cycleIdx = nodeFactory.getMergeTarget(node->getNodeIndex()); |
406 | | // errs() << "Collapse node " << cycleIdx << " with node " << repIdx << |
407 | | // "\n"; |
408 | |
|
409 | 0 | collapseNodes(repIdx, cycleIdx, nodeFactory, ptsGraph, constraintGraph); |
410 | 0 | } |
411 | | // Specify how to process the rep nodes if a cycle is found |
412 | 7.14k | void processCycleRepNode(NodeType const *node) override { |
413 | | // Do nothing, I guess? |
414 | 7.14k | } |
415 | | |
416 | | public: |
417 | | OnlineCycleDetector(AndersNodeFactory &n, ConstraintGraph &co, |
418 | | std::map<NodeIndex, AndersPtsSet> &p, |
419 | | DenseSet<NodeIndex> const &ca) |
420 | 1.71k | : nodeFactory(n), constraintGraph(co), ptsGraph(p), candidates(ca) {} |
421 | | |
422 | 1.71k | void run() override { |
423 | | // Perform cycle detection on for nodes on the candidate list |
424 | 1.71k | for (auto node : candidates) |
425 | 7.03k | runOnNode(node); |
426 | 1.71k | } |
427 | | }; |
428 | | |
429 | | } // end of anonymous namespace |
430 | | |
431 | | /// solveConstraints - This stage iteratively processes the constraints list |
432 | | /// propagating constraints (adding edges to the Nodes in the points-to graph) |
433 | | /// until a fixed point is reached. |
434 | | /// |
435 | | /// We use a variant of the technique called "Lazy Cycle Detection", which is |
436 | | /// described in "The Ant and the Grasshopper: Fast and Accurate Pointer |
437 | | /// Analysis for Millions of Lines of Code. In Programming Language Design and |
438 | | /// Implementation (PLDI), June 2007." |
439 | | /// The paper describes performing cycle detection one node at a time, which can |
440 | | /// be expensive if there are no cycles, but there are long chains of nodes that |
441 | | /// it heuristically believes are cycles (because it will DFS from each node |
442 | | /// without state from previous nodes). |
443 | | /// Instead, we use the heuristic to build a worklist of nodes to check, then |
444 | | /// cycle detect them all at the same time to do this more cheaply. This |
445 | | /// catches cycles slightly later than the original technique did, but does it |
446 | | /// make significantly cheaper. |
447 | 1.76k | void Andersen::solveConstraints() { |
448 | | // We'll do offline HCD first |
449 | 1.76k | OfflineCycleDetector offlineInfo(constraints, nodeFactory); |
450 | 1.76k | if (EnableHCD) |
451 | 1.76k | offlineInfo.run(); |
452 | | |
453 | | // Now build the constraint graph |
454 | 1.76k | ConstraintGraph constraintGraph; |
455 | 1.76k | buildConstraintGraph(constraintGraph, constraints, nodeFactory, ptsGraph); |
456 | | // The constraint vector is useless now |
457 | 1.76k | constraints.clear(); |
458 | | |
459 | | // We switch between two work lists instead of relying on only one work list |
460 | 1.76k | AndersWorkList workList1, workList2; |
461 | | // The "current" and the "next" work list |
462 | 1.76k | AndersWorkList *currWorkList = &workList1, *nextWorkList = &workList2; |
463 | | // The set of nodes that LCD believes might be on a cycle |
464 | 1.76k | DenseSet<NodeIndex> cycleCandidates; |
465 | | // The set of edges that LCD believes not on a cycle |
466 | 1.76k | DenseSet<std::pair<NodeIndex, NodeIndex>> checkedEdges; |
467 | | |
468 | | // Scan the node list, add it to work list if the node a representative and |
469 | | // can contribute to the calculation right now. |
470 | 45.9k | for (auto const &mapping : ptsGraph) { |
471 | 45.9k | NodeIndex node = mapping.first; |
472 | 45.9k | if (nodeFactory.getMergeTarget(node) == node && |
473 | 45.9k | constraintGraph.getNodeWithIndex(node) != nullptr) |
474 | 13.4k | currWorkList->enqueue(node); |
475 | 45.9k | } |
476 | | |
477 | 9.04k | while (!currWorkList->isEmpty()) { |
478 | | // Iteration begins |
479 | | |
480 | | // First we've got to check if there is any cycle candidates in the last |
481 | | // iteration. If there is, detect and collapse cycle |
482 | 7.28k | if (EnableLCD && !cycleCandidates.empty()) { |
483 | | // Detect and collapse cycles online |
484 | 1.71k | OnlineCycleDetector cycleDetector(nodeFactory, constraintGraph, ptsGraph, |
485 | 1.71k | cycleCandidates); |
486 | 1.71k | cycleDetector.run(); |
487 | 1.71k | cycleCandidates.clear(); |
488 | 1.71k | } |
489 | | |
490 | 116k | while (!currWorkList->isEmpty()) { |
491 | 108k | NodeIndex node = currWorkList->dequeue(); |
492 | 108k | node = nodeFactory.getMergeTarget(node); |
493 | | // errs() << "Examining node " << node << "\n"; |
494 | | |
495 | 108k | ConstraintGraphNode *cNode = constraintGraph.getNodeWithIndex(node); |
496 | 108k | if (cNode == nullptr) |
497 | 61.8k | continue; |
498 | | |
499 | 47.1k | auto ptsItr = ptsGraph.find(node); |
500 | 47.1k | if (ptsItr != ptsGraph.end()) { |
501 | | // Check indirect constraints and add copy edge to the constraint graph |
502 | | // if necessary |
503 | 39.2k | AndersPtsSet const &ptsSet = ptsItr->second; |
504 | | |
505 | | // This is where we perform HCD: check if node has a collapse target, |
506 | | // and if it does, merge them immediately |
507 | 39.2k | if (EnableHCD) { |
508 | 39.2k | NodeIndex collapseTarget = offlineInfo.getCollapseTarget(node); |
509 | 39.2k | if (collapseTarget != AndersNodeFactory::InvalidIndex) { |
510 | | // errs() << "node = " << node << ", collapseTgt = " << |
511 | | // collapseTarget << "\n"; |
512 | 0 | NodeIndex ctRep = nodeFactory.getMergeTarget(collapseTarget); |
513 | | // Here we have to pay special attention to whether the node |
514 | | // points-to itself. |
515 | 0 | bool mergeSelf = false; |
516 | 0 | for (auto v : ptsSet) { |
517 | 0 | NodeIndex vRep = nodeFactory.getMergeTarget(v); |
518 | 0 | if (vRep == node) { |
519 | 0 | mergeSelf = true; |
520 | 0 | continue; |
521 | 0 | } |
522 | 0 | collapseNodes(ctRep, vRep, nodeFactory, ptsGraph, |
523 | 0 | constraintGraph); |
524 | 0 | } |
525 | |
|
526 | 0 | if (mergeSelf) { |
527 | 0 | collapseNodes(ctRep, node, nodeFactory, ptsGraph, |
528 | 0 | constraintGraph); |
529 | | // If the node collapsing succeeds, we can't proceed here because |
530 | | // node no longer exists. Push ctRep to the worklist and proceed |
531 | 0 | if (ctRep != node) { |
532 | 0 | nextWorkList->enqueue(ctRep); |
533 | 0 | continue; |
534 | 0 | } |
535 | 0 | } |
536 | 0 | } |
537 | 39.2k | } |
538 | | |
539 | 51.9k | for (auto v : ptsSet) { |
540 | 51.9k | DenseMap<NodeIndex, NodeIndex> updateMap; |
541 | | |
542 | 51.9k | NodeIndex vRep = nodeFactory.getMergeTarget(v); |
543 | 51.9k | for (auto const &dst : cNode->loads()) { |
544 | 30.2k | NodeIndex tgtNode = nodeFactory.getMergeTarget(dst); |
545 | | // errs() << "Examining load edge " << node << " -> " << tgtNode << |
546 | | // "\n"; |
547 | 30.2k | if (constraintGraph.insertCopyEdge(vRep, tgtNode)) { |
548 | | // errs() << "\tInsert copy edge " << v << " -> " << tgtNode << |
549 | | // "\n"; |
550 | 26.6k | nextWorkList->enqueue(vRep); |
551 | 26.6k | } |
552 | | |
553 | | // If we find that dst has been merged to elsewhere, remember this |
554 | | // fact to update the constraint graph later |
555 | 30.2k | if (tgtNode != dst) |
556 | 0 | updateMap[dst] = tgtNode; |
557 | 30.2k | } |
558 | | |
559 | | // Now perform the load edge updates |
560 | 51.9k | for (auto const &mapping : updateMap) |
561 | 0 | cNode->replaceLoadEdge(mapping.first, mapping.second); |
562 | 51.9k | updateMap.clear(); |
563 | | |
564 | 51.9k | for (auto const &dst : cNode->stores()) { |
565 | 22.6k | NodeIndex tgtNode = nodeFactory.getMergeTarget(dst); |
566 | 22.6k | if (constraintGraph.insertCopyEdge(tgtNode, vRep)) { |
567 | | // errs() << "\tInsert copy edge " << tgtNode << " -> " << v << |
568 | | // "\n"; |
569 | 13.9k | nextWorkList->enqueue(tgtNode); |
570 | 13.9k | } |
571 | | |
572 | | // If we find that dst has been merged to elsewhere, remember this |
573 | | // fact to update the constraint graph later |
574 | 22.6k | if (tgtNode != dst) |
575 | 0 | updateMap[dst] = tgtNode; |
576 | 22.6k | } |
577 | | |
578 | | // Now perform the store edge updates |
579 | 51.9k | for (auto const &mapping : updateMap) |
580 | 0 | cNode->replaceStoreEdge(mapping.first, mapping.second); |
581 | 51.9k | } |
582 | | |
583 | 39.2k | DenseMap<NodeIndex, NodeIndex> updateMap; |
584 | | // Finally, it's time to propagate pts-to info along the copy edges |
585 | 88.2k | for (auto const &dst : *cNode) { |
586 | 88.2k | NodeIndex tgtNode = nodeFactory.getMergeTarget(dst); |
587 | 88.2k | if (node == tgtNode) |
588 | 113 | continue; |
589 | 88.1k | AndersPtsSet &tgtPtsSet = ptsGraph[tgtNode]; |
590 | | |
591 | | // errs() << "pts[" << tgtNode << "] |= pts[" << node << "]\n"; |
592 | 88.1k | bool isChanged = tgtPtsSet.unionWith(ptsSet); |
593 | | |
594 | 88.1k | if (isChanged) { |
595 | 79.3k | nextWorkList->enqueue(tgtNode); |
596 | 79.3k | } else if (EnableLCD) { |
597 | | // This is where we do lazy cycle detection. |
598 | | // If this is a cycle candidate (equal points-to sets and this |
599 | | // particular edge has not been cycle-checked previously), add to |
600 | | // the list to check for cycles on the next iteration |
601 | 8.71k | auto edgePair = std::make_pair(node, tgtNode); |
602 | 8.71k | if (!checkedEdges.count(edgePair) && ptsSet == tgtPtsSet) { |
603 | 8.31k | checkedEdges.insert(edgePair); |
604 | 8.31k | cycleCandidates.insert(tgtNode); |
605 | 8.31k | } |
606 | 8.71k | } |
607 | | |
608 | 88.1k | if (tgtNode != dst) |
609 | 0 | updateMap[dst] = tgtNode; |
610 | 88.1k | } |
611 | | |
612 | | // Now perform the copy edge updates |
613 | 39.2k | for (auto const &mapping : updateMap) |
614 | 0 | cNode->replaceCopyEdge(mapping.first, mapping.second); |
615 | 39.2k | } |
616 | 47.1k | } |
617 | | // Swap the current and the next worklist |
618 | 7.28k | std::swap(currWorkList, nextWorkList); |
619 | 7.28k | } |
620 | 1.76k | } |