1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
//===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InstVisitor.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
static void findCallees(
SmallVectorImpl<Constant *> &Worklist, SmallPtrSetImpl<Constant *> &Visited,
SmallVectorImpl<PointerUnion<Function *, LazyCallGraph::Node *> > &Callees,
SmallPtrSetImpl<Function *> &CalleeSet) {
while (!Worklist.empty()) {
Constant *C = Worklist.pop_back_val();
if (Function *F = dyn_cast<Function>(C)) {
// Note that we consider *any* function with a definition to be a viable
// edge. Even if the function's definition is subject to replacement by
// some other module (say, a weak definition) there may still be
// optimizations which essentially speculate based on the definition and
// a way to check that the specific definition is in fact the one being
// used. For example, this could be done by moving the weak definition to
// a strong (internal) definition and making the weak definition be an
// alias. Then a test of the address of the weak function against the new
// strong definition's address would be an effective way to determine the
// safety of optimizing a direct call edge.
if (!F->isDeclaration() && CalleeSet.insert(F))
Callees.push_back(F);
continue;
}
for (Value *Op : C->operand_values())
if (Visited.insert(cast<Constant>(Op)))
Worklist.push_back(cast<Constant>(Op));
}
}
LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(G), F(F) {
SmallVector<Constant *, 16> Worklist;
SmallPtrSet<Constant *, 16> Visited;
// Find all the potential callees in this function. First walk the
// instructions and add every operand which is a constant to the worklist.
for (Function::iterator BBI = F.begin(), BBE = F.end(); BBI != BBE; ++BBI)
for (BasicBlock::iterator II = BBI->begin(), IE = BBI->end(); II != IE;
++II)
for (Value *Op : II->operand_values())
if (Constant *C = dyn_cast<Constant>(Op))
if (Visited.insert(C))
Worklist.push_back(C);
// We've collected all the constant (and thus potentially function or
// function containing) operands to all of the instructions in the function.
// Process them (recursively) collecting every function found.
findCallees(Worklist, Visited, Callees, CalleeSet);
}
LazyCallGraph::Node::Node(LazyCallGraph &G, const Node &OtherN)
: G(G), F(OtherN.F), CalleeSet(OtherN.CalleeSet) {
// Loop over the other node's callees, adding the Function*s to our list
// directly, and recursing to add the Node*s.
Callees.reserve(OtherN.Callees.size());
for (NodeVectorImplT::iterator OI = OtherN.Callees.begin(),
OE = OtherN.Callees.end();
OI != OE; ++OI)
if (Function *Callee = OI->dyn_cast<Function *>())
Callees.push_back(Callee);
else
Callees.push_back(G.copyInto(*OI->get<Node *>()));
}
LazyCallGraph::Node::Node(LazyCallGraph &G, Node &&OtherN)
: G(G), F(OtherN.F), Callees(std::move(OtherN.Callees)),
CalleeSet(std::move(OtherN.CalleeSet)) {
// Loop over our Callees. They've been moved from another node, but we need
// to move the Node*s to live under our bump ptr allocator.
for (NodeVectorImplT::iterator CI = Callees.begin(), CE = Callees.end();
CI != CE; ++CI)
if (Node *ChildN = CI->dyn_cast<Node *>())
*CI = G.moveInto(std::move(*ChildN));
}
LazyCallGraph::LazyCallGraph(Module &M) : M(M) {
for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
if (!FI->isDeclaration() && !FI->hasLocalLinkage())
if (EntryNodeSet.insert(&*FI))
EntryNodes.push_back(&*FI);
// Now add entry nodes for functions reachable via initializers to globals.
SmallVector<Constant *, 16> Worklist;
SmallPtrSet<Constant *, 16> Visited;
for (Module::global_iterator GI = M.global_begin(), GE = M.global_end(); GI != GE; ++GI)
if (GI->hasInitializer())
if (Visited.insert(GI->getInitializer()))
Worklist.push_back(GI->getInitializer());
findCallees(Worklist, Visited, EntryNodes, EntryNodeSet);
}
LazyCallGraph::LazyCallGraph(const LazyCallGraph &G)
: M(G.M), EntryNodeSet(G.EntryNodeSet) {
EntryNodes.reserve(G.EntryNodes.size());
for (NodeVectorImplT::const_iterator EI = G.EntryNodes.begin(),
EE = G.EntryNodes.end();
EI != EE; ++EI)
if (Function *Callee = EI->dyn_cast<Function *>())
EntryNodes.push_back(Callee);
else
EntryNodes.push_back(copyInto(*EI->get<Node *>()));
}
// FIXME: This would be crazy simpler if BumpPtrAllocator were movable without
// invalidating any of the allocated memory. We should make that be the case at
// some point and delete this.
LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
: M(G.M), EntryNodes(std::move(G.EntryNodes)),
EntryNodeSet(std::move(G.EntryNodeSet)) {
// Loop over our EntryNodes. They've been moved from another graph, so we
// need to move the Node*s to live under our bump ptr allocator. We can just
// do this in-place.
for (NodeVectorImplT::iterator EI = EntryNodes.begin(),
EE = EntryNodes.end();
EI != EE; ++EI)
if (Node *EntryN = EI->dyn_cast<Node *>())
*EI = moveInto(std::move(*EntryN));
}
LazyCallGraph::Node *LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
return new (MappedN = BPA.Allocate()) Node(*this, F);
}
LazyCallGraph::Node *LazyCallGraph::copyInto(const Node &OtherN) {
Node *&N = NodeMap[&OtherN.F];
if (N)
return N;
return new (N = BPA.Allocate()) Node(*this, OtherN);
}
LazyCallGraph::Node *LazyCallGraph::moveInto(Node &&OtherN) {
Node *&N = NodeMap[&OtherN.F];
if (N)
return N;
return new (N = BPA.Allocate()) Node(*this, std::move(OtherN));
}
char LazyCallGraphAnalysis::PassID;
LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) {
// Recurse depth first through the nodes.
for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I)
if (Printed.insert(*I))
printNodes(OS, **I, Printed);
OS << " Call edges in function: " << N.getFunction().getName() << "\n";
for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I)
OS << " -> " << I->getFunction().getName() << "\n";
OS << "\n";
}
PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M, ModuleAnalysisManager *AM) {
LazyCallGraph &G = AM->getResult<LazyCallGraphAnalysis>(M);
OS << "Printing the call graph for module: " << M->getModuleIdentifier() << "\n\n";
SmallPtrSet<LazyCallGraph::Node *, 16> Printed;
for (LazyCallGraph::iterator I = G.begin(), E = G.end(); I != E; ++I)
if (Printed.insert(*I))
printNodes(OS, **I, Printed);
return PreservedAnalyses::all();
}
|
