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