1 //===- ArgumentPromotion.cpp - Promote by-reference arguments -------------===// 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 // 9 // This pass promotes "by reference" arguments to be "by value" arguments. In 10 // practice, this means looking for internal functions that have pointer 11 // arguments. If it can prove, through the use of alias analysis, that an 12 // argument is *only* loaded, then it can pass the value into the function 13 // instead of the address of the value. This can cause recursive simplification 14 // of code and lead to the elimination of allocas (especially in C++ template 15 // code like the STL). 16 // 17 // This pass also handles aggregate arguments that are passed into a function, 18 // scalarizing them if the elements of the aggregate are only loaded. Note that 19 // by default it refuses to scalarize aggregates which would require passing in 20 // more than three operands to the function, because passing thousands of 21 // operands for a large array or structure is unprofitable! This limit can be 22 // configured or disabled, however. 23 // 24 // Note that this transformation could also be done for arguments that are only 25 // stored to (returning the value instead), but does not currently. This case 26 // would be best handled when and if LLVM begins supporting multiple return 27 // values from functions. 28 // 29 //===----------------------------------------------------------------------===// 30 31 #include "llvm/Transforms/IPO/ArgumentPromotion.h" 32 #include "llvm/ADT/DepthFirstIterator.h" 33 #include "llvm/ADT/None.h" 34 #include "llvm/ADT/Optional.h" 35 #include "llvm/ADT/STLExtras.h" 36 #include "llvm/ADT/SmallPtrSet.h" 37 #include "llvm/ADT/SmallVector.h" 38 #include "llvm/ADT/Statistic.h" 39 #include "llvm/ADT/Twine.h" 40 #include "llvm/Analysis/AliasAnalysis.h" 41 #include "llvm/Analysis/AssumptionCache.h" 42 #include "llvm/Analysis/BasicAliasAnalysis.h" 43 #include "llvm/Analysis/CGSCCPassManager.h" 44 #include "llvm/Analysis/CallGraph.h" 45 #include "llvm/Analysis/CallGraphSCCPass.h" 46 #include "llvm/Analysis/LazyCallGraph.h" 47 #include "llvm/Analysis/Loads.h" 48 #include "llvm/Analysis/MemoryLocation.h" 49 #include "llvm/Analysis/TargetLibraryInfo.h" 50 #include "llvm/Analysis/TargetTransformInfo.h" 51 #include "llvm/IR/Argument.h" 52 #include "llvm/IR/Attributes.h" 53 #include "llvm/IR/BasicBlock.h" 54 #include "llvm/IR/CFG.h" 55 #include "llvm/IR/Constants.h" 56 #include "llvm/IR/DataLayout.h" 57 #include "llvm/IR/DerivedTypes.h" 58 #include "llvm/IR/Function.h" 59 #include "llvm/IR/IRBuilder.h" 60 #include "llvm/IR/InstrTypes.h" 61 #include "llvm/IR/Instruction.h" 62 #include "llvm/IR/Instructions.h" 63 #include "llvm/IR/Metadata.h" 64 #include "llvm/IR/Module.h" 65 #include "llvm/IR/NoFolder.h" 66 #include "llvm/IR/PassManager.h" 67 #include "llvm/IR/Type.h" 68 #include "llvm/IR/Use.h" 69 #include "llvm/IR/User.h" 70 #include "llvm/IR/Value.h" 71 #include "llvm/InitializePasses.h" 72 #include "llvm/Pass.h" 73 #include "llvm/Support/Casting.h" 74 #include "llvm/Support/Debug.h" 75 #include "llvm/Support/FormatVariadic.h" 76 #include "llvm/Support/raw_ostream.h" 77 #include "llvm/Transforms/IPO.h" 78 #include <algorithm> 79 #include <cassert> 80 #include <cstdint> 81 #include <functional> 82 #include <iterator> 83 #include <map> 84 #include <set> 85 #include <string> 86 #include <utility> 87 #include <vector> 88 89 using namespace llvm; 90 91 #define DEBUG_TYPE "argpromotion" 92 93 STATISTIC(NumArgumentsPromoted, "Number of pointer arguments promoted"); 94 STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted"); 95 STATISTIC(NumByValArgsPromoted, "Number of byval arguments promoted"); 96 STATISTIC(NumArgumentsDead, "Number of dead pointer args eliminated"); 97 98 /// A vector used to hold the indices of a single GEP instruction 99 using IndicesVector = std::vector<uint64_t>; 100 101 /// DoPromotion - This method actually performs the promotion of the specified 102 /// arguments, and returns the new function. At this point, we know that it's 103 /// safe to do so. 104 static Function * 105 doPromotion(Function *F, SmallPtrSetImpl<Argument *> &ArgsToPromote, 106 SmallPtrSetImpl<Argument *> &ByValArgsToTransform, 107 Optional<function_ref<void(CallBase &OldCS, CallBase &NewCS)>> 108 ReplaceCallSite) { 109 // Start by computing a new prototype for the function, which is the same as 110 // the old function, but has modified arguments. 111 FunctionType *FTy = F->getFunctionType(); 112 std::vector<Type *> Params; 113 114 using ScalarizeTable = std::set<std::pair<Type *, IndicesVector>>; 115 116 // ScalarizedElements - If we are promoting a pointer that has elements 117 // accessed out of it, keep track of which elements are accessed so that we 118 // can add one argument for each. 119 // 120 // Arguments that are directly loaded will have a zero element value here, to 121 // handle cases where there are both a direct load and GEP accesses. 122 std::map<Argument *, ScalarizeTable> ScalarizedElements; 123 124 // OriginalLoads - Keep track of a representative load instruction from the 125 // original function so that we can tell the alias analysis implementation 126 // what the new GEP/Load instructions we are inserting look like. 127 // We need to keep the original loads for each argument and the elements 128 // of the argument that are accessed. 129 std::map<std::pair<Argument *, IndicesVector>, LoadInst *> OriginalLoads; 130 131 // Attribute - Keep track of the parameter attributes for the arguments 132 // that we are *not* promoting. For the ones that we do promote, the parameter 133 // attributes are lost 134 SmallVector<AttributeSet, 8> ArgAttrVec; 135 AttributeList PAL = F->getAttributes(); 136 137 // First, determine the new argument list 138 unsigned ArgNo = 0; 139 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 140 ++I, ++ArgNo) { 141 if (ByValArgsToTransform.count(&*I)) { 142 // Simple byval argument? Just add all the struct element types. 143 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 144 StructType *STy = cast<StructType>(AgTy); 145 Params.insert(Params.end(), STy->element_begin(), STy->element_end()); 146 ArgAttrVec.insert(ArgAttrVec.end(), STy->getNumElements(), 147 AttributeSet()); 148 ++NumByValArgsPromoted; 149 } else if (!ArgsToPromote.count(&*I)) { 150 // Unchanged argument 151 Params.push_back(I->getType()); 152 ArgAttrVec.push_back(PAL.getParamAttributes(ArgNo)); 153 } else if (I->use_empty()) { 154 // Dead argument (which are always marked as promotable) 155 ++NumArgumentsDead; 156 157 // There may be remaining metadata uses of the argument for things like 158 // llvm.dbg.value. Replace them with undef. 159 I->replaceAllUsesWith(UndefValue::get(I->getType())); 160 } else { 161 // Okay, this is being promoted. This means that the only uses are loads 162 // or GEPs which are only used by loads 163 164 // In this table, we will track which indices are loaded from the argument 165 // (where direct loads are tracked as no indices). 166 ScalarizeTable &ArgIndices = ScalarizedElements[&*I]; 167 for (User *U : I->users()) { 168 Instruction *UI = cast<Instruction>(U); 169 Type *SrcTy; 170 if (LoadInst *L = dyn_cast<LoadInst>(UI)) 171 SrcTy = L->getType(); 172 else 173 SrcTy = cast<GetElementPtrInst>(UI)->getSourceElementType(); 174 IndicesVector Indices; 175 Indices.reserve(UI->getNumOperands() - 1); 176 // Since loads will only have a single operand, and GEPs only a single 177 // non-index operand, this will record direct loads without any indices, 178 // and gep+loads with the GEP indices. 179 for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end(); 180 II != IE; ++II) 181 Indices.push_back(cast<ConstantInt>(*II)->getSExtValue()); 182 // GEPs with a single 0 index can be merged with direct loads 183 if (Indices.size() == 1 && Indices.front() == 0) 184 Indices.clear(); 185 ArgIndices.insert(std::make_pair(SrcTy, Indices)); 186 LoadInst *OrigLoad; 187 if (LoadInst *L = dyn_cast<LoadInst>(UI)) 188 OrigLoad = L; 189 else 190 // Take any load, we will use it only to update Alias Analysis 191 OrigLoad = cast<LoadInst>(UI->user_back()); 192 OriginalLoads[std::make_pair(&*I, Indices)] = OrigLoad; 193 } 194 195 // Add a parameter to the function for each element passed in. 196 for (const auto &ArgIndex : ArgIndices) { 197 // not allowed to dereference ->begin() if size() is 0 198 Params.push_back(GetElementPtrInst::getIndexedType( 199 cast<PointerType>(I->getType())->getElementType(), 200 ArgIndex.second)); 201 ArgAttrVec.push_back(AttributeSet()); 202 assert(Params.back()); 203 } 204 205 if (ArgIndices.size() == 1 && ArgIndices.begin()->second.empty()) 206 ++NumArgumentsPromoted; 207 else 208 ++NumAggregatesPromoted; 209 } 210 } 211 212 Type *RetTy = FTy->getReturnType(); 213 214 // Construct the new function type using the new arguments. 215 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 216 217 // Create the new function body and insert it into the module. 218 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace(), 219 F->getName()); 220 NF->copyAttributesFrom(F); 221 222 // Patch the pointer to LLVM function in debug info descriptor. 223 NF->setSubprogram(F->getSubprogram()); 224 F->setSubprogram(nullptr); 225 226 LLVM_DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n" 227 << "From: " << *F); 228 229 // Recompute the parameter attributes list based on the new arguments for 230 // the function. 231 NF->setAttributes(AttributeList::get(F->getContext(), PAL.getFnAttributes(), 232 PAL.getRetAttributes(), ArgAttrVec)); 233 ArgAttrVec.clear(); 234 235 F->getParent()->getFunctionList().insert(F->getIterator(), NF); 236 NF->takeName(F); 237 238 // Loop over all of the callers of the function, transforming the call sites 239 // to pass in the loaded pointers. 240 // 241 SmallVector<Value *, 16> Args; 242 while (!F->use_empty()) { 243 CallBase &CB = cast<CallBase>(*F->user_back()); 244 assert(CB.getCalledFunction() == F); 245 const AttributeList &CallPAL = CB.getAttributes(); 246 IRBuilder<NoFolder> IRB(&CB); 247 248 // Loop over the operands, inserting GEP and loads in the caller as 249 // appropriate. 250 auto AI = CB.arg_begin(); 251 ArgNo = 0; 252 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 253 ++I, ++AI, ++ArgNo) 254 if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) { 255 Args.push_back(*AI); // Unmodified argument 256 ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo)); 257 } else if (ByValArgsToTransform.count(&*I)) { 258 // Emit a GEP and load for each element of the struct. 259 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 260 StructType *STy = cast<StructType>(AgTy); 261 Value *Idxs[2] = { 262 ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr}; 263 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 264 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 265 auto *Idx = 266 IRB.CreateGEP(STy, *AI, Idxs, (*AI)->getName() + "." + Twine(i)); 267 // TODO: Tell AA about the new values? 268 Args.push_back(IRB.CreateLoad(STy->getElementType(i), Idx, 269 Idx->getName() + ".val")); 270 ArgAttrVec.push_back(AttributeSet()); 271 } 272 } else if (!I->use_empty()) { 273 // Non-dead argument: insert GEPs and loads as appropriate. 274 ScalarizeTable &ArgIndices = ScalarizedElements[&*I]; 275 // Store the Value* version of the indices in here, but declare it now 276 // for reuse. 277 std::vector<Value *> Ops; 278 for (const auto &ArgIndex : ArgIndices) { 279 Value *V = *AI; 280 LoadInst *OrigLoad = 281 OriginalLoads[std::make_pair(&*I, ArgIndex.second)]; 282 if (!ArgIndex.second.empty()) { 283 Ops.reserve(ArgIndex.second.size()); 284 Type *ElTy = V->getType(); 285 for (auto II : ArgIndex.second) { 286 // Use i32 to index structs, and i64 for others (pointers/arrays). 287 // This satisfies GEP constraints. 288 Type *IdxTy = 289 (ElTy->isStructTy() ? Type::getInt32Ty(F->getContext()) 290 : Type::getInt64Ty(F->getContext())); 291 Ops.push_back(ConstantInt::get(IdxTy, II)); 292 // Keep track of the type we're currently indexing. 293 if (auto *ElPTy = dyn_cast<PointerType>(ElTy)) 294 ElTy = ElPTy->getElementType(); 295 else 296 ElTy = GetElementPtrInst::getTypeAtIndex(ElTy, II); 297 } 298 // And create a GEP to extract those indices. 299 V = IRB.CreateGEP(ArgIndex.first, V, Ops, V->getName() + ".idx"); 300 Ops.clear(); 301 } 302 // Since we're replacing a load make sure we take the alignment 303 // of the previous load. 304 LoadInst *newLoad = 305 IRB.CreateLoad(OrigLoad->getType(), V, V->getName() + ".val"); 306 newLoad->setAlignment(OrigLoad->getAlign()); 307 // Transfer the AA info too. 308 AAMDNodes AAInfo; 309 OrigLoad->getAAMetadata(AAInfo); 310 newLoad->setAAMetadata(AAInfo); 311 312 Args.push_back(newLoad); 313 ArgAttrVec.push_back(AttributeSet()); 314 } 315 } 316 317 // Push any varargs arguments on the list. 318 for (; AI != CB.arg_end(); ++AI, ++ArgNo) { 319 Args.push_back(*AI); 320 ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo)); 321 } 322 323 SmallVector<OperandBundleDef, 1> OpBundles; 324 CB.getOperandBundlesAsDefs(OpBundles); 325 326 CallBase *NewCS = nullptr; 327 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 328 NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 329 Args, OpBundles, "", &CB); 330 } else { 331 auto *NewCall = CallInst::Create(NF, Args, OpBundles, "", &CB); 332 NewCall->setTailCallKind(cast<CallInst>(&CB)->getTailCallKind()); 333 NewCS = NewCall; 334 } 335 NewCS->setCallingConv(CB.getCallingConv()); 336 NewCS->setAttributes( 337 AttributeList::get(F->getContext(), CallPAL.getFnAttributes(), 338 CallPAL.getRetAttributes(), ArgAttrVec)); 339 NewCS->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg}); 340 Args.clear(); 341 ArgAttrVec.clear(); 342 343 // Update the callgraph to know that the callsite has been transformed. 344 if (ReplaceCallSite) 345 (*ReplaceCallSite)(CB, *NewCS); 346 347 if (!CB.use_empty()) { 348 CB.replaceAllUsesWith(NewCS); 349 NewCS->takeName(&CB); 350 } 351 352 // Finally, remove the old call from the program, reducing the use-count of 353 // F. 354 CB.eraseFromParent(); 355 } 356 357 const DataLayout &DL = F->getParent()->getDataLayout(); 358 359 // Since we have now created the new function, splice the body of the old 360 // function right into the new function, leaving the old rotting hulk of the 361 // function empty. 362 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 363 364 // Loop over the argument list, transferring uses of the old arguments over to 365 // the new arguments, also transferring over the names as well. 366 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 367 I2 = NF->arg_begin(); 368 I != E; ++I) { 369 if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) { 370 // If this is an unmodified argument, move the name and users over to the 371 // new version. 372 I->replaceAllUsesWith(&*I2); 373 I2->takeName(&*I); 374 ++I2; 375 continue; 376 } 377 378 if (ByValArgsToTransform.count(&*I)) { 379 // In the callee, we create an alloca, and store each of the new incoming 380 // arguments into the alloca. 381 Instruction *InsertPt = &NF->begin()->front(); 382 383 // Just add all the struct element types. 384 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 385 Value *TheAlloca = new AllocaInst( 386 AgTy, DL.getAllocaAddrSpace(), nullptr, 387 I->getParamAlign().getValueOr(DL.getPrefTypeAlign(AgTy)), "", 388 InsertPt); 389 StructType *STy = cast<StructType>(AgTy); 390 Value *Idxs[2] = {ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 391 nullptr}; 392 393 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 394 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 395 Value *Idx = GetElementPtrInst::Create( 396 AgTy, TheAlloca, Idxs, TheAlloca->getName() + "." + Twine(i), 397 InsertPt); 398 I2->setName(I->getName() + "." + Twine(i)); 399 new StoreInst(&*I2++, Idx, InsertPt); 400 } 401 402 // Anything that used the arg should now use the alloca. 403 I->replaceAllUsesWith(TheAlloca); 404 TheAlloca->takeName(&*I); 405 406 // If the alloca is used in a call, we must clear the tail flag since 407 // the callee now uses an alloca from the caller. 408 for (User *U : TheAlloca->users()) { 409 CallInst *Call = dyn_cast<CallInst>(U); 410 if (!Call) 411 continue; 412 Call->setTailCall(false); 413 } 414 continue; 415 } 416 417 if (I->use_empty()) 418 continue; 419 420 // Otherwise, if we promoted this argument, then all users are load 421 // instructions (or GEPs with only load users), and all loads should be 422 // using the new argument that we added. 423 ScalarizeTable &ArgIndices = ScalarizedElements[&*I]; 424 425 while (!I->use_empty()) { 426 if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) { 427 assert(ArgIndices.begin()->second.empty() && 428 "Load element should sort to front!"); 429 I2->setName(I->getName() + ".val"); 430 LI->replaceAllUsesWith(&*I2); 431 LI->eraseFromParent(); 432 LLVM_DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName() 433 << "' in function '" << F->getName() << "'\n"); 434 } else { 435 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back()); 436 IndicesVector Operands; 437 Operands.reserve(GEP->getNumIndices()); 438 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 439 II != IE; ++II) 440 Operands.push_back(cast<ConstantInt>(*II)->getSExtValue()); 441 442 // GEPs with a single 0 index can be merged with direct loads 443 if (Operands.size() == 1 && Operands.front() == 0) 444 Operands.clear(); 445 446 Function::arg_iterator TheArg = I2; 447 for (ScalarizeTable::iterator It = ArgIndices.begin(); 448 It->second != Operands; ++It, ++TheArg) { 449 assert(It != ArgIndices.end() && "GEP not handled??"); 450 } 451 452 TheArg->setName(formatv("{0}.{1:$[.]}.val", I->getName(), 453 make_range(Operands.begin(), Operands.end()))); 454 455 LLVM_DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName() 456 << "' of function '" << NF->getName() << "'\n"); 457 458 // All of the uses must be load instructions. Replace them all with 459 // the argument specified by ArgNo. 460 while (!GEP->use_empty()) { 461 LoadInst *L = cast<LoadInst>(GEP->user_back()); 462 L->replaceAllUsesWith(&*TheArg); 463 L->eraseFromParent(); 464 } 465 GEP->eraseFromParent(); 466 } 467 } 468 469 // Increment I2 past all of the arguments added for this promoted pointer. 470 std::advance(I2, ArgIndices.size()); 471 } 472 473 return NF; 474 } 475 476 /// Return true if we can prove that all callees pass in a valid pointer for the 477 /// specified function argument. 478 static bool allCallersPassValidPointerForArgument(Argument *Arg, Type *Ty) { 479 Function *Callee = Arg->getParent(); 480 const DataLayout &DL = Callee->getParent()->getDataLayout(); 481 482 unsigned ArgNo = Arg->getArgNo(); 483 484 // Look at all call sites of the function. At this point we know we only have 485 // direct callees. 486 for (User *U : Callee->users()) { 487 CallBase &CB = cast<CallBase>(*U); 488 489 if (!isDereferenceablePointer(CB.getArgOperand(ArgNo), Ty, DL)) 490 return false; 491 } 492 return true; 493 } 494 495 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size 496 /// that is greater than or equal to the size of prefix, and each of the 497 /// elements in Prefix is the same as the corresponding elements in Longer. 498 /// 499 /// This means it also returns true when Prefix and Longer are equal! 500 static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer) { 501 if (Prefix.size() > Longer.size()) 502 return false; 503 return std::equal(Prefix.begin(), Prefix.end(), Longer.begin()); 504 } 505 506 /// Checks if Indices, or a prefix of Indices, is in Set. 507 static bool prefixIn(const IndicesVector &Indices, 508 std::set<IndicesVector> &Set) { 509 std::set<IndicesVector>::iterator Low; 510 Low = Set.upper_bound(Indices); 511 if (Low != Set.begin()) 512 Low--; 513 // Low is now the last element smaller than or equal to Indices. This means 514 // it points to a prefix of Indices (possibly Indices itself), if such 515 // prefix exists. 516 // 517 // This load is safe if any prefix of its operands is safe to load. 518 return Low != Set.end() && isPrefix(*Low, Indices); 519 } 520 521 /// Mark the given indices (ToMark) as safe in the given set of indices 522 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there 523 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe 524 /// already. Furthermore, any indices that Indices is itself a prefix of, are 525 /// removed from Safe (since they are implicitely safe because of Indices now). 526 static void markIndicesSafe(const IndicesVector &ToMark, 527 std::set<IndicesVector> &Safe) { 528 std::set<IndicesVector>::iterator Low; 529 Low = Safe.upper_bound(ToMark); 530 // Guard against the case where Safe is empty 531 if (Low != Safe.begin()) 532 Low--; 533 // Low is now the last element smaller than or equal to Indices. This 534 // means it points to a prefix of Indices (possibly Indices itself), if 535 // such prefix exists. 536 if (Low != Safe.end()) { 537 if (isPrefix(*Low, ToMark)) 538 // If there is already a prefix of these indices (or exactly these 539 // indices) marked a safe, don't bother adding these indices 540 return; 541 542 // Increment Low, so we can use it as a "insert before" hint 543 ++Low; 544 } 545 // Insert 546 Low = Safe.insert(Low, ToMark); 547 ++Low; 548 // If there we're a prefix of longer index list(s), remove those 549 std::set<IndicesVector>::iterator End = Safe.end(); 550 while (Low != End && isPrefix(ToMark, *Low)) { 551 std::set<IndicesVector>::iterator Remove = Low; 552 ++Low; 553 Safe.erase(Remove); 554 } 555 } 556 557 /// isSafeToPromoteArgument - As you might guess from the name of this method, 558 /// it checks to see if it is both safe and useful to promote the argument. 559 /// This method limits promotion of aggregates to only promote up to three 560 /// elements of the aggregate in order to avoid exploding the number of 561 /// arguments passed in. 562 static bool isSafeToPromoteArgument(Argument *Arg, Type *ByValTy, AAResults &AAR, 563 unsigned MaxElements) { 564 using GEPIndicesSet = std::set<IndicesVector>; 565 566 // Quick exit for unused arguments 567 if (Arg->use_empty()) 568 return true; 569 570 // We can only promote this argument if all of the uses are loads, or are GEP 571 // instructions (with constant indices) that are subsequently loaded. 572 // 573 // Promoting the argument causes it to be loaded in the caller 574 // unconditionally. This is only safe if we can prove that either the load 575 // would have happened in the callee anyway (ie, there is a load in the entry 576 // block) or the pointer passed in at every call site is guaranteed to be 577 // valid. 578 // In the former case, invalid loads can happen, but would have happened 579 // anyway, in the latter case, invalid loads won't happen. This prevents us 580 // from introducing an invalid load that wouldn't have happened in the 581 // original code. 582 // 583 // This set will contain all sets of indices that are loaded in the entry 584 // block, and thus are safe to unconditionally load in the caller. 585 GEPIndicesSet SafeToUnconditionallyLoad; 586 587 // This set contains all the sets of indices that we are planning to promote. 588 // This makes it possible to limit the number of arguments added. 589 GEPIndicesSet ToPromote; 590 591 // If the pointer is always valid, any load with first index 0 is valid. 592 593 if (ByValTy) 594 SafeToUnconditionallyLoad.insert(IndicesVector(1, 0)); 595 596 // Whenever a new underlying type for the operand is found, make sure it's 597 // consistent with the GEPs and loads we've already seen and, if necessary, 598 // use it to see if all incoming pointers are valid (which implies the 0-index 599 // is safe). 600 Type *BaseTy = ByValTy; 601 auto UpdateBaseTy = [&](Type *NewBaseTy) { 602 if (BaseTy) 603 return BaseTy == NewBaseTy; 604 605 BaseTy = NewBaseTy; 606 if (allCallersPassValidPointerForArgument(Arg, BaseTy)) { 607 assert(SafeToUnconditionallyLoad.empty()); 608 SafeToUnconditionallyLoad.insert(IndicesVector(1, 0)); 609 } 610 611 return true; 612 }; 613 614 // First, iterate the entry block and mark loads of (geps of) arguments as 615 // safe. 616 BasicBlock &EntryBlock = Arg->getParent()->front(); 617 // Declare this here so we can reuse it 618 IndicesVector Indices; 619 for (Instruction &I : EntryBlock) 620 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 621 Value *V = LI->getPointerOperand(); 622 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) { 623 V = GEP->getPointerOperand(); 624 if (V == Arg) { 625 // This load actually loads (part of) Arg? Check the indices then. 626 Indices.reserve(GEP->getNumIndices()); 627 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 628 II != IE; ++II) 629 if (ConstantInt *CI = dyn_cast<ConstantInt>(*II)) 630 Indices.push_back(CI->getSExtValue()); 631 else 632 // We found a non-constant GEP index for this argument? Bail out 633 // right away, can't promote this argument at all. 634 return false; 635 636 if (!UpdateBaseTy(GEP->getSourceElementType())) 637 return false; 638 639 // Indices checked out, mark them as safe 640 markIndicesSafe(Indices, SafeToUnconditionallyLoad); 641 Indices.clear(); 642 } 643 } else if (V == Arg) { 644 // Direct loads are equivalent to a GEP with a single 0 index. 645 markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad); 646 647 if (BaseTy && LI->getType() != BaseTy) 648 return false; 649 650 BaseTy = LI->getType(); 651 } 652 } 653 654 // Now, iterate all uses of the argument to see if there are any uses that are 655 // not (GEP+)loads, or any (GEP+)loads that are not safe to promote. 656 SmallVector<LoadInst *, 16> Loads; 657 IndicesVector Operands; 658 for (Use &U : Arg->uses()) { 659 User *UR = U.getUser(); 660 Operands.clear(); 661 if (LoadInst *LI = dyn_cast<LoadInst>(UR)) { 662 // Don't hack volatile/atomic loads 663 if (!LI->isSimple()) 664 return false; 665 Loads.push_back(LI); 666 // Direct loads are equivalent to a GEP with a zero index and then a load. 667 Operands.push_back(0); 668 669 if (!UpdateBaseTy(LI->getType())) 670 return false; 671 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) { 672 if (GEP->use_empty()) { 673 // Dead GEP's cause trouble later. Just remove them if we run into 674 // them. 675 GEP->eraseFromParent(); 676 // TODO: This runs the above loop over and over again for dead GEPs 677 // Couldn't we just do increment the UI iterator earlier and erase the 678 // use? 679 return isSafeToPromoteArgument(Arg, ByValTy, AAR, MaxElements); 680 } 681 682 if (!UpdateBaseTy(GEP->getSourceElementType())) 683 return false; 684 685 // Ensure that all of the indices are constants. 686 for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e; 687 ++i) 688 if (ConstantInt *C = dyn_cast<ConstantInt>(*i)) 689 Operands.push_back(C->getSExtValue()); 690 else 691 return false; // Not a constant operand GEP! 692 693 // Ensure that the only users of the GEP are load instructions. 694 for (User *GEPU : GEP->users()) 695 if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) { 696 // Don't hack volatile/atomic loads 697 if (!LI->isSimple()) 698 return false; 699 Loads.push_back(LI); 700 } else { 701 // Other uses than load? 702 return false; 703 } 704 } else { 705 return false; // Not a load or a GEP. 706 } 707 708 // Now, see if it is safe to promote this load / loads of this GEP. Loading 709 // is safe if Operands, or a prefix of Operands, is marked as safe. 710 if (!prefixIn(Operands, SafeToUnconditionallyLoad)) 711 return false; 712 713 // See if we are already promoting a load with these indices. If not, check 714 // to make sure that we aren't promoting too many elements. If so, nothing 715 // to do. 716 if (ToPromote.find(Operands) == ToPromote.end()) { 717 if (MaxElements > 0 && ToPromote.size() == MaxElements) { 718 LLVM_DEBUG(dbgs() << "argpromotion not promoting argument '" 719 << Arg->getName() 720 << "' because it would require adding more " 721 << "than " << MaxElements 722 << " arguments to the function.\n"); 723 // We limit aggregate promotion to only promoting up to a fixed number 724 // of elements of the aggregate. 725 return false; 726 } 727 ToPromote.insert(std::move(Operands)); 728 } 729 } 730 731 if (Loads.empty()) 732 return true; // No users, this is a dead argument. 733 734 // Okay, now we know that the argument is only used by load instructions and 735 // it is safe to unconditionally perform all of them. Use alias analysis to 736 // check to see if the pointer is guaranteed to not be modified from entry of 737 // the function to each of the load instructions. 738 739 // Because there could be several/many load instructions, remember which 740 // blocks we know to be transparent to the load. 741 df_iterator_default_set<BasicBlock *, 16> TranspBlocks; 742 743 for (LoadInst *Load : Loads) { 744 // Check to see if the load is invalidated from the start of the block to 745 // the load itself. 746 BasicBlock *BB = Load->getParent(); 747 748 MemoryLocation Loc = MemoryLocation::get(Load); 749 if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, ModRefInfo::Mod)) 750 return false; // Pointer is invalidated! 751 752 // Now check every path from the entry block to the load for transparency. 753 // To do this, we perform a depth first search on the inverse CFG from the 754 // loading block. 755 for (BasicBlock *P : predecessors(BB)) { 756 for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks)) 757 if (AAR.canBasicBlockModify(*TranspBB, Loc)) 758 return false; 759 } 760 } 761 762 // If the path from the entry of the function to each load is free of 763 // instructions that potentially invalidate the load, we can make the 764 // transformation! 765 return true; 766 } 767 768 bool ArgumentPromotionPass::isDenselyPacked(Type *type, const DataLayout &DL) { 769 // There is no size information, so be conservative. 770 if (!type->isSized()) 771 return false; 772 773 // If the alloc size is not equal to the storage size, then there are padding 774 // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128. 775 if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type)) 776 return false; 777 778 // FIXME: This isn't the right way to check for padding in vectors with 779 // non-byte-size elements. 780 if (VectorType *seqTy = dyn_cast<VectorType>(type)) 781 return isDenselyPacked(seqTy->getElementType(), DL); 782 783 // For array types, check for padding within members. 784 if (ArrayType *seqTy = dyn_cast<ArrayType>(type)) 785 return isDenselyPacked(seqTy->getElementType(), DL); 786 787 if (!isa<StructType>(type)) 788 return true; 789 790 // Check for padding within and between elements of a struct. 791 StructType *StructTy = cast<StructType>(type); 792 const StructLayout *Layout = DL.getStructLayout(StructTy); 793 uint64_t StartPos = 0; 794 for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) { 795 Type *ElTy = StructTy->getElementType(i); 796 if (!isDenselyPacked(ElTy, DL)) 797 return false; 798 if (StartPos != Layout->getElementOffsetInBits(i)) 799 return false; 800 StartPos += DL.getTypeAllocSizeInBits(ElTy); 801 } 802 803 return true; 804 } 805 806 /// Checks if the padding bytes of an argument could be accessed. 807 static bool canPaddingBeAccessed(Argument *arg) { 808 assert(arg->hasByValAttr()); 809 810 // Track all the pointers to the argument to make sure they are not captured. 811 SmallPtrSet<Value *, 16> PtrValues; 812 PtrValues.insert(arg); 813 814 // Track all of the stores. 815 SmallVector<StoreInst *, 16> Stores; 816 817 // Scan through the uses recursively to make sure the pointer is always used 818 // sanely. 819 SmallVector<Value *, 16> WorkList; 820 WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end()); 821 while (!WorkList.empty()) { 822 Value *V = WorkList.back(); 823 WorkList.pop_back(); 824 if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) { 825 if (PtrValues.insert(V).second) 826 WorkList.insert(WorkList.end(), V->user_begin(), V->user_end()); 827 } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) { 828 Stores.push_back(Store); 829 } else if (!isa<LoadInst>(V)) { 830 return true; 831 } 832 } 833 834 // Check to make sure the pointers aren't captured 835 for (StoreInst *Store : Stores) 836 if (PtrValues.count(Store->getValueOperand())) 837 return true; 838 839 return false; 840 } 841 842 bool ArgumentPromotionPass::areFunctionArgsABICompatible( 843 const Function &F, const TargetTransformInfo &TTI, 844 SmallPtrSetImpl<Argument *> &ArgsToPromote, 845 SmallPtrSetImpl<Argument *> &ByValArgsToTransform) { 846 for (const Use &U : F.uses()) { 847 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 848 if (!CB) 849 return false; 850 const Function *Caller = CB->getCaller(); 851 const Function *Callee = CB->getCalledFunction(); 852 if (!TTI.areFunctionArgsABICompatible(Caller, Callee, ArgsToPromote) || 853 !TTI.areFunctionArgsABICompatible(Caller, Callee, ByValArgsToTransform)) 854 return false; 855 } 856 return true; 857 } 858 859 /// PromoteArguments - This method checks the specified function to see if there 860 /// are any promotable arguments and if it is safe to promote the function (for 861 /// example, all callers are direct). If safe to promote some arguments, it 862 /// calls the DoPromotion method. 863 static Function * 864 promoteArguments(Function *F, function_ref<AAResults &(Function &F)> AARGetter, 865 unsigned MaxElements, 866 Optional<function_ref<void(CallBase &OldCS, CallBase &NewCS)>> 867 ReplaceCallSite, 868 const TargetTransformInfo &TTI) { 869 // Don't perform argument promotion for naked functions; otherwise we can end 870 // up removing parameters that are seemingly 'not used' as they are referred 871 // to in the assembly. 872 if(F->hasFnAttribute(Attribute::Naked)) 873 return nullptr; 874 875 // Make sure that it is local to this module. 876 if (!F->hasLocalLinkage()) 877 return nullptr; 878 879 // Don't promote arguments for variadic functions. Adding, removing, or 880 // changing non-pack parameters can change the classification of pack 881 // parameters. Frontends encode that classification at the call site in the 882 // IR, while in the callee the classification is determined dynamically based 883 // on the number of registers consumed so far. 884 if (F->isVarArg()) 885 return nullptr; 886 887 // Don't transform functions that receive inallocas, as the transformation may 888 // not be safe depending on calling convention. 889 if (F->getAttributes().hasAttrSomewhere(Attribute::InAlloca)) 890 return nullptr; 891 892 // First check: see if there are any pointer arguments! If not, quick exit. 893 SmallVector<Argument *, 16> PointerArgs; 894 for (Argument &I : F->args()) 895 if (I.getType()->isPointerTy()) 896 PointerArgs.push_back(&I); 897 if (PointerArgs.empty()) 898 return nullptr; 899 900 // Second check: make sure that all callers are direct callers. We can't 901 // transform functions that have indirect callers. Also see if the function 902 // is self-recursive and check that target features are compatible. 903 bool isSelfRecursive = false; 904 for (Use &U : F->uses()) { 905 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 906 // Must be a direct call. 907 if (CB == nullptr || !CB->isCallee(&U)) 908 return nullptr; 909 910 // Can't change signature of musttail callee 911 if (CB->isMustTailCall()) 912 return nullptr; 913 914 if (CB->getParent()->getParent() == F) 915 isSelfRecursive = true; 916 } 917 918 // Can't change signature of musttail caller 919 // FIXME: Support promoting whole chain of musttail functions 920 for (BasicBlock &BB : *F) 921 if (BB.getTerminatingMustTailCall()) 922 return nullptr; 923 924 const DataLayout &DL = F->getParent()->getDataLayout(); 925 926 AAResults &AAR = AARGetter(*F); 927 928 // Check to see which arguments are promotable. If an argument is promotable, 929 // add it to ArgsToPromote. 930 SmallPtrSet<Argument *, 8> ArgsToPromote; 931 SmallPtrSet<Argument *, 8> ByValArgsToTransform; 932 for (Argument *PtrArg : PointerArgs) { 933 Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); 934 935 // Replace sret attribute with noalias. This reduces register pressure by 936 // avoiding a register copy. 937 if (PtrArg->hasStructRetAttr()) { 938 unsigned ArgNo = PtrArg->getArgNo(); 939 F->removeParamAttr(ArgNo, Attribute::StructRet); 940 F->addParamAttr(ArgNo, Attribute::NoAlias); 941 for (Use &U : F->uses()) { 942 CallBase &CB = cast<CallBase>(*U.getUser()); 943 CB.removeParamAttr(ArgNo, Attribute::StructRet); 944 CB.addParamAttr(ArgNo, Attribute::NoAlias); 945 } 946 } 947 948 // If this is a byval argument, and if the aggregate type is small, just 949 // pass the elements, which is always safe, if the passed value is densely 950 // packed or if we can prove the padding bytes are never accessed. 951 bool isSafeToPromote = PtrArg->hasByValAttr() && 952 (ArgumentPromotionPass::isDenselyPacked(AgTy, DL) || 953 !canPaddingBeAccessed(PtrArg)); 954 if (isSafeToPromote) { 955 if (StructType *STy = dyn_cast<StructType>(AgTy)) { 956 if (MaxElements > 0 && STy->getNumElements() > MaxElements) { 957 LLVM_DEBUG(dbgs() << "argpromotion disable promoting argument '" 958 << PtrArg->getName() 959 << "' because it would require adding more" 960 << " than " << MaxElements 961 << " arguments to the function.\n"); 962 continue; 963 } 964 965 // If all the elements are single-value types, we can promote it. 966 bool AllSimple = true; 967 for (const auto *EltTy : STy->elements()) { 968 if (!EltTy->isSingleValueType()) { 969 AllSimple = false; 970 break; 971 } 972 } 973 974 // Safe to transform, don't even bother trying to "promote" it. 975 // Passing the elements as a scalar will allow sroa to hack on 976 // the new alloca we introduce. 977 if (AllSimple) { 978 ByValArgsToTransform.insert(PtrArg); 979 continue; 980 } 981 } 982 } 983 984 // If the argument is a recursive type and we're in a recursive 985 // function, we could end up infinitely peeling the function argument. 986 if (isSelfRecursive) { 987 if (StructType *STy = dyn_cast<StructType>(AgTy)) { 988 bool RecursiveType = false; 989 for (const auto *EltTy : STy->elements()) { 990 if (EltTy == PtrArg->getType()) { 991 RecursiveType = true; 992 break; 993 } 994 } 995 if (RecursiveType) 996 continue; 997 } 998 } 999 1000 // Otherwise, see if we can promote the pointer to its value. 1001 Type *ByValTy = 1002 PtrArg->hasByValAttr() ? PtrArg->getParamByValType() : nullptr; 1003 if (isSafeToPromoteArgument(PtrArg, ByValTy, AAR, MaxElements)) 1004 ArgsToPromote.insert(PtrArg); 1005 } 1006 1007 // No promotable pointer arguments. 1008 if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) 1009 return nullptr; 1010 1011 if (!ArgumentPromotionPass::areFunctionArgsABICompatible( 1012 *F, TTI, ArgsToPromote, ByValArgsToTransform)) 1013 return nullptr; 1014 1015 return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite); 1016 } 1017 1018 PreservedAnalyses ArgumentPromotionPass::run(LazyCallGraph::SCC &C, 1019 CGSCCAnalysisManager &AM, 1020 LazyCallGraph &CG, 1021 CGSCCUpdateResult &UR) { 1022 bool Changed = false, LocalChange; 1023 1024 // Iterate until we stop promoting from this SCC. 1025 do { 1026 LocalChange = false; 1027 1028 for (LazyCallGraph::Node &N : C) { 1029 Function &OldF = N.getFunction(); 1030 1031 FunctionAnalysisManager &FAM = 1032 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); 1033 // FIXME: This lambda must only be used with this function. We should 1034 // skip the lambda and just get the AA results directly. 1035 auto AARGetter = [&](Function &F) -> AAResults & { 1036 assert(&F == &OldF && "Called with an unexpected function!"); 1037 return FAM.getResult<AAManager>(F); 1038 }; 1039 1040 const TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(OldF); 1041 Function *NewF = 1042 promoteArguments(&OldF, AARGetter, MaxElements, None, TTI); 1043 if (!NewF) 1044 continue; 1045 LocalChange = true; 1046 1047 // Directly substitute the functions in the call graph. Note that this 1048 // requires the old function to be completely dead and completely 1049 // replaced by the new function. It does no call graph updates, it merely 1050 // swaps out the particular function mapped to a particular node in the 1051 // graph. 1052 C.getOuterRefSCC().replaceNodeFunction(N, *NewF); 1053 OldF.eraseFromParent(); 1054 } 1055 1056 Changed |= LocalChange; 1057 } while (LocalChange); 1058 1059 if (!Changed) 1060 return PreservedAnalyses::all(); 1061 1062 return PreservedAnalyses::none(); 1063 } 1064 1065 namespace { 1066 1067 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. 1068 struct ArgPromotion : public CallGraphSCCPass { 1069 // Pass identification, replacement for typeid 1070 static char ID; 1071 1072 explicit ArgPromotion(unsigned MaxElements = 3) 1073 : CallGraphSCCPass(ID), MaxElements(MaxElements) { 1074 initializeArgPromotionPass(*PassRegistry::getPassRegistry()); 1075 } 1076 1077 void getAnalysisUsage(AnalysisUsage &AU) const override { 1078 AU.addRequired<AssumptionCacheTracker>(); 1079 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1080 AU.addRequired<TargetTransformInfoWrapperPass>(); 1081 getAAResultsAnalysisUsage(AU); 1082 CallGraphSCCPass::getAnalysisUsage(AU); 1083 } 1084 1085 bool runOnSCC(CallGraphSCC &SCC) override; 1086 1087 private: 1088 using llvm::Pass::doInitialization; 1089 1090 bool doInitialization(CallGraph &CG) override; 1091 1092 /// The maximum number of elements to expand, or 0 for unlimited. 1093 unsigned MaxElements; 1094 }; 1095 1096 } // end anonymous namespace 1097 1098 char ArgPromotion::ID = 0; 1099 1100 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion", 1101 "Promote 'by reference' arguments to scalars", false, 1102 false) 1103 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1104 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 1105 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 1106 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 1107 INITIALIZE_PASS_END(ArgPromotion, "argpromotion", 1108 "Promote 'by reference' arguments to scalars", false, false) 1109 1110 Pass *llvm::createArgumentPromotionPass(unsigned MaxElements) { 1111 return new ArgPromotion(MaxElements); 1112 } 1113 1114 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) { 1115 if (skipSCC(SCC)) 1116 return false; 1117 1118 // Get the callgraph information that we need to update to reflect our 1119 // changes. 1120 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 1121 1122 LegacyAARGetter AARGetter(*this); 1123 1124 bool Changed = false, LocalChange; 1125 1126 // Iterate until we stop promoting from this SCC. 1127 do { 1128 LocalChange = false; 1129 // Attempt to promote arguments from all functions in this SCC. 1130 for (CallGraphNode *OldNode : SCC) { 1131 Function *OldF = OldNode->getFunction(); 1132 if (!OldF) 1133 continue; 1134 1135 auto ReplaceCallSite = [&](CallBase &OldCS, CallBase &NewCS) { 1136 Function *Caller = OldCS.getParent()->getParent(); 1137 CallGraphNode *NewCalleeNode = 1138 CG.getOrInsertFunction(NewCS.getCalledFunction()); 1139 CallGraphNode *CallerNode = CG[Caller]; 1140 CallerNode->replaceCallEdge(cast<CallBase>(OldCS), 1141 cast<CallBase>(NewCS), NewCalleeNode); 1142 }; 1143 1144 const TargetTransformInfo &TTI = 1145 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*OldF); 1146 if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements, 1147 {ReplaceCallSite}, TTI)) { 1148 LocalChange = true; 1149 1150 // Update the call graph for the newly promoted function. 1151 CallGraphNode *NewNode = CG.getOrInsertFunction(NewF); 1152 NewNode->stealCalledFunctionsFrom(OldNode); 1153 if (OldNode->getNumReferences() == 0) 1154 delete CG.removeFunctionFromModule(OldNode); 1155 else 1156 OldF->setLinkage(Function::ExternalLinkage); 1157 1158 // And updat ethe SCC we're iterating as well. 1159 SCC.ReplaceNode(OldNode, NewNode); 1160 } 1161 } 1162 // Remember that we changed something. 1163 Changed |= LocalChange; 1164 } while (LocalChange); 1165 1166 return Changed; 1167 } 1168 1169 bool ArgPromotion::doInitialization(CallGraph &CG) { 1170 return CallGraphSCCPass::doInitialization(CG); 1171 } 1172