Coverage Report

Created: 2023-10-30 17:15

/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
}