← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Analysis/LazyCallGraph.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/Analysis/LazyCallGraph.cpp
 
1
//===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
 
 
10
#include "llvm/Analysis/LazyCallGraph.h"
 
11
#include "llvm/ADT/STLExtras.h"
 
12
#include "llvm/IR/CallSite.h"
 
13
#include "llvm/IR/InstVisitor.h"
 
14
#include "llvm/IR/Instructions.h"
 
15
#include "llvm/IR/PassManager.h"
 
16
#include "llvm/Support/Debug.h"
 
17
#include "llvm/Support/raw_ostream.h"
 
18
 
 
19
using namespace llvm;
 
20
 
 
21
#define DEBUG_TYPE "lcg"
 
22
 
 
23
static void findCallees(
 
24
    SmallVectorImpl<Constant *> &Worklist, SmallPtrSetImpl<Constant *> &Visited,
 
25
    SmallVectorImpl<PointerUnion<Function *, LazyCallGraph::Node *>> &Callees,
 
26
    DenseMap<Function *, size_t> &CalleeIndexMap) {
 
27
  while (!Worklist.empty()) {
 
28
    Constant *C = Worklist.pop_back_val();
 
29
 
 
30
    if (Function *F = dyn_cast<Function>(C)) {
 
31
      // Note that we consider *any* function with a definition to be a viable
 
32
      // edge. Even if the function's definition is subject to replacement by
 
33
      // some other module (say, a weak definition) there may still be
 
34
      // optimizations which essentially speculate based on the definition and
 
35
      // a way to check that the specific definition is in fact the one being
 
36
      // used. For example, this could be done by moving the weak definition to
 
37
      // a strong (internal) definition and making the weak definition be an
 
38
      // alias. Then a test of the address of the weak function against the new
 
39
      // strong definition's address would be an effective way to determine the
 
40
      // safety of optimizing a direct call edge.
 
41
      if (!F->isDeclaration() &&
 
42
          CalleeIndexMap.insert(std::make_pair(F, Callees.size())).second) {
 
43
        DEBUG(dbgs() << "    Added callable function: " << F->getName()
 
44
                     << "\n");
 
45
        Callees.push_back(F);
 
46
      }
 
47
      continue;
 
48
    }
 
49
 
 
50
    for (Value *Op : C->operand_values())
 
51
      if (Visited.insert(cast<Constant>(Op)).second)
 
52
        Worklist.push_back(cast<Constant>(Op));
 
53
  }
 
54
}
 
55
 
 
56
LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
 
57
    : G(&G), F(F), DFSNumber(0), LowLink(0) {
 
58
  DEBUG(dbgs() << "  Adding functions called by '" << F.getName()
 
59
               << "' to the graph.\n");
 
60
 
 
61
  SmallVector<Constant *, 16> Worklist;
 
62
  SmallPtrSet<Constant *, 16> Visited;
 
63
  // Find all the potential callees in this function. First walk the
 
64
  // instructions and add every operand which is a constant to the worklist.
 
65
  for (BasicBlock &BB : F)
 
66
    for (Instruction &I : BB)
 
67
      for (Value *Op : I.operand_values())
 
68
        if (Constant *C = dyn_cast<Constant>(Op))
 
69
          if (Visited.insert(C).second)
 
70
            Worklist.push_back(C);
 
71
 
 
72
  // We've collected all the constant (and thus potentially function or
 
73
  // function containing) operands to all of the instructions in the function.
 
74
  // Process them (recursively) collecting every function found.
 
75
  findCallees(Worklist, Visited, Callees, CalleeIndexMap);
 
76
}
 
77
 
 
78
void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) {
 
79
  if (Node *N = G->lookup(Callee))
 
80
    return insertEdgeInternal(*N);
 
81
 
 
82
  CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size()));
 
83
  Callees.push_back(&Callee);
 
84
}
 
85
 
 
86
void LazyCallGraph::Node::insertEdgeInternal(Node &CalleeN) {
 
87
  CalleeIndexMap.insert(std::make_pair(&CalleeN.getFunction(), Callees.size()));
 
88
  Callees.push_back(&CalleeN);
 
89
}
 
