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 &NewFn) { 100 if (CG) 101 CG->addToCallGraph(&NewFn); 102 else if (LCG) 103 LCG->addNewFunctionIntoSCC(NewFn, *SCC); 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