1 //===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// 10 /// This file provides interfaces used to manipulate a call graph, regardless 11 /// if it is a "old style" CallGraph or an "new style" LazyCallGraph. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/CallGraphUpdater.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/Transforms/Utils/ModuleUtils.h" 18 19 using namespace llvm; 20 21 bool CallGraphUpdater::finalize() { 22 if (!DeadFunctionsInComdats.empty()) { 23 filterDeadComdatFunctions(*DeadFunctionsInComdats.front()->getParent(), 24 DeadFunctionsInComdats); 25 DeadFunctions.append(DeadFunctionsInComdats.begin(), 26 DeadFunctionsInComdats.end()); 27 } 28 29 if (CG) { 30 // First remove all references, e.g., outgoing via called functions. This is 31 // necessary as we can delete functions that have circular references. 32 for (Function *DeadFn : DeadFunctions) { 33 DeadFn->removeDeadConstantUsers(); 34 CallGraphNode *DeadCGN = (*CG)[DeadFn]; 35 DeadCGN->removeAllCalledFunctions(); 36 CG->getExternalCallingNode()->removeAnyCallEdgeTo(DeadCGN); 37 DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType())); 38 } 39 40 // Then remove the node and function from the module. 41 for (Function *DeadFn : DeadFunctions) { 42 CallGraphNode *DeadCGN = CG->getOrInsertFunction(DeadFn); 43 assert(DeadCGN->getNumReferences() == 0 && 44 "References should have been handled by now"); 45 delete CG->removeFunctionFromModule(DeadCGN); 46 } 47 } else { 48 // This is the code path for the new lazy call graph and for the case were 49 // no call graph was provided. 50 for (Function *DeadFn : DeadFunctions) { 51 DeadFn->removeDeadConstantUsers(); 52 DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType())); 53 54 if (LCG && !ReplacedFunctions.count(DeadFn)) { 55 // Taken mostly from the inliner: 56 LazyCallGraph::Node &N = LCG->get(*DeadFn); 57 auto *DeadSCC = LCG->lookupSCC(N); 58 assert(DeadSCC && DeadSCC->size() == 1 && 59 &DeadSCC->begin()->getFunction() == DeadFn); 60 auto &DeadRC = DeadSCC->getOuterRefSCC(); 61 62 FunctionAnalysisManager &FAM = 63 AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG) 64 .getManager(); 65 66 FAM.clear(*DeadFn, DeadFn->getName()); 67 AM->clear(*DeadSCC, DeadSCC->getName()); 68 LCG->removeDeadFunction(*DeadFn); 69 70 // Mark the relevant parts of the call graph as invalid so we don't 71 // visit them. 72 UR->InvalidatedSCCs.insert(DeadSCC); 73 UR->InvalidatedRefSCCs.insert(&DeadRC); 74 } 75 76 // The function is now really dead and de-attached from everything. 77 DeadFn->eraseFromParent(); 78 } 79 } 80 81 bool Changed = !DeadFunctions.empty(); 82 DeadFunctionsInComdats.clear(); 83 DeadFunctions.clear(); 84 return Changed; 85 } 86 87 void CallGraphUpdater::reanalyzeFunction(Function &Fn) { 88 if (CG) { 89 CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn); 90 OldCGN->removeAllCalledFunctions(); 91 CG->populateCallGraphNode(OldCGN); 92 } else if (LCG) { 93 LazyCallGraph::Node &N = LCG->get(Fn); 94 LazyCallGraph::SCC *C = LCG->lookupSCC(N); 95 updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM); 96 } 97 } 98 99 void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn, 100 Function &NewFn) { 101 if (CG) 102 CG->addToCallGraph(&NewFn); 103 else if (LCG) 104 LCG->addSplitFunction(OriginalFn, NewFn); 105 } 106 107 void CallGraphUpdater::removeFunction(Function &DeadFn) { 108 DeadFn.deleteBody(); 109 DeadFn.setLinkage(GlobalValue::ExternalLinkage); 110 if (DeadFn.hasComdat()) 111 DeadFunctionsInComdats.push_back(&DeadFn); 112 else 113 DeadFunctions.push_back(&DeadFn); 114 115 // For the old call graph we remove the function from the SCC right away. 116 if (CG && !ReplacedFunctions.count(&DeadFn)) { 117 CallGraphNode *DeadCGN = (*CG)[&DeadFn]; 118 DeadCGN->removeAllCalledFunctions(); 119 CGSCC->DeleteNode(DeadCGN); 120 } 121 } 122 123 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) { 124 OldFn.removeDeadConstantUsers(); 125 ReplacedFunctions.insert(&OldFn); 126 if (CG) { 127 // Update the call graph for the newly promoted function. 128 CallGraphNode *OldCGN = (*CG)[&OldFn]; 129 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn); 130 NewCGN->stealCalledFunctionsFrom(OldCGN); 131 CG->ReplaceExternalCallEdge(OldCGN, NewCGN); 132 133 // And update the SCC we're iterating as well. 134 CGSCC->ReplaceNode(OldCGN, NewCGN); 135 } else if (LCG) { 136 // Directly substitute the functions in the call graph. 137 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn); 138 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn); 139 } 140 removeFunction(OldFn); 141 } 142 143 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) { 144 // This is only necessary in the (old) CG. 145 if (!CG) 146 return true; 147 148 Function *Caller = OldCS.getCaller(); 149 CallGraphNode *NewCalleeNode = 150 CG->getOrInsertFunction(NewCS.getCalledFunction()); 151 CallGraphNode *CallerNode = (*CG)[Caller]; 152 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) { 153 return CR.first && *CR.first == &OldCS; 154 })) 155 return false; 156 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode); 157 return true; 158 } 159 160 void CallGraphUpdater::removeCallSite(CallBase &CS) { 161 // This is only necessary in the (old) CG. 162 if (!CG) 163 return; 164 165 Function *Caller = CS.getCaller(); 166 CallGraphNode *CallerNode = (*CG)[Caller]; 167 CallerNode->removeCallEdgeFor(CS); 168 } 169