90
 
 
91
void LazyCallGraph::Node::removeEdgeInternal(Function &Callee) {
 
92
  auto IndexMapI = CalleeIndexMap.find(&Callee);
 
93
  assert(IndexMapI != CalleeIndexMap.end() &&
 
94
         "Callee not in the callee set for this caller?");
 
95
 
 
96
  Callees[IndexMapI->second] = nullptr;
 
97
  CalleeIndexMap.erase(IndexMapI);
 
98
}
 
99
 
 
100
LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
 
101
  DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
 
102
               << "\n");
 
103
  for (Function &F : M)
 
104
    if (!F.isDeclaration() && !F.hasLocalLinkage())
 
105
      if (EntryIndexMap.insert(std::make_pair(&F, EntryNodes.size())).second) {
 
106
        DEBUG(dbgs() << "  Adding '" << F.getName()
 
107
                     << "' to entry set of the graph.\n");
 
108
        EntryNodes.push_back(&F);
 
109
      }
 
110
 
 
111
  // Now add entry nodes for functions reachable via initializers to globals.
 
112
  SmallVector<Constant *, 16> Worklist;
 
113
  SmallPtrSet<Constant *, 16> Visited;
 
114
  for (GlobalVariable &GV : M.globals())
 
115
    if (GV.hasInitializer())
 
116
      if (Visited.insert(GV.getInitializer()).second)
 
117
        Worklist.push_back(GV.getInitializer());
 
118
 
 
119
  DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
 
120
                  "entry set.\n");
 
121
  findCallees(Worklist, Visited, EntryNodes, EntryIndexMap);
 
122
 
 
123
  for (auto &Entry : EntryNodes) {
 
124
    assert(!Entry.isNull() &&
 
125
           "We can't have removed edges before we finish the constructor!");
 
126
    if (Function *F = Entry.dyn_cast<Function *>())
 
127
      SCCEntryNodes.push_back(F);
 
128
    else
 
129
      SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction());
 
130
  }
 
131
}
 
132
 
 
133
LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
 
134
    : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
 
135
      EntryNodes(std::move(G.EntryNodes)),
 
136
      EntryIndexMap(std::move(G.EntryIndexMap)), SCCBPA(std::move(G.SCCBPA)),
 
137
      SCCMap(std::move(G.SCCMap)), LeafSCCs(std::move(G.LeafSCCs)),
 
138
      DFSStack(std::move(G.DFSStack)),
 
139
      SCCEntryNodes(std::move(G.SCCEntryNodes)),
 
140
      NextDFSNumber(G.NextDFSNumber) {
 
141
  updateGraphPtrs();
 
142
}
 
143
 
 
144
LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
 
145
  BPA = std::move(G.BPA);
 
146
  NodeMap = std::move(G.NodeMap);
 
147
  EntryNodes = std::move(G.EntryNodes);
 
148
  EntryIndexMap = std::move(G.EntryIndexMap);
 
149
  SCCBPA = std::move(G.SCCBPA);
 
150
  SCCMap = std::move(G.SCCMap);
 
151
  LeafSCCs = std::move(G.LeafSCCs);
 
152
  DFSStack = std::move(G.DFSStack);
 
153
  SCCEntryNodes = std::move(G.SCCEntryNodes);
 
154
  NextDFSNumber = G.NextDFSNumber;
 
155
  updateGraphPtrs();
 
156
  return *this;
 
157
}
 
158
 
 
159
void LazyCallGraph::SCC::insert(Node &N) {
 
160
  N.DFSNumber = N.LowLink = -1;
 
161
  Nodes.push_back(&N);
 
162
  G->SCCMap[&N] = this;
 
163
}
 
164
 
 
165
bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const {
 
166
  // Walk up the parents of this SCC and verify that we eventually find C.
 
167
  SmallVector<const SCC *, 4> AncestorWorklist;
 
168
  AncestorWorklist.push_back(this);
 
169
  do {
 
170
    const SCC *AncestorC = AncestorWorklist.pop_back_val();
 
171
    if (AncestorC->isChildOf(C))
 
172
      return true;
 
173
    for (const SCC *ParentC : AncestorC->ParentSCCs)
 
174
      AncestorWorklist.push_back(ParentC);
 
175
  } while (!AncestorWorklist.empty());
 
176
 
 
177
  return false;
 
178
}
 
