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