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