179
 
 
180
void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
 
181
  // First insert it into the caller.
 
182
  CallerN.insertEdgeInternal(CalleeN);
 
183
 
 
184
  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
 
185
  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
 
186
 
 
187
  // Nothing changes about this SCC or any other.
 
188
}
 
189
 
 
190
void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) {
 
191
  // First insert it into the caller.
 
192
  CallerN.insertEdgeInternal(CalleeN);
 
193
 
 
194
  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
 
195
 
 
196
  SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
 
197
  assert(&CalleeC != this && "Callee must not be in this SCC.");
 
198
  assert(CalleeC.isDescendantOf(*this) &&
 
199
         "Callee must be a descendant of the Caller.");
 
200
 
 
201
  // The only change required is to add this SCC to the parent set of the callee.
 
202
  CalleeC.ParentSCCs.insert(this);
 
203
}
 
204
 
 
205
SmallVector<LazyCallGraph::SCC *, 1>
 
206
LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) {
 
207
  // First insert it into the caller.
 
208
  CallerN.insertEdgeInternal(CalleeN);
 
209
 
 
210
  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
 
211
 
 
212
  SCC &CallerC = *G->SCCMap.lookup(&CallerN);
 
213
  assert(&CallerC != this && "Caller must not be in this SCC.");
 
214
  assert(CallerC.isDescendantOf(*this) &&
 
215
         "Caller must be a descendant of the Callee.");
 
216
 
 
217
  // The algorithm we use for merging SCCs based on the cycle introduced here
 
218
  // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse
 
219
  // graph has the same cycle properties as the actual DAG of the SCCs, and
 
220
  // when forming SCCs lazily by a DFS, the bottom of the graph won't exist in
 
221
  // many cases which should prune the search space.
 
222
  //
 
223
  // FIXME: We can get this pruning behavior even after the incremental SCC
 
224
  // formation by leaving behind (conservative) DFS numberings in the nodes,
 
225
  // and pruning the search with them. These would need to be cleverly updated
 
226
  // during the removal of intra-SCC edges, but could be preserved
 
227
  // conservatively.
 
228
 
 
229
  // The set of SCCs that are connected to the caller, and thus will
 
230
  // participate in the merged connected component.
 
231
  SmallPtrSet<SCC *, 8> ConnectedSCCs;
 
232
  ConnectedSCCs.insert(this);
 
233
  ConnectedSCCs.insert(&CallerC);
 
234
 
 
235
  // We build up a DFS stack of the parents chains.
 
236
  SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs;
 
237
  SmallPtrSet<SCC *, 8> VisitedSCCs;
 
238
  int ConnectedDepth = -1;
 
239
  SCC *C = this;
 
240
  parent_iterator I = parent_begin(), E = parent_end();
 
241
  for (;;) {
 
242
    while (I != E) {
 
243
      SCC &ParentSCC = *I++;
 
244
 
 
245
      // If we have already processed this parent SCC, skip it, and remember
 
246
      // whether it was connected so we don't have to check the rest of the
 
247
      // stack. This also handles when we reach a child of the 'this' SCC (the
 
248
      // callee) which terminates the search.
 
249
      if (ConnectedSCCs.count(&ParentSCC)) {
 
250
        ConnectedDepth = std::max<int>(ConnectedDepth, DFSSCCs.size());
 
251
        continue;
 
252
      }
 
253
      if (VisitedSCCs.count(&ParentSCC))
 
254
        continue;
 
255
 
 
256
      // We fully explore the depth-first space, adding nodes to the connected
 
257
      // set only as we pop them off, so "recurse" by rotating to the parent.
 
258
      DFSSCCs.push_back(std::make_pair(C, I));
 
259
      C = &ParentSCC;
 
260
      I = ParentSCC.parent_begin();
 
261
      E = ParentSCC.parent_end();
 
262
    }
 
263
 
 
264
    // If we've found a connection anywhere below this point on the stack (and
 
265
    // thus up the parent graph from the caller), the current node needs to be
 
266
    // added to the connected set now that we've processed all of its parents.
 
267
    if ((int)DFSSCCs.size() == ConnectedDepth) {
 
268
      --ConnectedDepth; // We're finished with this connection.
 
269
      ConnectedSCCs.insert(C);
 
270
    } else {
 
271
      // Otherwise remember that its parents don't ever connect.
 
272
      assert(ConnectedDepth < (int)DFSSCCs.size() &&
 
273
             "Cannot have a connected depth greater than the DFS depth!");
 
274
      VisitedSCCs.insert(C);
 
275
    }
 
276
 
 
277
    if (DFSSCCs.empty())
 
278
      break; // We've walked all the parents of the caller transitively.
 
279
 
 
280
    // Pop off the prior node and position to unwind the depth first recursion.
 
281
    std::tie(C, I) = DFSSCCs.pop_back_val();
 
282
    E = C->parent_end();
 
283
  }
 
284
 
 
285
  // Now that we have identified all of the SCCs which need to be merged into
 
286
  // a connected set with the inserted edge, merge all of them into this SCC.
 
287
  // FIXME: This operation currently creates ordering stability problems
 
288
  // because we don't use stably ordered containers for the parent SCCs or the
 
289
  // connected SCCs.
 
290
  unsigned NewNodeBeginIdx = Nodes.size();
 
291
  for (SCC *C : ConnectedSCCs) {
 
292
    if (C == this)
 
293
      continue;
 
294
    for (SCC *ParentC : C->ParentSCCs)
 
295
      if (!ConnectedSCCs.count(ParentC))
 
296
        ParentSCCs.insert(ParentC);
 
297
    C->ParentSCCs.clear();
 
298
 
 
299
    for (Node *N : *C) {
 
300
      for (Node &ChildN : *N) {
 
301
        SCC &ChildC = *G->SCCMap.lookup(&ChildN);
 
302
        if (&ChildC != C)
 
303
          ChildC.ParentSCCs.erase(C);
 
304
      }
 
305
      G->SCCMap[N] = this;
 
306
      Nodes.push_back(N);
 
307
    }
 
308
    C->Nodes.clear();
 
309
  }
 
310
  for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I)
 
