1 //===-- ArgumentPromotion.cpp - Promote by-reference arguments ------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass promotes "by reference" arguments to be "by value" arguments. In 11 // practice, this means looking for internal functions that have pointer 12 // arguments. If it can prove, through the use of alias analysis, that an 13 // argument is *only* loaded, then it can pass the value into the function 14 // instead of the address of the value. This can cause recursive simplification 15 // of code and lead to the elimination of allocas (especially in C++ template 16 // code like the STL). 17 // 18 // This pass also handles aggregate arguments that are passed into a function, 19 // scalarizing them if the elements of the aggregate are only loaded. Note that 20 // by default it refuses to scalarize aggregates which would require passing in 21 // more than three operands to the function, because passing thousands of 22 // operands for a large array or structure is unprofitable! This limit can be 23 // configured or disabled, however. 24 // 25 // Note that this transformation could also be done for arguments that are only 26 // stored to (returning the value instead), but does not currently. This case 27 // would be best handled when and if LLVM begins supporting multiple return 28 // values from functions. 29 // 30 //===----------------------------------------------------------------------===// 31 32 #include "llvm/Transforms/IPO.h" 33 #include "llvm/ADT/DepthFirstIterator.h" 34 #include "llvm/ADT/Statistic.h" 35 #include "llvm/ADT/StringExtras.h" 36 #include "llvm/Analysis/AliasAnalysis.h" 37 #include "llvm/Analysis/CallGraph.h" 38 #include "llvm/Analysis/CallGraphSCCPass.h" 39 #include "llvm/IR/CFG.h" 40 #include "llvm/IR/CallSite.h" 41 #include "llvm/IR/Constants.h" 42 #include "llvm/IR/DataLayout.h" 43 #include "llvm/IR/DebugInfo.h" 44 #include "llvm/IR/DerivedTypes.h" 45 #include "llvm/IR/Instructions.h" 46 #include "llvm/IR/LLVMContext.h" 47 #include "llvm/IR/Module.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include <set> 51 using namespace llvm; 52 53 #define DEBUG_TYPE "argpromotion" 54 55 STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted"); 56 STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted"); 57 STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted"); 58 STATISTIC(NumArgumentsDead , "Number of dead pointer args eliminated"); 59 60 namespace { 61 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. 62 /// 63 struct ArgPromotion : public CallGraphSCCPass { 64 void getAnalysisUsage(AnalysisUsage &AU) const override { 65 AU.addRequired<AliasAnalysis>(); 66 CallGraphSCCPass::getAnalysisUsage(AU); 67 } 68 69 bool runOnSCC(CallGraphSCC &SCC) override; 70 static char ID; // Pass identification, replacement for typeid 71 explicit ArgPromotion(unsigned maxElements = 3) 72 : CallGraphSCCPass(ID), DL(nullptr), maxElements(maxElements) { 73 initializeArgPromotionPass(*PassRegistry::getPassRegistry()); 74 } 75 76 /// A vector used to hold the indices of a single GEP instruction 77 typedef std::vector<uint64_t> IndicesVector; 78 79 const DataLayout *DL; 80 private: 81 CallGraphNode *PromoteArguments(CallGraphNode *CGN); 82 bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const; 83 CallGraphNode *DoPromotion(Function *F, 84 SmallPtrSet<Argument*, 8> &ArgsToPromote, 85 SmallPtrSet<Argument*, 8> &ByValArgsToTransform); 86 bool doInitialization(CallGraph &CG) override; 87 /// The maximum number of elements to expand, or 0 for unlimited. 88 unsigned maxElements; 89 DenseMap<const Function *, DISubprogram> FunctionDIs; 90 }; 91 } 92 93 char ArgPromotion::ID = 0; 94 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion", 95 "Promote 'by reference' arguments to scalars", false, false) 96 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 97 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 98 INITIALIZE_PASS_END(ArgPromotion, "argpromotion", 99 "Promote 'by reference' arguments to scalars", false, false) 100 101 Pass *llvm::createArgumentPromotionPass(unsigned maxElements) { 102 return new ArgPromotion(maxElements); 103 } 104 105 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) { 106 bool Changed = false, LocalChange; 107 108 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 109 DL = DLP ? &DLP->getDataLayout() : nullptr; 110 111 do { // Iterate until we stop promoting from this SCC. 112 LocalChange = false; 113 // Attempt to promote arguments from all functions in this SCC. 114 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 115 if (CallGraphNode *CGN = PromoteArguments(*I)) { 116 LocalChange = true; 117 SCC.ReplaceNode(*I, CGN); 118 } 119 } 120 Changed |= LocalChange; // Remember that we changed something. 121 } while (LocalChange); 122 123 return Changed; 124 } 125 126 /// PromoteArguments - This method checks the specified function to see if there 127 /// are any promotable arguments and if it is safe to promote the function (for 128 /// example, all callers are direct). If safe to promote some arguments, it 129 /// calls the DoPromotion method. 130 /// 131 CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) { 132 Function *F = CGN->getFunction(); 133 134 // Make sure that it is local to this module. 135 if (!F || !F->hasLocalLinkage()) return nullptr; 136 137 // First check: see if there are any pointer arguments! If not, quick exit. 138 SmallVector<Argument*, 16> PointerArgs; 139 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) 140 if (I->getType()->isPointerTy()) 141 PointerArgs.push_back(I); 142 if (PointerArgs.empty()) return nullptr; 143 144 // Second check: make sure that all callers are direct callers. We can't 145 // transform functions that have indirect callers. Also see if the function 146 // is self-recursive. 147 bool isSelfRecursive = false; 148 for (Use &U : F->uses()) { 149 CallSite CS(U.getUser()); 150 // Must be a direct call. 151 if (CS.getInstruction() == nullptr || !CS.isCallee(&U)) return nullptr; 152 153 if (CS.getInstruction()->getParent()->getParent() == F) 154 isSelfRecursive = true; 155 } 156 157 // Check to see which arguments are promotable. If an argument is promotable, 158 // add it to ArgsToPromote. 159 SmallPtrSet<Argument*, 8> ArgsToPromote; 160 SmallPtrSet<Argument*, 8> ByValArgsToTransform; 161 for (unsigned i = 0, e = PointerArgs.size(); i != e; ++i) { 162 Argument *PtrArg = PointerArgs[i]; 163 Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); 164 165 // If this is a byval argument, and if the aggregate type is small, just 166 // pass the elements, which is always safe. This does not apply to 167 // inalloca. 168 if (PtrArg->hasByValAttr()) { 169 if (StructType *STy = dyn_cast<StructType>(AgTy)) { 170 if (maxElements > 0 && STy->getNumElements() > maxElements) { 171 DEBUG(dbgs() << "argpromotion disable promoting argument '" 172 << PtrArg->getName() << "' because it would require adding more" 173 << " than " << maxElements << " arguments to the function.\n"); 174 continue; 175 } 176 177 // If all the elements are single-value types, we can promote it. 178 bool AllSimple = true; 179 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 180 if (!STy->getElementType(i)->isSingleValueType()) { 181 AllSimple = false; 182 break; 183 } 184 } 185 186 // Safe to transform, don't even bother trying to "promote" it. 187 // Passing the elements as a scalar will allow scalarrepl to hack on 188 // the new alloca we introduce. 189 if (AllSimple) { 190 ByValArgsToTransform.insert(PtrArg); 191 continue; 192 } 193 } 194 } 195 196 // If the argument is a recursive type and we're in a recursive 197 // function, we could end up infinitely peeling the function argument. 198 if (isSelfRecursive) { 199 if (StructType *STy = dyn_cast<StructType>(AgTy)) { 200 bool RecursiveType = false; 201 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 202 if (STy->getElementType(i) == PtrArg->getType()) { 203 RecursiveType = true; 204 break; 205 } 206 } 207 if (RecursiveType) 208 continue; 209 } 210 } 211 212 // Otherwise, see if we can promote the pointer to its value. 213 if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr())) 214 ArgsToPromote.insert(PtrArg); 215 } 216 217 // No promotable pointer arguments. 218 if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) 219 return nullptr; 220 221 return DoPromotion(F, ArgsToPromote, ByValArgsToTransform); 222 } 223 224 /// AllCallersPassInValidPointerForArgument - Return true if we can prove that 225 /// all callees pass in a valid pointer for the specified function argument. 226 static bool AllCallersPassInValidPointerForArgument(Argument *Arg, 227 const DataLayout *DL) { 228 Function *Callee = Arg->getParent(); 229 230 unsigned ArgNo = Arg->getArgNo(); 231 232 // Look at all call sites of the function. At this pointer we know we only 233 // have direct callees. 234 for (User *U : Callee->users()) { 235 CallSite CS(U); 236 assert(CS && "Should only have direct calls!"); 237 238 if (!CS.getArgument(ArgNo)->isDereferenceablePointer(DL)) 239 return false; 240 } 241 return true; 242 } 243 244 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size 245 /// that is greater than or equal to the size of prefix, and each of the 246 /// elements in Prefix is the same as the corresponding elements in Longer. 247 /// 248 /// This means it also returns true when Prefix and Longer are equal! 249 static bool IsPrefix(const ArgPromotion::IndicesVector &Prefix, 250 const ArgPromotion::IndicesVector &Longer) { 251 if (Prefix.size() > Longer.size()) 252 return false; 253 return std::equal(Prefix.begin(), Prefix.end(), Longer.begin()); 254 } 255 256 257 /// Checks if Indices, or a prefix of Indices, is in Set. 258 static bool PrefixIn(const ArgPromotion::IndicesVector &Indices, 259 std::set<ArgPromotion::IndicesVector> &Set) { 260 std::set<ArgPromotion::IndicesVector>::iterator Low; 261 Low = Set.upper_bound(Indices); 262 if (Low != Set.begin()) 263 Low--; 264 // Low is now the last element smaller than or equal to Indices. This means 265 // it points to a prefix of Indices (possibly Indices itself), if such 266 // prefix exists. 267 // 268 // This load is safe if any prefix of its operands is safe to load. 269 return Low != Set.end() && IsPrefix(*Low, Indices); 270 } 271 272 /// Mark the given indices (ToMark) as safe in the given set of indices 273 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there 274 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe 275 /// already. Furthermore, any indices that Indices is itself a prefix of, are 276 /// removed from Safe (since they are implicitely safe because of Indices now). 277 static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark, 278 std::set<ArgPromotion::IndicesVector> &Safe) { 279 std::set<ArgPromotion::IndicesVector>::iterator Low; 280 Low = Safe.upper_bound(ToMark); 281 // Guard against the case where Safe is empty 282 if (Low != Safe.begin()) 283 Low--; 284 // Low is now the last element smaller than or equal to Indices. This 285 // means it points to a prefix of Indices (possibly Indices itself), if 286 // such prefix exists. 287 if (Low != Safe.end()) { 288 if (IsPrefix(*Low, ToMark)) 289 // If there is already a prefix of these indices (or exactly these 290 // indices) marked a safe, don't bother adding these indices 291 return; 292 293 // Increment Low, so we can use it as a "insert before" hint 294 ++Low; 295 } 296 // Insert 297 Low = Safe.insert(Low, ToMark); 298 ++Low; 299 // If there we're a prefix of longer index list(s), remove those 300 std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end(); 301 while (Low != End && IsPrefix(ToMark, *Low)) { 302 std::set<ArgPromotion::IndicesVector>::iterator Remove = Low; 303 ++Low; 304 Safe.erase(Remove); 305 } 306 } 307 308 /// isSafeToPromoteArgument - As you might guess from the name of this method, 309 /// it checks to see if it is both safe and useful to promote the argument. 310 /// This method limits promotion of aggregates to only promote up to three 311 /// elements of the aggregate in order to avoid exploding the number of 312 /// arguments passed in. 313 bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, 314 bool isByValOrInAlloca) const { 315 typedef std::set<IndicesVector> GEPIndicesSet; 316 317 // Quick exit for unused arguments 318 if (Arg->use_empty()) 319 return true; 320 321 // We can only promote this argument if all of the uses are loads, or are GEP 322 // instructions (with constant indices) that are subsequently loaded. 323 // 324 // Promoting the argument causes it to be loaded in the caller 325 // unconditionally. This is only safe if we can prove that either the load 326 // would have happened in the callee anyway (ie, there is a load in the entry 327 // block) or the pointer passed in at every call site is guaranteed to be 328 // valid. 329 // In the former case, invalid loads can happen, but would have happened 330 // anyway, in the latter case, invalid loads won't happen. This prevents us 331 // from introducing an invalid load that wouldn't have happened in the 332 // original code. 333 // 334 // This set will contain all sets of indices that are loaded in the entry 335 // block, and thus are safe to unconditionally load in the caller. 336 // 337 // This optimization is also safe for InAlloca parameters, because it verifies 338 // that the address isn't captured. 339 GEPIndicesSet SafeToUnconditionallyLoad; 340 341 // This set contains all the sets of indices that we are planning to promote. 342 // This makes it possible to limit the number of arguments added. 343 GEPIndicesSet ToPromote; 344 345 // If the pointer is always valid, any load with first index 0 is valid. 346 if (isByValOrInAlloca || AllCallersPassInValidPointerForArgument(Arg, DL)) 347 SafeToUnconditionallyLoad.insert(IndicesVector(1, 0)); 348 349 // First, iterate the entry block and mark loads of (geps of) arguments as 350 // safe. 351 BasicBlock *EntryBlock = Arg->getParent()->begin(); 352 // Declare this here so we can reuse it 353 IndicesVector Indices; 354 for (BasicBlock::iterator I = EntryBlock->begin(), E = EntryBlock->end(); 355 I != E; ++I) 356 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 357 Value *V = LI->getPointerOperand(); 358 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) { 359 V = GEP->getPointerOperand(); 360 if (V == Arg) { 361 // This load actually loads (part of) Arg? Check the indices then. 362 Indices.reserve(GEP->getNumIndices()); 363 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 364 II != IE; ++II) 365 if (ConstantInt *CI = dyn_cast<ConstantInt>(*II)) 366 Indices.push_back(CI->getSExtValue()); 367 else 368 // We found a non-constant GEP index for this argument? Bail out 369 // right away, can't promote this argument at all. 370 return false; 371 372 // Indices checked out, mark them as safe 373 MarkIndicesSafe(Indices, SafeToUnconditionallyLoad); 374 Indices.clear(); 375 } 376 } else if (V == Arg) { 377 // Direct loads are equivalent to a GEP with a single 0 index. 378 MarkIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad); 379 } 380 } 381 382 // Now, iterate all uses of the argument to see if there are any uses that are 383 // not (GEP+)loads, or any (GEP+)loads that are not safe to promote. 384 SmallVector<LoadInst*, 16> Loads; 385 IndicesVector Operands; 386 for (Use &U : Arg->uses()) { 387 User *UR = U.getUser(); 388 Operands.clear(); 389 if (LoadInst *LI = dyn_cast<LoadInst>(UR)) { 390 // Don't hack volatile/atomic loads 391 if (!LI->isSimple()) return false; 392 Loads.push_back(LI); 393 // Direct loads are equivalent to a GEP with a zero index and then a load. 394 Operands.push_back(0); 395 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) { 396 if (GEP->use_empty()) { 397 // Dead GEP's cause trouble later. Just remove them if we run into 398 // them. 399 getAnalysis<AliasAnalysis>().deleteValue(GEP); 400 GEP->eraseFromParent(); 401 // TODO: This runs the above loop over and over again for dead GEPs 402 // Couldn't we just do increment the UI iterator earlier and erase the 403 // use? 404 return isSafeToPromoteArgument(Arg, isByValOrInAlloca); 405 } 406 407 // Ensure that all of the indices are constants. 408 for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); 409 i != e; ++i) 410 if (ConstantInt *C = dyn_cast<ConstantInt>(*i)) 411 Operands.push_back(C->getSExtValue()); 412 else 413 return false; // Not a constant operand GEP! 414 415 // Ensure that the only users of the GEP are load instructions. 416 for (User *GEPU : GEP->users()) 417 if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) { 418 // Don't hack volatile/atomic loads 419 if (!LI->isSimple()) return false; 420 Loads.push_back(LI); 421 } else { 422 // Other uses than load? 423 return false; 424 } 425 } else { 426 return false; // Not a load or a GEP. 427 } 428 429 // Now, see if it is safe to promote this load / loads of this GEP. Loading 430 // is safe if Operands, or a prefix of Operands, is marked as safe. 431 if (!PrefixIn(Operands, SafeToUnconditionallyLoad)) 432 return false; 433 434 // See if we are already promoting a load with these indices. If not, check 435 // to make sure that we aren't promoting too many elements. If so, nothing 436 // to do. 437 if (ToPromote.find(Operands) == ToPromote.end()) { 438 if (maxElements > 0 && ToPromote.size() == maxElements) { 439 DEBUG(dbgs() << "argpromotion not promoting argument '" 440 << Arg->getName() << "' because it would require adding more " 441 << "than " << maxElements << " arguments to the function.\n"); 442 // We limit aggregate promotion to only promoting up to a fixed number 443 // of elements of the aggregate. 444 return false; 445 } 446 ToPromote.insert(Operands); 447 } 448 } 449 450 if (Loads.empty()) return true; // No users, this is a dead argument. 451 452 // Okay, now we know that the argument is only used by load instructions and 453 // it is safe to unconditionally perform all of them. Use alias analysis to 454 // check to see if the pointer is guaranteed to not be modified from entry of 455 // the function to each of the load instructions. 456 457 // Because there could be several/many load instructions, remember which 458 // blocks we know to be transparent to the load. 459 SmallPtrSet<BasicBlock*, 16> TranspBlocks; 460 461 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 462 463 for (unsigned i = 0, e = Loads.size(); i != e; ++i) { 464 // Check to see if the load is invalidated from the start of the block to 465 // the load itself. 466 LoadInst *Load = Loads[i]; 467 BasicBlock *BB = Load->getParent(); 468 469 AliasAnalysis::Location Loc = AA.getLocation(Load); 470 if (AA.canInstructionRangeModify(BB->front(), *Load, Loc)) 471 return false; // Pointer is invalidated! 472 473 // Now check every path from the entry block to the load for transparency. 474 // To do this, we perform a depth first search on the inverse CFG from the 475 // loading block. 476 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 477 BasicBlock *P = *PI; 478 for (idf_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 16> > 479 I = idf_ext_begin(P, TranspBlocks), 480 E = idf_ext_end(P, TranspBlocks); I != E; ++I) 481 if (AA.canBasicBlockModify(**I, Loc)) 482 return false; 483 } 484 } 485 486 // If the path from the entry of the function to each load is free of 487 // instructions that potentially invalidate the load, we can make the 488 // transformation! 489 return true; 490 } 491 492 /// DoPromotion - This method actually performs the promotion of the specified 493 /// arguments, and returns the new function. At this point, we know that it's 494 /// safe to do so. 495 CallGraphNode *ArgPromotion::DoPromotion(Function *F, 496 SmallPtrSet<Argument*, 8> &ArgsToPromote, 497 SmallPtrSet<Argument*, 8> &ByValArgsToTransform) { 498 499 // Start by computing a new prototype for the function, which is the same as 500 // the old function, but has modified arguments. 501 FunctionType *FTy = F->getFunctionType(); 502 std::vector<Type*> Params; 503 504 typedef std::set<IndicesVector> ScalarizeTable; 505 506 // ScalarizedElements - If we are promoting a pointer that has elements 507 // accessed out of it, keep track of which elements are accessed so that we 508 // can add one argument for each. 509 // 510 // Arguments that are directly loaded will have a zero element value here, to 511 // handle cases where there are both a direct load and GEP accesses. 512 // 513 std::map<Argument*, ScalarizeTable> ScalarizedElements; 514 515 // OriginalLoads - Keep track of a representative load instruction from the 516 // original function so that we can tell the alias analysis implementation 517 // what the new GEP/Load instructions we are inserting look like. 518 // We need to keep the original loads for each argument and the elements 519 // of the argument that are accessed. 520 std::map<std::pair<Argument*, IndicesVector>, LoadInst*> OriginalLoads; 521 522 // Attribute - Keep track of the parameter attributes for the arguments 523 // that we are *not* promoting. For the ones that we do promote, the parameter 524 // attributes are lost 525 SmallVector<AttributeSet, 8> AttributesVec; 526 const AttributeSet &PAL = F->getAttributes(); 527 528 // Add any return attributes. 529 if (PAL.hasAttributes(AttributeSet::ReturnIndex)) 530 AttributesVec.push_back(AttributeSet::get(F->getContext(), 531 PAL.getRetAttributes())); 532 533 // First, determine the new argument list 534 unsigned ArgIndex = 1; 535 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 536 ++I, ++ArgIndex) { 537 if (ByValArgsToTransform.count(I)) { 538 // Simple byval argument? Just add all the struct element types. 539 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 540 StructType *STy = cast<StructType>(AgTy); 541 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 542 Params.push_back(STy->getElementType(i)); 543 ++NumByValArgsPromoted; 544 } else if (!ArgsToPromote.count(I)) { 545 // Unchanged argument 546 Params.push_back(I->getType()); 547 AttributeSet attrs = PAL.getParamAttributes(ArgIndex); 548 if (attrs.hasAttributes(ArgIndex)) { 549 AttrBuilder B(attrs, ArgIndex); 550 AttributesVec. 551 push_back(AttributeSet::get(F->getContext(), Params.size(), B)); 552 } 553 } else if (I->use_empty()) { 554 // Dead argument (which are always marked as promotable) 555 ++NumArgumentsDead; 556 } else { 557 // Okay, this is being promoted. This means that the only uses are loads 558 // or GEPs which are only used by loads 559 560 // In this table, we will track which indices are loaded from the argument 561 // (where direct loads are tracked as no indices). 562 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 563 for (User *U : I->users()) { 564 Instruction *UI = cast<Instruction>(U); 565 assert(isa<LoadInst>(UI) || isa<GetElementPtrInst>(UI)); 566 IndicesVector Indices; 567 Indices.reserve(UI->getNumOperands() - 1); 568 // Since loads will only have a single operand, and GEPs only a single 569 // non-index operand, this will record direct loads without any indices, 570 // and gep+loads with the GEP indices. 571 for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end(); 572 II != IE; ++II) 573 Indices.push_back(cast<ConstantInt>(*II)->getSExtValue()); 574 // GEPs with a single 0 index can be merged with direct loads 575 if (Indices.size() == 1 && Indices.front() == 0) 576 Indices.clear(); 577 ArgIndices.insert(Indices); 578 LoadInst *OrigLoad; 579 if (LoadInst *L = dyn_cast<LoadInst>(UI)) 580 OrigLoad = L; 581 else 582 // Take any load, we will use it only to update Alias Analysis 583 OrigLoad = cast<LoadInst>(UI->user_back()); 584 OriginalLoads[std::make_pair(I, Indices)] = OrigLoad; 585 } 586 587 // Add a parameter to the function for each element passed in. 588 for (ScalarizeTable::iterator SI = ArgIndices.begin(), 589 E = ArgIndices.end(); SI != E; ++SI) { 590 // not allowed to dereference ->begin() if size() is 0 591 Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), *SI)); 592 assert(Params.back()); 593 } 594 595 if (ArgIndices.size() == 1 && ArgIndices.begin()->empty()) 596 ++NumArgumentsPromoted; 597 else 598 ++NumAggregatesPromoted; 599 } 600 } 601 602 // Add any function attributes. 603 if (PAL.hasAttributes(AttributeSet::FunctionIndex)) 604 AttributesVec.push_back(AttributeSet::get(FTy->getContext(), 605 PAL.getFnAttributes())); 606 607 Type *RetTy = FTy->getReturnType(); 608 609 // Construct the new function type using the new arguments. 610 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 611 612 // Create the new function body and insert it into the module. 613 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName()); 614 NF->copyAttributesFrom(F); 615 616 // Patch the pointer to LLVM function in debug info descriptor. 617 auto DI = FunctionDIs.find(F); 618 if (DI != FunctionDIs.end()) 619 DI->second.replaceFunction(NF); 620 621 DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n" 622 << "From: " << *F); 623 624 // Recompute the parameter attributes list based on the new arguments for 625 // the function. 626 NF->setAttributes(AttributeSet::get(F->getContext(), AttributesVec)); 627 AttributesVec.clear(); 628 629 F->getParent()->getFunctionList().insert(F, NF); 630 NF->takeName(F); 631 632 // Get the alias analysis information that we need to update to reflect our 633 // changes. 634 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 635 636 // Get the callgraph information that we need to update to reflect our 637 // changes. 638 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 639 640 // Get a new callgraph node for NF. 641 CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF); 642 643 // Loop over all of the callers of the function, transforming the call sites 644 // to pass in the loaded pointers. 645 // 646 SmallVector<Value*, 16> Args; 647 while (!F->use_empty()) { 648 CallSite CS(F->user_back()); 649 assert(CS.getCalledFunction() == F); 650 Instruction *Call = CS.getInstruction(); 651 const AttributeSet &CallPAL = CS.getAttributes(); 652 653 // Add any return attributes. 654 if (CallPAL.hasAttributes(AttributeSet::ReturnIndex)) 655 AttributesVec.push_back(AttributeSet::get(F->getContext(), 656 CallPAL.getRetAttributes())); 657 658 // Loop over the operands, inserting GEP and loads in the caller as 659 // appropriate. 660 CallSite::arg_iterator AI = CS.arg_begin(); 661 ArgIndex = 1; 662 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 663 I != E; ++I, ++AI, ++ArgIndex) 664 if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { 665 Args.push_back(*AI); // Unmodified argument 666 667 if (CallPAL.hasAttributes(ArgIndex)) { 668 AttrBuilder B(CallPAL, ArgIndex); 669 AttributesVec. 670 push_back(AttributeSet::get(F->getContext(), Args.size(), B)); 671 } 672 } else if (ByValArgsToTransform.count(I)) { 673 // Emit a GEP and load for each element of the struct. 674 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 675 StructType *STy = cast<StructType>(AgTy); 676 Value *Idxs[2] = { 677 ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr }; 678 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 679 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 680 Value *Idx = GetElementPtrInst::Create(*AI, Idxs, 681 (*AI)->getName()+"."+utostr(i), 682 Call); 683 // TODO: Tell AA about the new values? 684 Args.push_back(new LoadInst(Idx, Idx->getName()+".val", Call)); 685 } 686 } else if (!I->use_empty()) { 687 // Non-dead argument: insert GEPs and loads as appropriate. 688 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 689 // Store the Value* version of the indices in here, but declare it now 690 // for reuse. 691 std::vector<Value*> Ops; 692 for (ScalarizeTable::iterator SI = ArgIndices.begin(), 693 E = ArgIndices.end(); SI != E; ++SI) { 694 Value *V = *AI; 695 LoadInst *OrigLoad = OriginalLoads[std::make_pair(I, *SI)]; 696 if (!SI->empty()) { 697 Ops.reserve(SI->size()); 698 Type *ElTy = V->getType(); 699 for (IndicesVector::const_iterator II = SI->begin(), 700 IE = SI->end(); II != IE; ++II) { 701 // Use i32 to index structs, and i64 for others (pointers/arrays). 702 // This satisfies GEP constraints. 703 Type *IdxTy = (ElTy->isStructTy() ? 704 Type::getInt32Ty(F->getContext()) : 705 Type::getInt64Ty(F->getContext())); 706 Ops.push_back(ConstantInt::get(IdxTy, *II)); 707 // Keep track of the type we're currently indexing. 708 ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II); 709 } 710 // And create a GEP to extract those indices. 711 V = GetElementPtrInst::Create(V, Ops, V->getName()+".idx", Call); 712 Ops.clear(); 713 AA.copyValue(OrigLoad->getOperand(0), V); 714 } 715 // Since we're replacing a load make sure we take the alignment 716 // of the previous load. 717 LoadInst *newLoad = new LoadInst(V, V->getName()+".val", Call); 718 newLoad->setAlignment(OrigLoad->getAlignment()); 719 // Transfer the TBAA info too. 720 newLoad->setMetadata(LLVMContext::MD_tbaa, 721 OrigLoad->getMetadata(LLVMContext::MD_tbaa)); 722 Args.push_back(newLoad); 723 AA.copyValue(OrigLoad, Args.back()); 724 } 725 } 726 727 // Push any varargs arguments on the list. 728 for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { 729 Args.push_back(*AI); 730 if (CallPAL.hasAttributes(ArgIndex)) { 731 AttrBuilder B(CallPAL, ArgIndex); 732 AttributesVec. 733 push_back(AttributeSet::get(F->getContext(), Args.size(), B)); 734 } 735 } 736 737 // Add any function attributes. 738 if (CallPAL.hasAttributes(AttributeSet::FunctionIndex)) 739 AttributesVec.push_back(AttributeSet::get(Call->getContext(), 740 CallPAL.getFnAttributes())); 741 742 Instruction *New; 743 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 744 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 745 Args, "", Call); 746 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 747 cast<InvokeInst>(New)->setAttributes(AttributeSet::get(II->getContext(), 748 AttributesVec)); 749 } else { 750 New = CallInst::Create(NF, Args, "", Call); 751 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 752 cast<CallInst>(New)->setAttributes(AttributeSet::get(New->getContext(), 753 AttributesVec)); 754 if (cast<CallInst>(Call)->isTailCall()) 755 cast<CallInst>(New)->setTailCall(); 756 } 757 New->setDebugLoc(Call->getDebugLoc()); 758 Args.clear(); 759 AttributesVec.clear(); 760 761 // Update the alias analysis implementation to know that we are replacing 762 // the old call with a new one. 763 AA.replaceWithNewValue(Call, New); 764 765 // Update the callgraph to know that the callsite has been transformed. 766 CallGraphNode *CalleeNode = CG[Call->getParent()->getParent()]; 767 CalleeNode->replaceCallEdge(Call, New, NF_CGN); 768 769 if (!Call->use_empty()) { 770 Call->replaceAllUsesWith(New); 771 New->takeName(Call); 772 } 773 774 // Finally, remove the old call from the program, reducing the use-count of 775 // F. 776 Call->eraseFromParent(); 777 } 778 779 // Since we have now created the new function, splice the body of the old 780 // function right into the new function, leaving the old rotting hulk of the 781 // function empty. 782 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 783 784 // Loop over the argument list, transferring uses of the old arguments over to 785 // the new arguments, also transferring over the names as well. 786 // 787 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 788 I2 = NF->arg_begin(); I != E; ++I) { 789 if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { 790 // If this is an unmodified argument, move the name and users over to the 791 // new version. 792 I->replaceAllUsesWith(I2); 793 I2->takeName(I); 794 AA.replaceWithNewValue(I, I2); 795 ++I2; 796 continue; 797 } 798 799 if (ByValArgsToTransform.count(I)) { 800 // In the callee, we create an alloca, and store each of the new incoming 801 // arguments into the alloca. 802 Instruction *InsertPt = NF->begin()->begin(); 803 804 // Just add all the struct element types. 805 Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 806 Value *TheAlloca = new AllocaInst(AgTy, nullptr, "", InsertPt); 807 StructType *STy = cast<StructType>(AgTy); 808 Value *Idxs[2] = { 809 ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr }; 810 811 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 812 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 813 Value *Idx = 814 GetElementPtrInst::Create(TheAlloca, Idxs, 815 TheAlloca->getName()+"."+Twine(i), 816 InsertPt); 817 I2->setName(I->getName()+"."+Twine(i)); 818 new StoreInst(I2++, Idx, InsertPt); 819 } 820 821 // Anything that used the arg should now use the alloca. 822 I->replaceAllUsesWith(TheAlloca); 823 TheAlloca->takeName(I); 824 AA.replaceWithNewValue(I, TheAlloca); 825 826 // If the alloca is used in a call, we must clear the tail flag since 827 // the callee now uses an alloca from the caller. 828 for (User *U : TheAlloca->users()) { 829 CallInst *Call = dyn_cast<CallInst>(U); 830 if (!Call) 831 continue; 832 Call->setTailCall(false); 833 } 834 continue; 835 } 836 837 if (I->use_empty()) { 838 AA.deleteValue(I); 839 continue; 840 } 841 842 // Otherwise, if we promoted this argument, then all users are load 843 // instructions (or GEPs with only load users), and all loads should be 844 // using the new argument that we added. 845 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 846 847 while (!I->use_empty()) { 848 if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) { 849 assert(ArgIndices.begin()->empty() && 850 "Load element should sort to front!"); 851 I2->setName(I->getName()+".val"); 852 LI->replaceAllUsesWith(I2); 853 AA.replaceWithNewValue(LI, I2); 854 LI->eraseFromParent(); 855 DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName() 856 << "' in function '" << F->getName() << "'\n"); 857 } else { 858 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back()); 859 IndicesVector Operands; 860 Operands.reserve(GEP->getNumIndices()); 861 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 862 II != IE; ++II) 863 Operands.push_back(cast<ConstantInt>(*II)->getSExtValue()); 864 865 // GEPs with a single 0 index can be merged with direct loads 866 if (Operands.size() == 1 && Operands.front() == 0) 867 Operands.clear(); 868 869 Function::arg_iterator TheArg = I2; 870 for (ScalarizeTable::iterator It = ArgIndices.begin(); 871 *It != Operands; ++It, ++TheArg) { 872 assert(It != ArgIndices.end() && "GEP not handled??"); 873 } 874 875 std::string NewName = I->getName(); 876 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 877 NewName += "." + utostr(Operands[i]); 878 } 879 NewName += ".val"; 880 TheArg->setName(NewName); 881 882 DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName() 883 << "' of function '" << NF->getName() << "'\n"); 884 885 // All of the uses must be load instructions. Replace them all with 886 // the argument specified by ArgNo. 887 while (!GEP->use_empty()) { 888 LoadInst *L = cast<LoadInst>(GEP->user_back()); 889 L->replaceAllUsesWith(TheArg); 890 AA.replaceWithNewValue(L, TheArg); 891 L->eraseFromParent(); 892 } 893 AA.deleteValue(GEP); 894 GEP->eraseFromParent(); 895 } 896 } 897 898 // Increment I2 past all of the arguments added for this promoted pointer. 899 std::advance(I2, ArgIndices.size()); 900 } 901 902 // Tell the alias analysis that the old function is about to disappear. 903 AA.replaceWithNewValue(F, NF); 904 905 906 NF_CGN->stealCalledFunctionsFrom(CG[F]); 907 908 // Now that the old function is dead, delete it. If there is a dangling 909 // reference to the CallgraphNode, just leave the dead function around for 910 // someone else to nuke. 911 CallGraphNode *CGN = CG[F]; 912 if (CGN->getNumReferences() == 0) 913 delete CG.removeFunctionFromModule(CGN); 914 else 915 F->setLinkage(Function::ExternalLinkage); 916 917 return NF_CGN; 918 } 919 920 bool ArgPromotion::doInitialization(CallGraph &CG) { 921 FunctionDIs = makeSubprogramMap(CG.getModule()); 922 return CallGraphSCCPass::doInitialization(CG); 923 } 924