1 //===- DeadArgumentElimination.cpp - Eliminate dead 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 deletes dead arguments from internal functions. Dead argument 11 // elimination removes arguments which are directly dead, as well as arguments 12 // only passed into function calls as dead arguments of other functions. This 13 // pass also deletes dead return values in a similar way. 14 // 15 // This pass is often useful as a cleanup pass to run after aggressive 16 // interprocedural passes, which add possibly-dead arguments or return values. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/Transforms/IPO/DeadArgumentElimination.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/IR/Argument.h" 24 #include "llvm/IR/Attributes.h" 25 #include "llvm/IR/BasicBlock.h" 26 #include "llvm/IR/CallSite.h" 27 #include "llvm/IR/Constant.h" 28 #include "llvm/IR/Constants.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Function.h" 31 #include "llvm/IR/InstrTypes.h" 32 #include "llvm/IR/Instruction.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/IR/IntrinsicInst.h" 35 #include "llvm/IR/Intrinsics.h" 36 #include "llvm/IR/Module.h" 37 #include "llvm/IR/PassManager.h" 38 #include "llvm/IR/Type.h" 39 #include "llvm/IR/Use.h" 40 #include "llvm/IR/User.h" 41 #include "llvm/IR/Value.h" 42 #include "llvm/Pass.h" 43 #include "llvm/Support/Casting.h" 44 #include "llvm/Support/Debug.h" 45 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/Transforms/IPO.h" 47 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 48 #include <cassert> 49 #include <cstdint> 50 #include <utility> 51 #include <vector> 52 53 using namespace llvm; 54 55 #define DEBUG_TYPE "deadargelim" 56 57 STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 58 STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 59 STATISTIC(NumArgumentsReplacedWithUndef, 60 "Number of unread args replaced with undef"); 61 62 namespace { 63 64 /// DAE - The dead argument elimination pass. 65 class DAE : public ModulePass { 66 protected: 67 // DAH uses this to specify a different ID. 68 explicit DAE(char &ID) : ModulePass(ID) {} 69 70 public: 71 static char ID; // Pass identification, replacement for typeid 72 73 DAE() : ModulePass(ID) { 74 initializeDAEPass(*PassRegistry::getPassRegistry()); 75 } 76 77 bool runOnModule(Module &M) override { 78 if (skipModule(M)) 79 return false; 80 DeadArgumentEliminationPass DAEP(ShouldHackArguments()); 81 ModuleAnalysisManager DummyMAM; 82 PreservedAnalyses PA = DAEP.run(M, DummyMAM); 83 return !PA.areAllPreserved(); 84 } 85 86 virtual bool ShouldHackArguments() const { return false; } 87 }; 88 89 } // end anonymous namespace 90 91 char DAE::ID = 0; 92 93 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 94 95 namespace { 96 97 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 98 /// deletes arguments to functions which are external. This is only for use 99 /// by bugpoint. 100 struct DAH : public DAE { 101 static char ID; 102 103 DAH() : DAE(ID) {} 104 105 bool ShouldHackArguments() const override { return true; } 106 }; 107 108 } // end anonymous namespace 109 110 char DAH::ID = 0; 111 112 INITIALIZE_PASS(DAH, "deadarghaX0r", 113 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", 114 false, false) 115 116 /// createDeadArgEliminationPass - This pass removes arguments from functions 117 /// which are not used by the body of the function. 118 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 119 120 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 121 122 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if 123 /// llvm.vastart is never called, the varargs list is dead for the function. 124 bool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) { 125 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 126 if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false; 127 128 // Ensure that the function is only directly called. 129 if (Fn.hasAddressTaken()) 130 return false; 131 132 // Don't touch naked functions. The assembly might be using an argument, or 133 // otherwise rely on the frame layout in a way that this analysis will not 134 // see. 135 if (Fn.hasFnAttribute(Attribute::Naked)) { 136 return false; 137 } 138 139 // Okay, we know we can transform this function if safe. Scan its body 140 // looking for calls marked musttail or calls to llvm.vastart. 141 for (BasicBlock &BB : Fn) { 142 for (Instruction &I : BB) { 143 CallInst *CI = dyn_cast<CallInst>(&I); 144 if (!CI) 145 continue; 146 if (CI->isMustTailCall()) 147 return false; 148 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 149 if (II->getIntrinsicID() == Intrinsic::vastart) 150 return false; 151 } 152 } 153 } 154 155 // If we get here, there are no calls to llvm.vastart in the function body, 156 // remove the "..." and adjust all the calls. 157 158 // Start by computing a new prototype for the function, which is the same as 159 // the old function, but doesn't have isVarArg set. 160 FunctionType *FTy = Fn.getFunctionType(); 161 162 std::vector<Type *> Params(FTy->param_begin(), FTy->param_end()); 163 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 164 Params, false); 165 unsigned NumArgs = Params.size(); 166 167 // Create the new function body and insert it into the module... 168 Function *NF = Function::Create(NFTy, Fn.getLinkage()); 169 NF->copyAttributesFrom(&Fn); 170 NF->setComdat(Fn.getComdat()); 171 Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF); 172 NF->takeName(&Fn); 173 174 // Loop over all of the callers of the function, transforming the call sites 175 // to pass in a smaller number of arguments into the new function. 176 // 177 std::vector<Value *> Args; 178 for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) { 179 CallSite CS(*I++); 180 if (!CS) 181 continue; 182 Instruction *Call = CS.getInstruction(); 183 184 // Pass all the same arguments. 185 Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs); 186 187 // Drop any attributes that were on the vararg arguments. 188 AttributeList PAL = CS.getAttributes(); 189 if (!PAL.isEmpty()) { 190 SmallVector<AttributeSet, 8> ArgAttrs; 191 for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) 192 ArgAttrs.push_back(PAL.getParamAttributes(ArgNo)); 193 PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(), 194 PAL.getRetAttributes(), ArgAttrs); 195 } 196 197 SmallVector<OperandBundleDef, 1> OpBundles; 198 CS.getOperandBundlesAsDefs(OpBundles); 199 200 CallSite NewCS; 201 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 202 NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 203 Args, OpBundles, "", Call); 204 } else { 205 NewCS = CallInst::Create(NF, Args, OpBundles, "", Call); 206 cast<CallInst>(NewCS.getInstruction()) 207 ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 208 } 209 NewCS.setCallingConv(CS.getCallingConv()); 210 NewCS.setAttributes(PAL); 211 NewCS->setDebugLoc(Call->getDebugLoc()); 212 uint64_t W; 213 if (Call->extractProfTotalWeight(W)) 214 NewCS->setProfWeight(W); 215 216 Args.clear(); 217 218 if (!Call->use_empty()) 219 Call->replaceAllUsesWith(NewCS.getInstruction()); 220 221 NewCS->takeName(Call); 222 223 // Finally, remove the old call from the program, reducing the use-count of 224 // F. 225 Call->eraseFromParent(); 226 } 227 228 // Since we have now created the new function, splice the body of the old 229 // function right into the new function, leaving the old rotting hulk of the 230 // function empty. 231 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 232 233 // Loop over the argument list, transferring uses of the old arguments over to 234 // the new arguments, also transferring over the names as well. While we're at 235 // it, remove the dead arguments from the DeadArguments list. 236 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 237 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 238 // Move the name and users over to the new version. 239 I->replaceAllUsesWith(&*I2); 240 I2->takeName(&*I); 241 } 242 243 // Clone metadatas from the old function, including debug info descriptor. 244 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 245 Fn.getAllMetadata(MDs); 246 for (auto MD : MDs) 247 NF->addMetadata(MD.first, *MD.second); 248 249 // Fix up any BlockAddresses that refer to the function. 250 Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType())); 251 // Delete the bitcast that we just created, so that NF does not 252 // appear to be address-taken. 253 NF->removeDeadConstantUsers(); 254 // Finally, nuke the old function. 255 Fn.eraseFromParent(); 256 return true; 257 } 258 259 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any 260 /// arguments that are unused, and changes the caller parameters to be undefined 261 /// instead. 262 bool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) { 263 // We cannot change the arguments if this TU does not define the function or 264 // if the linker may choose a function body from another TU, even if the 265 // nominal linkage indicates that other copies of the function have the same 266 // semantics. In the below example, the dead load from %p may not have been 267 // eliminated from the linker-chosen copy of f, so replacing %p with undef 268 // in callers may introduce undefined behavior. 269 // 270 // define linkonce_odr void @f(i32* %p) { 271 // %v = load i32 %p 272 // ret void 273 // } 274 if (!Fn.hasExactDefinition()) 275 return false; 276 277 // Functions with local linkage should already have been handled, except the 278 // fragile (variadic) ones which we can improve here. 279 if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg()) 280 return false; 281 282 // Don't touch naked functions. The assembly might be using an argument, or 283 // otherwise rely on the frame layout in a way that this analysis will not 284 // see. 285 if (Fn.hasFnAttribute(Attribute::Naked)) 286 return false; 287 288 if (Fn.use_empty()) 289 return false; 290 291 SmallVector<unsigned, 8> UnusedArgs; 292 for (Argument &Arg : Fn.args()) { 293 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && !Arg.hasByValOrInAllocaAttr()) 294 UnusedArgs.push_back(Arg.getArgNo()); 295 } 296 297 if (UnusedArgs.empty()) 298 return false; 299 300 bool Changed = false; 301 302 for (Use &U : Fn.uses()) { 303 CallSite CS(U.getUser()); 304 if (!CS || !CS.isCallee(&U)) 305 continue; 306 307 // Now go through all unused args and replace them with "undef". 308 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 309 unsigned ArgNo = UnusedArgs[I]; 310 311 Value *Arg = CS.getArgument(ArgNo); 312 CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); 313 ++NumArgumentsReplacedWithUndef; 314 Changed = true; 315 } 316 } 317 318 return Changed; 319 } 320 321 /// Convenience function that returns the number of return values. It returns 0 322 /// for void functions and 1 for functions not returning a struct. It returns 323 /// the number of struct elements for functions returning a struct. 324 static unsigned NumRetVals(const Function *F) { 325 Type *RetTy = F->getReturnType(); 326 if (RetTy->isVoidTy()) 327 return 0; 328 else if (StructType *STy = dyn_cast<StructType>(RetTy)) 329 return STy->getNumElements(); 330 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 331 return ATy->getNumElements(); 332 else 333 return 1; 334 } 335 336 /// Returns the sub-type a function will return at a given Idx. Should 337 /// correspond to the result type of an ExtractValue instruction executed with 338 /// just that one Idx (i.e. only top-level structure is considered). 339 static Type *getRetComponentType(const Function *F, unsigned Idx) { 340 Type *RetTy = F->getReturnType(); 341 assert(!RetTy->isVoidTy() && "void type has no subtype"); 342 343 if (StructType *STy = dyn_cast<StructType>(RetTy)) 344 return STy->getElementType(Idx); 345 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 346 return ATy->getElementType(); 347 else 348 return RetTy; 349 } 350 351 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 352 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined 353 /// liveness of Use. 354 DeadArgumentEliminationPass::Liveness 355 DeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use, 356 UseVector &MaybeLiveUses) { 357 // We're live if our use or its Function is already marked as live. 358 if (LiveFunctions.count(Use.F) || LiveValues.count(Use)) 359 return Live; 360 361 // We're maybe live otherwise, but remember that we must become live if 362 // Use becomes live. 363 MaybeLiveUses.push_back(Use); 364 return MaybeLive; 365 } 366 367 /// SurveyUse - This looks at a single use of an argument or return value 368 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses 369 /// if it causes the used value to become MaybeLive. 370 /// 371 /// RetValNum is the return value number to use when this use is used in a 372 /// return instruction. This is used in the recursion, you should always leave 373 /// it at 0. 374 DeadArgumentEliminationPass::Liveness 375 DeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses, 376 unsigned RetValNum) { 377 const User *V = U->getUser(); 378 if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 379 // The value is returned from a function. It's only live when the 380 // function's return value is live. We use RetValNum here, for the case 381 // that U is really a use of an insertvalue instruction that uses the 382 // original Use. 383 const Function *F = RI->getParent()->getParent(); 384 if (RetValNum != -1U) { 385 RetOrArg Use = CreateRet(F, RetValNum); 386 // We might be live, depending on the liveness of Use. 387 return MarkIfNotLive(Use, MaybeLiveUses); 388 } else { 389 DeadArgumentEliminationPass::Liveness Result = MaybeLive; 390 for (unsigned i = 0; i < NumRetVals(F); ++i) { 391 RetOrArg Use = CreateRet(F, i); 392 // We might be live, depending on the liveness of Use. If any 393 // sub-value is live, then the entire value is considered live. This 394 // is a conservative choice, and better tracking is possible. 395 DeadArgumentEliminationPass::Liveness SubResult = 396 MarkIfNotLive(Use, MaybeLiveUses); 397 if (Result != Live) 398 Result = SubResult; 399 } 400 return Result; 401 } 402 } 403 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 404 if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() 405 && IV->hasIndices()) 406 // The use we are examining is inserted into an aggregate. Our liveness 407 // depends on all uses of that aggregate, but if it is used as a return 408 // value, only index at which we were inserted counts. 409 RetValNum = *IV->idx_begin(); 410 411 // Note that if we are used as the aggregate operand to the insertvalue, 412 // we don't change RetValNum, but do survey all our uses. 413 414 Liveness Result = MaybeLive; 415 for (const Use &UU : IV->uses()) { 416 Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); 417 if (Result == Live) 418 break; 419 } 420 return Result; 421 } 422 423 if (auto CS = ImmutableCallSite(V)) { 424 const Function *F = CS.getCalledFunction(); 425 if (F) { 426 // Used in a direct call. 427 428 // The function argument is live if it is used as a bundle operand. 429 if (CS.isBundleOperand(U)) 430 return Live; 431 432 // Find the argument number. We know for sure that this use is an 433 // argument, since if it was the function argument this would be an 434 // indirect call and the we know can't be looking at a value of the 435 // label type (for the invoke instruction). 436 unsigned ArgNo = CS.getArgumentNo(U); 437 438 if (ArgNo >= F->getFunctionType()->getNumParams()) 439 // The value is passed in through a vararg! Must be live. 440 return Live; 441 442 assert(CS.getArgument(ArgNo) 443 == CS->getOperand(U->getOperandNo()) 444 && "Argument is not where we expected it"); 445 446 // Value passed to a normal call. It's only live when the corresponding 447 // argument to the called function turns out live. 448 RetOrArg Use = CreateArg(F, ArgNo); 449 return MarkIfNotLive(Use, MaybeLiveUses); 450 } 451 } 452 // Used in any other way? Value must be live. 453 return Live; 454 } 455 456 /// SurveyUses - This looks at all the uses of the given value 457 /// Returns the Liveness deduced from the uses of this value. 458 /// 459 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 460 /// the result is Live, MaybeLiveUses might be modified but its content should 461 /// be ignored (since it might not be complete). 462 DeadArgumentEliminationPass::Liveness 463 DeadArgumentEliminationPass::SurveyUses(const Value *V, 464 UseVector &MaybeLiveUses) { 465 // Assume it's dead (which will only hold if there are no uses at all..). 466 Liveness Result = MaybeLive; 467 // Check each use. 468 for (const Use &U : V->uses()) { 469 Result = SurveyUse(&U, MaybeLiveUses); 470 if (Result == Live) 471 break; 472 } 473 return Result; 474 } 475 476 // SurveyFunction - This performs the initial survey of the specified function, 477 // checking out whether or not it uses any of its incoming arguments or whether 478 // any callers use the return value. This fills in the LiveValues set and Uses 479 // map. 480 // 481 // We consider arguments of non-internal functions to be intrinsically alive as 482 // well as arguments to functions which have their "address taken". 483 void DeadArgumentEliminationPass::SurveyFunction(const Function &F) { 484 // Functions with inalloca parameters are expecting args in a particular 485 // register and memory layout. 486 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) { 487 MarkLive(F); 488 return; 489 } 490 491 // Don't touch naked functions. The assembly might be using an argument, or 492 // otherwise rely on the frame layout in a way that this analysis will not 493 // see. 494 if (F.hasFnAttribute(Attribute::Naked)) { 495 MarkLive(F); 496 return; 497 } 498 499 unsigned RetCount = NumRetVals(&F); 500 501 // Assume all return values are dead 502 using RetVals = SmallVector<Liveness, 5>; 503 504 RetVals RetValLiveness(RetCount, MaybeLive); 505 506 using RetUses = SmallVector<UseVector, 5>; 507 508 // These vectors map each return value to the uses that make it MaybeLive, so 509 // we can add those to the Uses map if the return value really turns out to be 510 // MaybeLive. Initialized to a list of RetCount empty lists. 511 RetUses MaybeLiveRetUses(RetCount); 512 513 bool HasMustTailCalls = false; 514 515 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 516 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 517 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 518 != F.getFunctionType()->getReturnType()) { 519 // We don't support old style multiple return values. 520 MarkLive(F); 521 return; 522 } 523 } 524 525 // If we have any returns of `musttail` results - the signature can't 526 // change 527 if (BB->getTerminatingMustTailCall() != nullptr) 528 HasMustTailCalls = true; 529 } 530 531 if (HasMustTailCalls) { 532 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 533 << " has musttail calls\n"); 534 } 535 536 if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { 537 MarkLive(F); 538 return; 539 } 540 541 LLVM_DEBUG( 542 dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: " 543 << F.getName() << "\n"); 544 // Keep track of the number of live retvals, so we can skip checks once all 545 // of them turn out to be live. 546 unsigned NumLiveRetVals = 0; 547 548 bool HasMustTailCallers = false; 549 550 // Loop all uses of the function. 551 for (const Use &U : F.uses()) { 552 // If the function is PASSED IN as an argument, its address has been 553 // taken. 554 ImmutableCallSite CS(U.getUser()); 555 if (!CS || !CS.isCallee(&U)) { 556 MarkLive(F); 557 return; 558 } 559 560 // The number of arguments for `musttail` call must match the number of 561 // arguments of the caller 562 if (CS.isMustTailCall()) 563 HasMustTailCallers = true; 564 565 // If this use is anything other than a call site, the function is alive. 566 const Instruction *TheCall = CS.getInstruction(); 567 if (!TheCall) { // Not a direct call site? 568 MarkLive(F); 569 return; 570 } 571 572 // If we end up here, we are looking at a direct call to our function. 573 574 // Now, check how our return value(s) is/are used in this caller. Don't 575 // bother checking return values if all of them are live already. 576 if (NumLiveRetVals == RetCount) 577 continue; 578 579 // Check all uses of the return value. 580 for (const Use &U : TheCall->uses()) { 581 if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { 582 // This use uses a part of our return value, survey the uses of 583 // that part and store the results for this index only. 584 unsigned Idx = *Ext->idx_begin(); 585 if (RetValLiveness[Idx] != Live) { 586 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 587 if (RetValLiveness[Idx] == Live) 588 NumLiveRetVals++; 589 } 590 } else { 591 // Used by something else than extractvalue. Survey, but assume that the 592 // result applies to all sub-values. 593 UseVector MaybeLiveAggregateUses; 594 if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { 595 NumLiveRetVals = RetCount; 596 RetValLiveness.assign(RetCount, Live); 597 break; 598 } else { 599 for (unsigned i = 0; i != RetCount; ++i) { 600 if (RetValLiveness[i] != Live) 601 MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(), 602 MaybeLiveAggregateUses.end()); 603 } 604 } 605 } 606 } 607 } 608 609 if (HasMustTailCallers) { 610 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 611 << " has musttail callers\n"); 612 } 613 614 // Now we've inspected all callers, record the liveness of our return values. 615 for (unsigned i = 0; i != RetCount; ++i) 616 MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); 617 618 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: " 619 << F.getName() << "\n"); 620 621 // Now, check all of our arguments. 622 unsigned i = 0; 623 UseVector MaybeLiveArgUses; 624 for (Function::const_arg_iterator AI = F.arg_begin(), 625 E = F.arg_end(); AI != E; ++AI, ++i) { 626 Liveness Result; 627 if (F.getFunctionType()->isVarArg() || HasMustTailCallers || 628 HasMustTailCalls) { 629 // Variadic functions will already have a va_arg function expanded inside 630 // them, making them potentially very sensitive to ABI changes resulting 631 // from removing arguments entirely, so don't. For example AArch64 handles 632 // register and stack HFAs very differently, and this is reflected in the 633 // IR which has already been generated. 634 // 635 // `musttail` calls to this function restrict argument removal attempts. 636 // The signature of the caller must match the signature of the function. 637 // 638 // `musttail` calls in this function prevents us from changing its 639 // signature 640 Result = Live; 641 } else { 642 // See what the effect of this use is (recording any uses that cause 643 // MaybeLive in MaybeLiveArgUses). 644 Result = SurveyUses(&*AI, MaybeLiveArgUses); 645 } 646 647 // Mark the result. 648 MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); 649 // Clear the vector again for the next iteration. 650 MaybeLiveArgUses.clear(); 651 } 652 } 653 654 /// MarkValue - This function marks the liveness of RA depending on L. If L is 655 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 656 /// such that RA will be marked live if any use in MaybeLiveUses gets marked 657 /// live later on. 658 void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, 659 const UseVector &MaybeLiveUses) { 660 switch (L) { 661 case Live: 662 MarkLive(RA); 663 break; 664 case MaybeLive: 665 // Note any uses of this value, so this return value can be 666 // marked live whenever one of the uses becomes live. 667 for (const auto &MaybeLiveUse : MaybeLiveUses) 668 Uses.insert(std::make_pair(MaybeLiveUse, RA)); 669 break; 670 } 671 } 672 673 /// MarkLive - Mark the given Function as alive, meaning that it cannot be 674 /// changed in any way. Additionally, 675 /// mark any values that are used as this function's parameters or by its return 676 /// values (according to Uses) live as well. 677 void DeadArgumentEliminationPass::MarkLive(const Function &F) { 678 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: " 679 << F.getName() << "\n"); 680 // Mark the function as live. 681 LiveFunctions.insert(&F); 682 // Mark all arguments as live. 683 for (unsigned i = 0, e = F.arg_size(); i != e; ++i) 684 PropagateLiveness(CreateArg(&F, i)); 685 // Mark all return values as live. 686 for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) 687 PropagateLiveness(CreateRet(&F, i)); 688 } 689 690 /// MarkLive - Mark the given return value or argument as live. Additionally, 691 /// mark any values that are used by this value (according to Uses) live as 692 /// well. 693 void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { 694 if (LiveFunctions.count(RA.F)) 695 return; // Function was already marked Live. 696 697 if (!LiveValues.insert(RA).second) 698 return; // We were already marked Live. 699 700 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking " 701 << RA.getDescription() << " live\n"); 702 PropagateLiveness(RA); 703 } 704 705 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness 706 /// to any other values it uses (according to Uses). 707 void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { 708 // We don't use upper_bound (or equal_range) here, because our recursive call 709 // to ourselves is likely to cause the upper_bound (which is the first value 710 // not belonging to RA) to become erased and the iterator invalidated. 711 UseMap::iterator Begin = Uses.lower_bound(RA); 712 UseMap::iterator E = Uses.end(); 713 UseMap::iterator I; 714 for (I = Begin; I != E && I->first == RA; ++I) 715 MarkLive(I->second); 716 717 // Erase RA from the Uses map (from the lower bound to wherever we ended up 718 // after the loop). 719 Uses.erase(Begin, I); 720 } 721 722 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F 723 // that are not in LiveValues. Transform the function and all of the callees of 724 // the function to not have these arguments and return values. 725 // 726 bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { 727 // Don't modify fully live functions 728 if (LiveFunctions.count(F)) 729 return false; 730 731 // Start by computing a new prototype for the function, which is the same as 732 // the old function, but has fewer arguments and a different return type. 733 FunctionType *FTy = F->getFunctionType(); 734 std::vector<Type*> Params; 735 736 // Keep track of if we have a live 'returned' argument 737 bool HasLiveReturnedArg = false; 738 739 // Set up to build a new list of parameter attributes. 740 SmallVector<AttributeSet, 8> ArgAttrVec; 741 const AttributeList &PAL = F->getAttributes(); 742 743 // Remember which arguments are still alive. 744 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 745 // Construct the new parameter list from non-dead arguments. Also construct 746 // a new set of parameter attributes to correspond. Skip the first parameter 747 // attribute, since that belongs to the return value. 748 unsigned i = 0; 749 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 750 I != E; ++I, ++i) { 751 RetOrArg Arg = CreateArg(F, i); 752 if (LiveValues.erase(Arg)) { 753 Params.push_back(I->getType()); 754 ArgAlive[i] = true; 755 ArgAttrVec.push_back(PAL.getParamAttributes(i)); 756 HasLiveReturnedArg |= PAL.hasParamAttribute(i, Attribute::Returned); 757 } else { 758 ++NumArgumentsEliminated; 759 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " 760 << i << " (" << I->getName() << ") from " 761 << F->getName() << "\n"); 762 } 763 } 764 765 // Find out the new return value. 766 Type *RetTy = FTy->getReturnType(); 767 Type *NRetTy = nullptr; 768 unsigned RetCount = NumRetVals(F); 769 770 // -1 means unused, other numbers are the new index 771 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 772 std::vector<Type*> RetTypes; 773 774 // If there is a function with a live 'returned' argument but a dead return 775 // value, then there are two possible actions: 776 // 1) Eliminate the return value and take off the 'returned' attribute on the 777 // argument. 778 // 2) Retain the 'returned' attribute and treat the return value (but not the 779 // entire function) as live so that it is not eliminated. 780 // 781 // It's not clear in the general case which option is more profitable because, 782 // even in the absence of explicit uses of the return value, code generation 783 // is free to use the 'returned' attribute to do things like eliding 784 // save/restores of registers across calls. Whether or not this happens is 785 // target and ABI-specific as well as depending on the amount of register 786 // pressure, so there's no good way for an IR-level pass to figure this out. 787 // 788 // Fortunately, the only places where 'returned' is currently generated by 789 // the FE are places where 'returned' is basically free and almost always a 790 // performance win, so the second option can just be used always for now. 791 // 792 // This should be revisited if 'returned' is ever applied more liberally. 793 if (RetTy->isVoidTy() || HasLiveReturnedArg) { 794 NRetTy = RetTy; 795 } else { 796 // Look at each of the original return values individually. 797 for (unsigned i = 0; i != RetCount; ++i) { 798 RetOrArg Ret = CreateRet(F, i); 799 if (LiveValues.erase(Ret)) { 800 RetTypes.push_back(getRetComponentType(F, i)); 801 NewRetIdxs[i] = RetTypes.size() - 1; 802 } else { 803 ++NumRetValsEliminated; 804 LLVM_DEBUG( 805 dbgs() << "DeadArgumentEliminationPass - Removing return value " 806 << i << " from " << F->getName() << "\n"); 807 } 808 } 809 if (RetTypes.size() > 1) { 810 // More than one return type? Reduce it down to size. 811 if (StructType *STy = dyn_cast<StructType>(RetTy)) { 812 // Make the new struct packed if we used to return a packed struct 813 // already. 814 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 815 } else { 816 assert(isa<ArrayType>(RetTy) && "unexpected multi-value return"); 817 NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); 818 } 819 } else if (RetTypes.size() == 1) 820 // One return type? Just a simple value then, but only if we didn't use to 821 // return a struct with that simple value before. 822 NRetTy = RetTypes.front(); 823 else if (RetTypes.empty()) 824 // No return types? Make it void, but only if we didn't use to return {}. 825 NRetTy = Type::getVoidTy(F->getContext()); 826 } 827 828 assert(NRetTy && "No new return type found?"); 829 830 // The existing function return attributes. 831 AttrBuilder RAttrs(PAL.getRetAttributes()); 832 833 // Remove any incompatible attributes, but only if we removed all return 834 // values. Otherwise, ensure that we don't have any conflicting attributes 835 // here. Currently, this should not be possible, but special handling might be 836 // required when new return value attributes are added. 837 if (NRetTy->isVoidTy()) 838 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 839 else 840 assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && 841 "Return attributes no longer compatible?"); 842 843 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 844 845 // Strip allocsize attributes. They might refer to the deleted arguments. 846 AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( 847 F->getContext(), Attribute::AllocSize); 848 849 // Reconstruct the AttributesList based on the vector we constructed. 850 assert(ArgAttrVec.size() == Params.size()); 851 AttributeList NewPAL = 852 AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 853 854 // Create the new function type based on the recomputed parameters. 855 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 856 857 // No change? 858 if (NFTy == FTy) 859 return false; 860 861 // Create the new function body and insert it into the module... 862 Function *NF = Function::Create(NFTy, F->getLinkage()); 863 NF->copyAttributesFrom(F); 864 NF->setComdat(F->getComdat()); 865 NF->setAttributes(NewPAL); 866 // Insert the new function before the old function, so we won't be processing 867 // it again. 868 F->getParent()->getFunctionList().insert(F->getIterator(), NF); 869 NF->takeName(F); 870 871 // Loop over all of the callers of the function, transforming the call sites 872 // to pass in a smaller number of arguments into the new function. 873 std::vector<Value*> Args; 874 while (!F->use_empty()) { 875 CallSite CS(F->user_back()); 876 Instruction *Call = CS.getInstruction(); 877 878 ArgAttrVec.clear(); 879 const AttributeList &CallPAL = CS.getAttributes(); 880 881 // Adjust the call return attributes in case the function was changed to 882 // return void. 883 AttrBuilder RAttrs(CallPAL.getRetAttributes()); 884 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 885 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 886 887 // Declare these outside of the loops, so we can reuse them for the second 888 // loop, which loops the varargs. 889 CallSite::arg_iterator I = CS.arg_begin(); 890 unsigned i = 0; 891 // Loop over those operands, corresponding to the normal arguments to the 892 // original function, and add those that are still alive. 893 for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 894 if (ArgAlive[i]) { 895 Args.push_back(*I); 896 // Get original parameter attributes, but skip return attributes. 897 AttributeSet Attrs = CallPAL.getParamAttributes(i); 898 if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { 899 // If the return type has changed, then get rid of 'returned' on the 900 // call site. The alternative is to make all 'returned' attributes on 901 // call sites keep the return value alive just like 'returned' 902 // attributes on function declaration but it's less clearly a win and 903 // this is not an expected case anyway 904 ArgAttrVec.push_back(AttributeSet::get( 905 F->getContext(), 906 AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); 907 } else { 908 // Otherwise, use the original attributes. 909 ArgAttrVec.push_back(Attrs); 910 } 911 } 912 913 // Push any varargs arguments on the list. Don't forget their attributes. 914 for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 915 Args.push_back(*I); 916 ArgAttrVec.push_back(CallPAL.getParamAttributes(i)); 917 } 918 919 // Reconstruct the AttributesList based on the vector we constructed. 920 assert(ArgAttrVec.size() == Args.size()); 921 922 // Again, be sure to remove any allocsize attributes, since their indices 923 // may now be incorrect. 924 AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( 925 F->getContext(), Attribute::AllocSize); 926 927 AttributeList NewCallPAL = AttributeList::get( 928 F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 929 930 SmallVector<OperandBundleDef, 1> OpBundles; 931 CS.getOperandBundlesAsDefs(OpBundles); 932 933 CallSite NewCS; 934 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 935 NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 936 Args, OpBundles, "", Call->getParent()); 937 } else { 938 NewCS = CallInst::Create(NF, Args, OpBundles, "", Call); 939 cast<CallInst>(NewCS.getInstruction()) 940 ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 941 } 942 NewCS.setCallingConv(CS.getCallingConv()); 943 NewCS.setAttributes(NewCallPAL); 944 NewCS->setDebugLoc(Call->getDebugLoc()); 945 uint64_t W; 946 if (Call->extractProfTotalWeight(W)) 947 NewCS->setProfWeight(W); 948 Args.clear(); 949 ArgAttrVec.clear(); 950 951 Instruction *New = NewCS.getInstruction(); 952 if (!Call->use_empty()) { 953 if (New->getType() == Call->getType()) { 954 // Return type not changed? Just replace users then. 955 Call->replaceAllUsesWith(New); 956 New->takeName(Call); 957 } else if (New->getType()->isVoidTy()) { 958 // Our return value has uses, but they will get removed later on. 959 // Replace by null for now. 960 if (!Call->getType()->isX86_MMXTy()) 961 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 962 } else { 963 assert((RetTy->isStructTy() || RetTy->isArrayTy()) && 964 "Return type changed, but not into a void. The old return type" 965 " must have been a struct or an array!"); 966 Instruction *InsertPt = Call; 967 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 968 BasicBlock *NewEdge = SplitEdge(New->getParent(), II->getNormalDest()); 969 InsertPt = &*NewEdge->getFirstInsertionPt(); 970 } 971 972 // We used to return a struct or array. Instead of doing smart stuff 973 // with all the uses, we will just rebuild it using extract/insertvalue 974 // chaining and let instcombine clean that up. 975 // 976 // Start out building up our return value from undef 977 Value *RetVal = UndefValue::get(RetTy); 978 for (unsigned i = 0; i != RetCount; ++i) 979 if (NewRetIdxs[i] != -1) { 980 Value *V; 981 if (RetTypes.size() > 1) 982 // We are still returning a struct, so extract the value from our 983 // return value 984 V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret", 985 InsertPt); 986 else 987 // We are now returning a single element, so just insert that 988 V = New; 989 // Insert the value at the old position 990 RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt); 991 } 992 // Now, replace all uses of the old call instruction with the return 993 // struct we built 994 Call->replaceAllUsesWith(RetVal); 995 New->takeName(Call); 996 } 997 } 998 999 // Finally, remove the old call from the program, reducing the use-count of 1000 // F. 1001 Call->eraseFromParent(); 1002 } 1003 1004 // Since we have now created the new function, splice the body of the old 1005 // function right into the new function, leaving the old rotting hulk of the 1006 // function empty. 1007 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 1008 1009 // Loop over the argument list, transferring uses of the old arguments over to 1010 // the new arguments, also transferring over the names as well. 1011 i = 0; 1012 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 1013 I2 = NF->arg_begin(); I != E; ++I, ++i) 1014 if (ArgAlive[i]) { 1015 // If this is a live argument, move the name and users over to the new 1016 // version. 1017 I->replaceAllUsesWith(&*I2); 1018 I2->takeName(&*I); 1019 ++I2; 1020 } else { 1021 // If this argument is dead, replace any uses of it with null constants 1022 // (these are guaranteed to become unused later on). 1023 if (!I->getType()->isX86_MMXTy()) 1024 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 1025 } 1026 1027 // If we change the return value of the function we must rewrite any return 1028 // instructions. Check this now. 1029 if (F->getReturnType() != NF->getReturnType()) 1030 for (BasicBlock &BB : *NF) 1031 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { 1032 Value *RetVal; 1033 1034 if (NFTy->getReturnType()->isVoidTy()) { 1035 RetVal = nullptr; 1036 } else { 1037 assert(RetTy->isStructTy() || RetTy->isArrayTy()); 1038 // The original return value was a struct or array, insert 1039 // extractvalue/insertvalue chains to extract only the values we need 1040 // to return and insert them into our new result. 1041 // This does generate messy code, but we'll let it to instcombine to 1042 // clean that up. 1043 Value *OldRet = RI->getOperand(0); 1044 // Start out building up our return value from undef 1045 RetVal = UndefValue::get(NRetTy); 1046 for (unsigned i = 0; i != RetCount; ++i) 1047 if (NewRetIdxs[i] != -1) { 1048 ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 1049 "oldret", RI); 1050 if (RetTypes.size() > 1) { 1051 // We're still returning a struct, so reinsert the value into 1052 // our new return value at the new index 1053 1054 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 1055 "newret", RI); 1056 } else { 1057 // We are now only returning a simple value, so just return the 1058 // extracted value. 1059 RetVal = EV; 1060 } 1061 } 1062 } 1063 // Replace the return instruction with one returning the new return 1064 // value (possibly 0 if we became void). 1065 ReturnInst::Create(F->getContext(), RetVal, RI); 1066 BB.getInstList().erase(RI); 1067 } 1068 1069 // Clone metadatas from the old function, including debug info descriptor. 1070 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 1071 F->getAllMetadata(MDs); 1072 for (auto MD : MDs) 1073 NF->addMetadata(MD.first, *MD.second); 1074 1075 // Now that the old function is dead, delete it. 1076 F->eraseFromParent(); 1077 1078 return true; 1079 } 1080 1081 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, 1082 ModuleAnalysisManager &) { 1083 bool Changed = false; 1084 1085 // First pass: Do a simple check to see if any functions can have their "..." 1086 // removed. We can do this if they never call va_start. This loop cannot be 1087 // fused with the next loop, because deleting a function invalidates 1088 // information computed while surveying other functions. 1089 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); 1090 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1091 Function &F = *I++; 1092 if (F.getFunctionType()->isVarArg()) 1093 Changed |= DeleteDeadVarargs(F); 1094 } 1095 1096 // Second phase:loop through the module, determining which arguments are live. 1097 // We assume all arguments are dead unless proven otherwise (allowing us to 1098 // determine that dead arguments passed into recursive functions are dead). 1099 // 1100 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); 1101 for (auto &F : M) 1102 SurveyFunction(F); 1103 1104 // Now, remove all dead arguments and return values from each function in 1105 // turn. 1106 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1107 // Increment now, because the function will probably get removed (ie. 1108 // replaced by a new one). 1109 Function *F = &*I++; 1110 Changed |= RemoveDeadStuffFromFunction(F); 1111 } 1112 1113 // Finally, look for any unused parameters in functions with non-local 1114 // linkage and replace the passed in parameters with undef. 1115 for (auto &F : M) 1116 Changed |= RemoveDeadArgumentsFromCallers(F); 1117 1118 if (!Changed) 1119 return PreservedAnalyses::all(); 1120 return PreservedAnalyses::none(); 1121 } 1122