311
    for (Node &ChildN : **I) {
 
312
      SCC &ChildC = *G->SCCMap.lookup(&ChildN);
 
313
      if (&ChildC != this)
 
314
        ChildC.ParentSCCs.insert(this);
 
315
    }
 
316
 
 
317
  // We return the list of SCCs which were merged so that callers can
 
318
  // invalidate any data they have associated with those SCCs. Note that these
 
319
  // SCCs are no longer in an interesting state (they are totally empty) but
 
320
  // the pointers will remain stable for the life of the graph itself.
 
321
  return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end());
 
322
}
 
323
 
 
324
void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
 
325
  // First remove it from the node.
 
326
  CallerN.removeEdgeInternal(CalleeN.getFunction());
 
327
 
 
328
  assert(G->SCCMap.lookup(&CallerN) == this &&
 
329
         "The caller must be a member of this SCC.");
 
330
 
 
331
  SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
 
332
  assert(&CalleeC != this &&
 
333
         "This API only supports the rmoval of inter-SCC edges.");
 
334
 
 
335
  assert(std::find(G->LeafSCCs.begin(), G->LeafSCCs.end(), this) ==
 
336
             G->LeafSCCs.end() &&
 
337
         "Cannot have a leaf SCC caller with a different SCC callee.");
 
338
 
 
339
  bool HasOtherCallToCalleeC = false;
 
340
  bool HasOtherCallOutsideSCC = false;
 
341
  for (Node *N : *this) {
 
342
    for (Node &OtherCalleeN : *N) {
 
343
      SCC &OtherCalleeC = *G->SCCMap.lookup(&OtherCalleeN);
 
344
      if (&OtherCalleeC == &CalleeC) {
 
345
        HasOtherCallToCalleeC = true;
 
346
        break;
 
347
      }
 
348
      if (&OtherCalleeC != this)
 
349
        HasOtherCallOutsideSCC = true;
 
350
    }
 
351
    if (HasOtherCallToCalleeC)
 
352
      break;
 
353
  }
 
354
  // Because the SCCs form a DAG, deleting such an edge cannot change the set
 
355
  // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
 
356
  // the caller no longer a parent of the callee. Walk the other call edges
 
357
  // in the caller to tell.
 
