Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 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" |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 11 | #include "llvm/ADT/STLExtras.h" |
Chandler Carruth | 219b89b | 2014-03-04 11:01:28 +0000 | [diff] [blame] | 12 | #include "llvm/IR/CallSite.h" |
Chandler Carruth | 7da14f1 | 2014-03-06 03:23:41 +0000 | [diff] [blame] | 13 | #include "llvm/IR/InstVisitor.h" |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 14 | #include "llvm/IR/Instructions.h" |
| 15 | #include "llvm/IR/PassManager.h" |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 16 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 17 | |
| 18 | using namespace llvm; |
| 19 | |
| 20 | static void findCallees( |
| 21 | SmallVectorImpl<Constant *> &Worklist, SmallPtrSetImpl<Constant *> &Visited, |
Chandler Carruth | e9b5061 | 2014-03-10 02:14:14 +0000 | [diff] [blame] | 22 | SmallVectorImpl<PointerUnion<Function *, LazyCallGraph::Node *>> &Callees, |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 23 | SmallPtrSetImpl<Function *> &CalleeSet) { |
| 24 | while (!Worklist.empty()) { |
| 25 | Constant *C = Worklist.pop_back_val(); |
| 26 | |
| 27 | if (Function *F = dyn_cast<Function>(C)) { |
| 28 | // Note that we consider *any* function with a definition to be a viable |
| 29 | // edge. Even if the function's definition is subject to replacement by |
| 30 | // some other module (say, a weak definition) there may still be |
| 31 | // optimizations which essentially speculate based on the definition and |
| 32 | // a way to check that the specific definition is in fact the one being |
| 33 | // used. For example, this could be done by moving the weak definition to |
| 34 | // a strong (internal) definition and making the weak definition be an |
| 35 | // alias. Then a test of the address of the weak function against the new |
| 36 | // strong definition's address would be an effective way to determine the |
| 37 | // safety of optimizing a direct call edge. |
| 38 | if (!F->isDeclaration() && CalleeSet.insert(F)) |
Chandler Carruth | e9b5061 | 2014-03-10 02:14:14 +0000 | [diff] [blame] | 39 | Callees.push_back(F); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 40 | continue; |
| 41 | } |
| 42 | |
Chandler Carruth | 1583e99 | 2014-03-03 10:42:58 +0000 | [diff] [blame] | 43 | for (Value *Op : C->operand_values()) |
| 44 | if (Visited.insert(cast<Constant>(Op))) |
| 45 | Worklist.push_back(cast<Constant>(Op)); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 46 | } |
| 47 | } |
| 48 | |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 49 | LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) |
| 50 | : G(&G), F(F), DFSNumber(0), LowLink(0) { |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 51 | SmallVector<Constant *, 16> Worklist; |
| 52 | SmallPtrSet<Constant *, 16> Visited; |
| 53 | // Find all the potential callees in this function. First walk the |
| 54 | // instructions and add every operand which is a constant to the worklist. |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 55 | for (BasicBlock &BB : F) |
| 56 | for (Instruction &I : BB) |
| 57 | for (Value *Op : I.operand_values()) |
Chandler Carruth | 1583e99 | 2014-03-03 10:42:58 +0000 | [diff] [blame] | 58 | if (Constant *C = dyn_cast<Constant>(Op)) |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 59 | if (Visited.insert(C)) |
| 60 | Worklist.push_back(C); |
| 61 | |
| 62 | // We've collected all the constant (and thus potentially function or |
| 63 | // function containing) operands to all of the instructions in the function. |
| 64 | // Process them (recursively) collecting every function found. |
| 65 | findCallees(Worklist, Visited, Callees, CalleeSet); |
| 66 | } |
| 67 | |
Chandler Carruth | 2174f44 | 2014-04-18 20:44:16 +0000 | [diff] [blame^] | 68 | LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 69 | for (Function &F : M) |
| 70 | if (!F.isDeclaration() && !F.hasLocalLinkage()) |
| 71 | if (EntryNodeSet.insert(&F)) |
| 72 | EntryNodes.push_back(&F); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 73 | |
| 74 | // Now add entry nodes for functions reachable via initializers to globals. |
| 75 | SmallVector<Constant *, 16> Worklist; |
| 76 | SmallPtrSet<Constant *, 16> Visited; |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 77 | for (GlobalVariable &GV : M.globals()) |
| 78 | if (GV.hasInitializer()) |
| 79 | if (Visited.insert(GV.getInitializer())) |
| 80 | Worklist.push_back(GV.getInitializer()); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 81 | |
| 82 | findCallees(Worklist, Visited, EntryNodes, EntryNodeSet); |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 83 | |
| 84 | for (auto &Entry : EntryNodes) |
| 85 | if (Function *F = Entry.dyn_cast<Function *>()) |
| 86 | SCCEntryNodes.insert(F); |
| 87 | else |
| 88 | SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction()); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 89 | } |
| 90 | |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 91 | LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) |
Chandler Carruth | 2174f44 | 2014-04-18 20:44:16 +0000 | [diff] [blame^] | 92 | : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)), |
| 93 | EntryNodes(std::move(G.EntryNodes)), |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 94 | EntryNodeSet(std::move(G.EntryNodeSet)), SCCBPA(std::move(G.SCCBPA)), |
| 95 | SCCMap(std::move(G.SCCMap)), LeafSCCs(std::move(G.LeafSCCs)), |
| 96 | DFSStack(std::move(G.DFSStack)), |
Chandler Carruth | 2174f44 | 2014-04-18 20:44:16 +0000 | [diff] [blame^] | 97 | SCCEntryNodes(std::move(G.SCCEntryNodes)), |
| 98 | NextDFSNumber(G.NextDFSNumber) { |
Chandler Carruth | d8d865e | 2014-04-18 11:02:33 +0000 | [diff] [blame] | 99 | updateGraphPtrs(); |
| 100 | } |
| 101 | |
| 102 | LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) { |
| 103 | BPA = std::move(G.BPA); |
Chandler Carruth | 2174f44 | 2014-04-18 20:44:16 +0000 | [diff] [blame^] | 104 | NodeMap = std::move(G.NodeMap); |
Chandler Carruth | d8d865e | 2014-04-18 11:02:33 +0000 | [diff] [blame] | 105 | EntryNodes = std::move(G.EntryNodes); |
| 106 | EntryNodeSet = std::move(G.EntryNodeSet); |
| 107 | SCCBPA = std::move(G.SCCBPA); |
| 108 | SCCMap = std::move(G.SCCMap); |
| 109 | LeafSCCs = std::move(G.LeafSCCs); |
| 110 | DFSStack = std::move(G.DFSStack); |
| 111 | SCCEntryNodes = std::move(G.SCCEntryNodes); |
Chandler Carruth | 2174f44 | 2014-04-18 20:44:16 +0000 | [diff] [blame^] | 112 | NextDFSNumber = G.NextDFSNumber; |
Chandler Carruth | d8d865e | 2014-04-18 11:02:33 +0000 | [diff] [blame] | 113 | updateGraphPtrs(); |
| 114 | return *this; |
| 115 | } |
| 116 | |
| 117 | LazyCallGraph::Node *LazyCallGraph::insertInto(Function &F, Node *&MappedN) { |
| 118 | return new (MappedN = BPA.Allocate()) Node(*this, F); |
| 119 | } |
| 120 | |
| 121 | void LazyCallGraph::updateGraphPtrs() { |
Chandler Carruth | b60cb31 | 2014-04-17 07:25:59 +0000 | [diff] [blame] | 122 | // Process all nodes updating the graph pointers. |
| 123 | SmallVector<Node *, 16> Worklist; |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 124 | for (auto &Entry : EntryNodes) |
| 125 | if (Node *EntryN = Entry.dyn_cast<Node *>()) |
Chandler Carruth | b60cb31 | 2014-04-17 07:25:59 +0000 | [diff] [blame] | 126 | Worklist.push_back(EntryN); |
| 127 | |
| 128 | while (!Worklist.empty()) { |
| 129 | Node *N = Worklist.pop_back_val(); |
| 130 | N->G = this; |
| 131 | for (auto &Callee : N->Callees) |
| 132 | if (Node *CalleeN = Callee.dyn_cast<Node *>()) |
| 133 | Worklist.push_back(CalleeN); |
| 134 | } |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 135 | } |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 136 | |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 137 | LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { |
| 138 | // When the stack is empty, there are no more SCCs to walk in this graph. |
| 139 | if (DFSStack.empty()) { |
| 140 | // If we've handled all candidate entry nodes to the SCC forest, we're done. |
| 141 | if (SCCEntryNodes.empty()) |
| 142 | return nullptr; |
| 143 | |
| 144 | Node *N = get(*SCCEntryNodes.pop_back_val()); |
| 145 | DFSStack.push_back(std::make_pair(N, N->begin())); |
| 146 | } |
| 147 | |
| 148 | Node *N = DFSStack.back().first; |
| 149 | if (N->DFSNumber == 0) { |
| 150 | // This node hasn't been visited before, assign it a DFS number and remove |
| 151 | // it from the entry set. |
| 152 | N->LowLink = N->DFSNumber = NextDFSNumber++; |
| 153 | SCCEntryNodes.remove(&N->getFunction()); |
| 154 | } |
| 155 | |
| 156 | for (auto I = DFSStack.back().second, E = N->end(); I != E; ++I) { |
| 157 | Node *ChildN = *I; |
| 158 | if (ChildN->DFSNumber == 0) { |
| 159 | // Mark that we should start at this child when next this node is the |
| 160 | // top of the stack. We don't start at the next child to ensure this |
| 161 | // child's lowlink is reflected. |
| 162 | // FIXME: I don't actually think this is required, and we could start |
| 163 | // at the next child. |
| 164 | DFSStack.back().second = I; |
| 165 | |
| 166 | // Recurse onto this node via a tail call. |
| 167 | DFSStack.push_back(std::make_pair(ChildN, ChildN->begin())); |
| 168 | return LazyCallGraph::getNextSCCInPostOrder(); |
| 169 | } |
| 170 | |
| 171 | // Track the lowest link of the childen, if any are still in the stack. |
| 172 | if (ChildN->LowLink < N->LowLink && !SCCMap.count(&ChildN->getFunction())) |
| 173 | N->LowLink = ChildN->LowLink; |
| 174 | } |
| 175 | |
| 176 | // The tail of the stack is the new SCC. Allocate the SCC and pop the stack |
| 177 | // into it. |
| 178 | SCC *NewSCC = new (SCCBPA.Allocate()) SCC(); |
| 179 | |
| 180 | // Because we don't follow the strict Tarjan recursive formulation, walk |
| 181 | // from the top of the stack down, propagating the lowest link and stopping |
| 182 | // when the DFS number is the lowest link. |
| 183 | int LowestLink = N->LowLink; |
| 184 | do { |
| 185 | Node *SCCN = DFSStack.pop_back_val().first; |
| 186 | SCCMap.insert(std::make_pair(&SCCN->getFunction(), NewSCC)); |
| 187 | NewSCC->Nodes.push_back(SCCN); |
| 188 | LowestLink = std::min(LowestLink, SCCN->LowLink); |
| 189 | bool Inserted = |
| 190 | NewSCC->NodeSet.insert(&SCCN->getFunction()); |
| 191 | (void)Inserted; |
| 192 | assert(Inserted && "Cannot have duplicates in the DFSStack!"); |
| 193 | } while (!DFSStack.empty() && LowestLink <= DFSStack.back().first->DFSNumber); |
| 194 | assert(LowestLink == NewSCC->Nodes.back()->DFSNumber && |
| 195 | "Cannot stop with a DFS number greater than the lowest link!"); |
| 196 | |
| 197 | // A final pass over all edges in the SCC (this remains linear as we only |
| 198 | // do this once when we build the SCC) to connect it to the parent sets of |
| 199 | // its children. |
| 200 | bool IsLeafSCC = true; |
| 201 | for (Node *SCCN : NewSCC->Nodes) |
| 202 | for (Node *SCCChildN : *SCCN) { |
| 203 | if (NewSCC->NodeSet.count(&SCCChildN->getFunction())) |
| 204 | continue; |
| 205 | SCC *ChildSCC = SCCMap.lookup(&SCCChildN->getFunction()); |
| 206 | assert(ChildSCC && |
| 207 | "Must have all child SCCs processed when building a new SCC!"); |
| 208 | ChildSCC->ParentSCCs.insert(NewSCC); |
| 209 | IsLeafSCC = false; |
| 210 | } |
| 211 | |
| 212 | // For the SCCs where we fine no child SCCs, add them to the leaf list. |
| 213 | if (IsLeafSCC) |
| 214 | LeafSCCs.push_back(NewSCC); |
| 215 | |
| 216 | return NewSCC; |
| 217 | } |
| 218 | |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 219 | char LazyCallGraphAnalysis::PassID; |
| 220 | |
| 221 | LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} |
| 222 | |
| 223 | static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N, |
| 224 | SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) { |
| 225 | // Recurse depth first through the nodes. |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 226 | for (LazyCallGraph::Node *ChildN : N) |
| 227 | if (Printed.insert(ChildN)) |
| 228 | printNodes(OS, *ChildN, Printed); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 229 | |
| 230 | OS << " Call edges in function: " << N.getFunction().getName() << "\n"; |
| 231 | for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I) |
| 232 | OS << " -> " << I->getFunction().getName() << "\n"; |
| 233 | |
| 234 | OS << "\n"; |
| 235 | } |
| 236 | |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 237 | static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) { |
| 238 | ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end()); |
| 239 | OS << " SCC with " << SCCSize << " functions:\n"; |
| 240 | |
| 241 | for (LazyCallGraph::Node *N : SCC) |
| 242 | OS << " " << N->getFunction().getName() << "\n"; |
| 243 | |
| 244 | OS << "\n"; |
| 245 | } |
| 246 | |
Chandler Carruth | e9b5061 | 2014-03-10 02:14:14 +0000 | [diff] [blame] | 247 | PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M, |
| 248 | ModuleAnalysisManager *AM) { |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 249 | LazyCallGraph &G = AM->getResult<LazyCallGraphAnalysis>(M); |
| 250 | |
Chandler Carruth | e9b5061 | 2014-03-10 02:14:14 +0000 | [diff] [blame] | 251 | OS << "Printing the call graph for module: " << M->getModuleIdentifier() |
| 252 | << "\n\n"; |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 253 | |
| 254 | SmallPtrSet<LazyCallGraph::Node *, 16> Printed; |
Chandler Carruth | b9e2f8c | 2014-03-09 12:20:34 +0000 | [diff] [blame] | 255 | for (LazyCallGraph::Node *N : G) |
| 256 | if (Printed.insert(N)) |
| 257 | printNodes(OS, *N, Printed); |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 258 | |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 259 | for (LazyCallGraph::SCC *SCC : G.postorder_sccs()) |
| 260 | printSCC(OS, *SCC); |
| 261 | |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 262 | return PreservedAnalyses::all(); |
Chandler Carruth | 18eadd92 | 2014-04-18 10:50:32 +0000 | [diff] [blame] | 263 | |
Chandler Carruth | bf71a34 | 2014-02-06 04:37:03 +0000 | [diff] [blame] | 264 | } |