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 if (FAM) 124 FAM->clear(DeadFn, DeadFn.getName()); 125 } 126 127 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) { 128 OldFn.removeDeadConstantUsers(); 129 ReplacedFunctions.insert(&OldFn); 130 if (CG) { 131 // Update the call graph for the newly promoted function. 132 CallGraphNode *OldCGN = (*CG)[&OldFn]; 133 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn); 134 NewCGN->stealCalledFunctionsFrom(OldCGN); 135 CG->ReplaceExternalCallEdge(OldCGN, NewCGN); 136 137 // And update the SCC we're iterating as well. 138 CGSCC->ReplaceNode(OldCGN, NewCGN); 139 } else if (LCG) { 140 // Directly substitute the functions in the call graph. 141 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn); 142 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn); 143 } 144 removeFunction(OldFn); 145 } 146 147 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) { 148 // This is only necessary in the (old) CG. 149 if (!CG) 150 return true; 151 152 Function *Caller = OldCS.getCaller(); 153 CallGraphNode *NewCalleeNode = 154 CG->getOrInsertFunction(NewCS.getCalledFunction()); 155 CallGraphNode *CallerNode = (*CG)[Caller]; 156 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) { 157 return CR.first && *CR.first == &OldCS; 158 })) 159 return false; 160 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode); 161 return true; 162 } 163 164 void CallGraphUpdater::removeCallSite(CallBase &CS) { 165 // This is only necessary in the (old) CG. 166 if (!CG) 167 return; 168 169 Function *Caller = CS.getCaller(); 170 CallGraphNode *CallerNode = (*CG)[Caller]; 171 CallerNode->removeCallEdgeFor(CS); 172 } 173