358
  if (!HasOtherCallToCalleeC) {
 
359
    bool Removed = CalleeC.ParentSCCs.erase(this);
 
360
    (void)Removed;
 
361
    assert(Removed &&
 
362
           "Did not find the caller SCC in the callee SCC's parent list!");
 
363
 
 
364
    // It may orphan an SCC if it is the last edge reaching it, but that does
 
365
    // not violate any invariants of the graph.
 
366
    if (CalleeC.ParentSCCs.empty())
 
367
      DEBUG(dbgs() << "LCG: Update removing " << CallerN.getFunction().getName()
 
368
                   << " -> " << CalleeN.getFunction().getName()
 
369
                   << " edge orphaned the callee's SCC!\n");
 
370
  }
 
371
 
 
372
  // It may make the Caller SCC a leaf SCC.
 
373
  if (!HasOtherCallOutsideSCC)
 
374
    G->LeafSCCs.push_back(this);
 
375
}
 
376
 
 
377
void LazyCallGraph::SCC::internalDFS(
 
378
    SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
 
379
    SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
 
380
    SmallVectorImpl<SCC *> &ResultSCCs) {
 
381
  Node::iterator I = N->begin();
 
382
  N->LowLink = N->DFSNumber = 1;
 
383
  int NextDFSNumber = 2;
 
384
  for (;;) {
 
385
    assert(N->DFSNumber != 0 && "We should always assign a DFS number "
 
386
                                "before processing a node.");
 
387
 
 
388
    // We simulate recursion by popping out of the nested loop and continuing.
 
389
    Node::iterator E = N->end();
 
390
    while (I != E) {
 
391
      Node &ChildN = *I;
 
392
      if (SCC *ChildSCC = G->SCCMap.lookup(&ChildN)) {
 
393
        // Check if we have reached a node in the new (known connected) set of
 
394
        // this SCC. If so, the entire stack is necessarily in that set and we
 
395
        // can re-start.
 
396
        if (ChildSCC == this) {
 
397
          insert(*N);
 
398
          while (!PendingSCCStack.empty())
 
399
            insert(*PendingSCCStack.pop_back_val());
 
400
          while (!DFSStack.empty())
 
401
            insert(*DFSStack.pop_back_val().first);
 
402
          return;
 
403
        }
 
404
 
 
405
        // If this child isn't currently in this SCC, no need to process it.
 
406
        // However, we do need to remove this SCC from its SCC's parent set.
 
407
        ChildSCC->ParentSCCs.erase(this);
 
408
        ++I;
 
409
        continue;
 
410
      }
 
411
 
 
412
      if (ChildN.DFSNumber == 0) {
 
413
        // Mark that we should start at this child when next this node is the
 
414
        // top of the stack. We don't start at the next child to ensure this
 
415
        // child's lowlink is reflected.
 
416
        DFSStack.push_back(std::make_pair(N, I));
 
417
 
 
418
        // Continue, resetting to the child node.
 
419
        ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
 
420
        N = &ChildN;
 
421
        I = ChildN.begin();
 
422
        E = ChildN.end();
 
423
        continue;
 
424
      }
 
425
 
 
426
      // Track the lowest link of the children, if any are still in the stack.
 
427
      // Any child not on the stack will have a LowLink of -1.
 
428
      assert(ChildN.LowLink != 0 &&
 
429
             "Low-link must not be zero with a non-zero DFS number.");
 
430
      if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
 
431
        N->LowLink = ChildN.LowLink;
 
432
      ++I;
 
433
    }
 
434
 
 
435
    if (N->LowLink == N->DFSNumber) {
 
436
      ResultSCCs.push_back(G->formSCC(N, PendingSCCStack));
 
437
      if (DFSStack.empty())
 
438
        return;
 
439
    } else {
 
440
      // At this point we know that N cannot ever be an SCC root. Its low-link
 
441
      // is not its dfs-number, and we've processed all of its children. It is
 
442
      // just sitting here waiting until some node further down the stack gets
 
443
      // low-link == dfs-number and pops it off as well. Move it to the pending
 
444
      // stack which is pulled into the next SCC to be formed.
 
445
      PendingSCCStack.push_back(N);
 
446
 
 
447
      assert(!DFSStack.empty() && "We shouldn't have an empty stack!");
 
448
    }
 
449
 
 
450
    N = DFSStack.back().first;
 
451
    I = DFSStack.back().second;
 
452
    DFSStack.pop_back();
 
453
  }
 
454
}
 
455
 
 
456
SmallVector<LazyCallGraph::SCC *, 1>
 
457
LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
 
458
                                       Node &CalleeN) {
 
459
  // First remove it from the node.
 
460
  CallerN.removeEdgeInternal(CalleeN.getFunction());
 
461
 
 
462
  // We return a list of the resulting *new* SCCs in postorder.
 
463
  SmallVector<SCC *, 1> ResultSCCs;
 
464
 
 
465
  // Direct recursion doesn't impact the SCC graph at all.
 
466
  if (&CallerN == &CalleeN)
 
467
    return ResultSCCs;
 
468
 
 
469
  // The worklist is every node in the original SCC.
 
470
  SmallVector<Node *, 1> Worklist;
 
471
  Worklist.swap(Nodes);
 
472
  for (Node *N : Worklist) {
 
473
    // The nodes formerly in this SCC are no longer in any SCC.
 
474
    N->DFSNumber = 0;
 
475
    N->LowLink = 0;
 
476
    G->SCCMap.erase(N);
 
477
  }
 
478
  assert(Worklist.size() > 1 && "We have to have at least two nodes to have an "
 
479
                                "edge between them that is within the SCC.");
 
480
 
 
481
  // The callee can already reach every node in this SCC (by definition). It is
 
482
  // the only node we know will stay inside this SCC. Everything which
 
483
  // transitively reaches Callee will also remain in the SCC. To model this we
 
484
  // incrementally add any chain of nodes which reaches something in the new
 
485
  // node set to the new node set. This short circuits one side of the Tarjan's
 
486
  // walk.
 
487
  insert(CalleeN);
 
488
 
 
489
  // We're going to do a full mini-Tarjan's walk using a local stack here.
 
490
  SmallVector<std::pair<Node *, Node::iterator>, 4> DFSStack;
 
491
  SmallVector<Node *, 4> PendingSCCStack;
 
492
  do {
 
493
    Node *N = Worklist.pop_back_val();
 
494
    if (N->DFSNumber == 0)
 
495
      internalDFS(DFSStack, PendingSCCStack, N, ResultSCCs);
 
496
 
 
497
    assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
 
498
    assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!");
 
499
  } while (!Worklist.empty());
 
500
 
 
501
  // Now we need to reconnect the current SCC to the graph.
 
502
  bool IsLeafSCC = true;
 
503
  for (Node *N : Nodes) {
 
504
    for (Node &ChildN : *N) {
 
505
      SCC &ChildSCC = *G->SCCMap.lookup(&ChildN);
 
506
      if (&ChildSCC == this)
 
507
        continue;
 
508
      ChildSCC.ParentSCCs.insert(this);
 
509
      IsLeafSCC = false;
 
510
    }
 
511
  }
 
512
#ifndef NDEBUG
 
513
  if (!ResultSCCs.empty())
 
514
    assert(!IsLeafSCC && "This SCC cannot be a leaf as we have split out new "
 
515
                         "SCCs by removing this edge.");
 
516
  if (!std::any_of(G->LeafSCCs.begin(), G->LeafSCCs.end(),
 
517
                   [&](SCC *C) { return C == this; }))
 
518
    assert(!IsLeafSCC && "This SCC cannot be a leaf as it already had child "
 
519
                         "SCCs before we removed this edge.");
 
520
#endif
 
521
  // If this SCC stopped being a leaf through this edge removal, remove it from
 
522
  // the leaf SCC list.
 
523
  if (!IsLeafSCC && !ResultSCCs.empty())
 
524
    G->LeafSCCs.erase(std::remove(G->LeafSCCs.begin(), G->LeafSCCs.end(), this),
 
525
                     G->LeafSCCs.end());
 
526
 
 
527
  // Return the new list of SCCs.
 
528
  return ResultSCCs;
 
529
}
 
530
 
 
531
void LazyCallGraph::insertEdge(Node &CallerN, Function &Callee) {
 
532
  assert(SCCMap.empty() && DFSStack.empty() &&
 
533
         "This method cannot be called after SCCs have been formed!");
 
534
 
 
535
  return CallerN.insertEdgeInternal(Callee);
 
536
}
 
537
 
 
538
void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) {
 
539
  assert(SCCMap.empty() && DFSStack.empty() &&
 
540
         "This method cannot be called after SCCs have been formed!");
 
541
 
 
542
  return CallerN.removeEdgeInternal(Callee);
 
543
}
 
544
 
 
545
LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
 
546
  return *new (MappedN = BPA.Allocate()) Node(*this, F);
 
547
}
 
548
 
 
549
void LazyCallGraph::updateGraphPtrs() {
 
550
  // Process all nodes updating the graph pointers.
 
551
  {
 
552
    SmallVector<Node *, 16> Worklist;
 
553
    for (auto &Entry : EntryNodes)
 
554
      if (Node *EntryN = Entry.dyn_cast<Node *>())
 
555
        Worklist.push_back(EntryN);
 
556
 
 
557
    while (!Worklist.empty()) {
 
558
      Node *N = Worklist.pop_back_val();
 
559
      N->G = this;
 
560
      for (auto &Callee : N->Callees)
 
561
        if (!Callee.isNull())
 
562
          if (Node *CalleeN = Callee.dyn_cast<Node *>())
 
563
            Worklist.push_back(CalleeN);
 
564
    }
 
565
  }
 
566
 
 
567
  // Process all SCCs updating the graph pointers.
 
568
  {
 
569
    SmallVector<SCC *, 16> Worklist(LeafSCCs.begin(), LeafSCCs.end());
 
570
 
 
571
    while (!Worklist.empty()) {
 
572
      SCC *C = Worklist.pop_back_val();
 
573
      C->G = this;
 
574
      Worklist.insert(Worklist.end(), C->ParentSCCs.begin(),
 
575
                      C->ParentSCCs.end());
 
576
    }
 
577
  }
 
578
}
 
579
 
 
580
LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN,
 
581
                                           SmallVectorImpl<Node *> &NodeStack) {
 
582
  // The tail of the stack is the new SCC. Allocate the SCC and pop the stack
 
583
  // into it.
 
584
  SCC *NewSCC = new (SCCBPA.Allocate()) SCC(*this);
 
585
 
 
586
  while (!NodeStack.empty() && NodeStack.back()->DFSNumber > RootN->DFSNumber) {
 
587
    assert(NodeStack.back()->LowLink >= RootN->LowLink &&
 
588
           "We cannot have a low link in an SCC lower than its root on the "
 
589
           "stack!");
 
590
    NewSCC->insert(*NodeStack.pop_back_val());
 
591
  }
 
592
  NewSCC->insert(*RootN);
 
593
 
 
594
  // A final pass over all edges in the SCC (this remains linear as we only
 
595
  // do this once when we build the SCC) to connect it to the parent sets of
 
596
  // its children.
 
597
  bool IsLeafSCC = true;
 
598
  for (Node *SCCN : NewSCC->Nodes)
 
599
    for (Node &SCCChildN : *SCCN) {
 
600
      SCC &ChildSCC = *SCCMap.lookup(&SCCChildN);
 
601
      if (&ChildSCC == NewSCC)
 
602
        continue;
 
603
      ChildSCC.ParentSCCs.insert(NewSCC);
 
604
      IsLeafSCC = false;
 
605
    }
 
606
 
 
607
  // For the SCCs where we fine no child SCCs, add them to the leaf list.
 
608
  if (IsLeafSCC)
 
609
    LeafSCCs.push_back(NewSCC);
 
610
 
 
611
  return NewSCC;
 
612
}
 
613
 
 
614
LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
 
615
  Node *N;
 
616
  Node::iterator I;
 
617
  if (!DFSStack.empty()) {
 
618
    N = DFSStack.back().first;
 
619
    I = DFSStack.back().second;
 
620
    DFSStack.pop_back();
 
621
  } else {
 
622
    // If we've handled all candidate entry nodes to the SCC forest, we're done.
 
623
    do {
 
624
      if (SCCEntryNodes.empty())
 
625
        return nullptr;
 
626
 
 
627
      N = &get(*SCCEntryNodes.pop_back_val());
 
628
    } while (N->DFSNumber != 0);
 
629
    I = N->begin();
 
630
    N->LowLink = N->DFSNumber = 1;
 
631
    NextDFSNumber = 2;
 
632
  }
 
633
 
 
634
  for (;;) {
 
635
    assert(N->DFSNumber != 0 && "We should always assign a DFS number "
 
636
                                "before placing a node onto the stack.");
 
637
 
 
638
    Node::iterator E = N->end();
 
639
    while (I != E) {
 
640
      Node &ChildN = *I;
 
641
      if (ChildN.DFSNumber == 0) {
 
642
        // Mark that we should start at this child when next this node is the
 
643
        // top of the stack. We don't start at the next child to ensure this
 
644
        // child's lowlink is reflected.
 
645
        DFSStack.push_back(std::make_pair(N, N->begin()));
 
646
 
 
647
        // Recurse onto this node via a tail call.
 
648
        assert(!SCCMap.count(&ChildN) &&
 
649
               "Found a node with 0 DFS number but already in an SCC!");
 
650
        ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
 
651
        N = &ChildN;
 
652
        I = ChildN.begin();
 
653
        E = ChildN.end();
 
654
        continue;
 
655
      }
 
656
 
 
657
      // Track the lowest link of the children, if any are still in the stack.
 
658
      assert(ChildN.LowLink != 0 &&
 
659
             "Low-link must not be zero with a non-zero DFS number.");
 
660
      if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
 
661
        N->LowLink = ChildN.LowLink;
 
662
      ++I;
 
663
    }
 
664
 
 
665
    if (N->LowLink == N->DFSNumber)
 
666
      // Form the new SCC out of the top of the DFS stack.
 
667
      return formSCC(N, PendingSCCStack);
 
668
 
 
669
    // At this point we know that N cannot ever be an SCC root. Its low-link
 
670
    // is not its dfs-number, and we've processed all of its children. It is
 
671
    // just sitting here waiting until some node further down the stack gets
 
672
    // low-link == dfs-number and pops it off as well. Move it to the pending
 
673
    // stack which is pulled into the next SCC to be formed.
 
674
    PendingSCCStack.push_back(N);
 
675
 
 
676
    assert(!DFSStack.empty() && "We never found a viable root!");
 
677
    N = DFSStack.back().first;
 
678
    I = DFSStack.back().second;
 
679
    DFSStack.pop_back();
 
680
  }
 
681
}
 
682
 
 
683
char LazyCallGraphAnalysis::PassID;
 
684
 
 
685
LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
 
686
 
 
687
static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
 
688
                       SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) {
 
689
  // Recurse depth first through the nodes.
 
690
  for (LazyCallGraph::Node &ChildN : N)
 
691
    if (Printed.insert(&ChildN).second)
 
692
      printNodes(OS, ChildN, Printed);
 
693
 
 
694
  OS << "  Call edges in function: " << N.getFunction().getName() << "\n";
 
695
  for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I)
 
696
    OS << "    -> " << I->getFunction().getName() << "\n";
 
697
 
 
698
  OS << "\n";
 
699
}
 
700
 
 
701
static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) {
 
702
  ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end());
 
703
  OS << "  SCC with " << SCCSize << " functions:\n";
 
704
 
 
705
  for (LazyCallGraph::Node *N : SCC)
 
706
    OS << "    " << N->getFunction().getName() << "\n";
 
707
 
 
708
  OS << "\n";
 
709
}
 
710
 
 
711
PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
 
712
                                                ModuleAnalysisManager *AM) {
 
713
  LazyCallGraph &G = AM->getResult<LazyCallGraphAnalysis>(M);
 
714
 
 
715
  OS << "Printing the call graph for module: " << M.getModuleIdentifier()
 
716
     << "\n\n";
 
717
 
 
718
  SmallPtrSet<LazyCallGraph::Node *, 16> Printed;
 
719
  for (LazyCallGraph::Node &N : G)
 
720
    if (Printed.insert(&N).second)
 
721
      printNodes(OS, N, Printed);
 
722
 
 
723
  for (LazyCallGraph::SCC &SCC : G.postorder_sccs())
 
724
    printSCC(OS, SCC);
 
725
 
 
726
  return PreservedAnalyses::all();
 
727
}