Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline
Changeset View
Standalone View
llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp
| Show First 20 Lines • Show All 79 Lines • ▼ Show 20 Lines | bool runOnModule(Module &M) override { | ||||
| ModuleAnalysisManager DummyMAM; | ModuleAnalysisManager DummyMAM; | ||||
| PreservedAnalyses PA = DAEP.run(M, DummyMAM); | PreservedAnalyses PA = DAEP.run(M, DummyMAM); | ||||
| return !PA.areAllPreserved(); | return !PA.areAllPreserved(); | ||||
| } | } | ||||
| virtual bool shouldHackArguments() const { return false; } | virtual bool shouldHackArguments() const { return false; } | ||||
| }; | }; | ||||
| bool isMustTailCalleeAnalyzable(const CallBase &CB) { | |||||
| assert(CB.isMustTailCall()); | |||||
nikic: Is `isDeclaration()` the right criterion here? Shouldn't we be checking for `hasLocalLinkage()`? | |||||
Line 544 has the hasLocalLinkage bit. The case here is about callees of musttail calls. Maybe I can rename this to isMusttailCalleeAnalyzable and hoist up the rest of the test, for clarity. mtrofin: Line 544 has the `hasLocalLinkage` bit. The case here is about callees of musttail calls. | |||||
| return CB.getCalledFunction() && !CB.getCalledFunction()->isDeclaration(); | |||||
| } | |||||
| } // end anonymous namespace | } // end anonymous namespace | ||||
| char DAE::ID = 0; | char DAE::ID = 0; | ||||
| INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) | INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) | ||||
| namespace { | namespace { | ||||
| ▲ Show 20 Lines • Show All 419 Lines • ▼ Show 20 Lines | void DeadArgumentEliminationPass::surveyFunction(const Function &F) { | ||||
| // we can add those to the Uses map if the return value really turns out to be | // we can add those to the Uses map if the return value really turns out to be | ||||
| // MaybeLive. Initialized to a list of RetCount empty lists. | // MaybeLive. Initialized to a list of RetCount empty lists. | ||||
| RetUses MaybeLiveRetUses(RetCount); | RetUses MaybeLiveRetUses(RetCount); | ||||
| bool HasMustTailCalls = false; | bool HasMustTailCalls = false; | ||||
| for (const BasicBlock &BB : F) { | for (const BasicBlock &BB : F) { | ||||
| // If we have any returns of `musttail` results - the signature can't | // If we have any returns of `musttail` results - the signature can't | ||||
| // change | // change | ||||
| if (BB.getTerminatingMustTailCall() != nullptr) | if (const auto *TC = BB.getTerminatingMustTailCall()) { | ||||
| HasMustTailCalls = true; | HasMustTailCalls = true; | ||||
| // In addition, if the called function is not locally defined (or unknown, | |||||
| // if this is an indirect call), we can't change the callsite and thus | |||||
Please explain why this matters. Intuitively, whether a function is virtual shouldn't affect liveness... do we handle the non-virtual case somewhere else? efriedma: Please explain why this matters. Intuitively, whether a function is virtual shouldn't affect… | |||||
Not sure I understand. It's about virtual musttail calls, not just virtual. "Liveness" in this pass means "it can't change". Without the patch, the test fails in the validator, because the module is transformed to: define internal void @test(ptr %fptr, i32 %a, i32 %b) {
%r = musttail call i32 %fptr(ptr %fptr, i32 %a, i32 0)
ret void
}The error is what the test checks isn't present: cannot guarantee tail call due to mismatched parameter counts The patch is actually incomplete - about to update it. This marking needs to be also propagated to users of the function. mtrofin: Not sure I understand. It's about virtual musttail calls, not just virtual. "Liveness" in this… | |||||
Not Done ReplyInline ActionsI believe Eli's point is that this is also true for non-virtual functions. For example, this example without virtual calls fails in the same way: define internal i32 @test() {
%r = musttail call i32 @foo()
ret i32 %r
}
declare i32 @foo()nikic: I believe Eli's point is that this is also true for non-virtual functions. For example, this… | |||||
Oh, I see. Let me update then. mtrofin: Oh, I see. Let me update then. | |||||
Not Done ReplyInline ActionsPlease add a comment explaining why direct calls and indirect calls are handled differently. (Is it related to the usage of getCalledFunction() in surveyUse?) efriedma: Please add a comment explaining why direct calls and indirect calls are handled differently. | |||||
Ah, it's not "direct" vs "indirect", rather, it's "can the callee be statically known and is it defined in this module". If it is, then we know that whatever transformations we plan on making at the callsite will also be reflected in the body of that callee. But if it's not, we don't know if that could happen. Declarations ended up being marked as "live" just below. So we'd pick up that in propagateVirtMustcallLiveness. All that being said, I think handling both callee cases here is more clear (+clarifying comment) WDYT? mtrofin: Ah, it's not "direct" vs "indirect", rather, it's "can the callee be statically known and is it… | |||||
The concept makes sense to me... I'd prefer some more obvious way to quantify "calls to functions we can't analyze" to make it more obvious this is the inverse of the calls we do analyze. efriedma: The concept makes sense to me... I'd prefer some more obvious way to quantify "calls to… | |||||
Would a isCalleeAnalyzable member that does the !TC->getCalledFunction() || TC->getCalledFunction()->isDeclaration() address that? mtrofin: Would a `isCalleeAnalyzable` member that does the `!TC->getCalledFunction() || TC… | |||||
That's reasonable. efriedma: That's reasonable. | |||||
done, ptal (ended up just a function, no need for a member) mtrofin: done, ptal (ended up just a function, no need for a member) | |||||
| // can't change this function's signature either. | |||||
| if (!isMustTailCalleeAnalyzable(*TC)) { | |||||
| markLive(F); | |||||
| return; | |||||
| } | |||||
| } | |||||
| } | } | ||||
| if (HasMustTailCalls) { | if (HasMustTailCalls) { | ||||
| LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() | ||||
| << " has musttail calls\n"); | << " has musttail calls\n"); | ||||
| } | } | ||||
| if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { | if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { | ||||
| ▲ Show 20 Lines • Show All 543 Lines • ▼ Show 20 Lines | bool DeadArgumentEliminationPass::removeDeadStuffFromFunction(Function *F) { | ||||
| } | } | ||||
| // Now that the old function is dead, delete it. | // Now that the old function is dead, delete it. | ||||
| F->eraseFromParent(); | F->eraseFromParent(); | ||||
| return true; | return true; | ||||
| } | } | ||||
| void DeadArgumentEliminationPass::propagateVirtMustcallLiveness( | |||||
| const Module &M) { | |||||
| // If a function was marked "live", and it has musttail callers, they in turn | |||||
| // can't change either. | |||||
| LiveFuncSet NewLiveFuncs(LiveFunctions); | |||||
| while (!NewLiveFuncs.empty()) { | |||||
| LiveFuncSet Temp; | |||||
| for (const auto *F : NewLiveFuncs) | |||||
| for (const auto *U : F->users()) | |||||
| if (const auto *CB = dyn_cast<CallBase>(U)) | |||||
| if (CB->isMustTailCall()) | |||||
| if (!LiveFunctions.count(CB->getParent()->getParent())) | |||||
| Temp.insert(CB->getParent()->getParent()); | |||||
| NewLiveFuncs.clear(); | |||||
| NewLiveFuncs.insert(Temp.begin(), Temp.end()); | |||||
| for (const auto *F : Temp) | |||||
| markLive(*F); | |||||
| } | |||||
| } | |||||
It's not really clear to me why we need a separate loop to do this, and this can't be included as part of the existing liveness propagation. E.g. surveyFunction() already looks at all the users, and even checks for musttail callers there. Currently, that's only used to mark all the arguments as live, but not the return values. Would it be sufficient to force live return values at that point? nikic: It's not really clear to me why we need a separate loop to do this, and this can't be included… | |||||
IIUC, if both argument and return values are marked, it'd be equivalent to the function being marked as live. But that aside, we can have A->B->C->x (all are musttail calls), and C has the unanalyzable callsite. That needs to "taint" all in the call chain. We could do that propagation in surveyFunction, but that would be equivalent to this patch, unless I'm missing something? mtrofin: IIUC, if both argument and return values are marked, it'd be equivalent to the function being… | |||||
Not Done ReplyInline ActionsDAE already propagates liveness across call chains, so it is best to reuse existing propagation is possible. However, after looking a bit closer I don't think we can actually use it, because for return values the propagation will go in the wrong direction. In that case, doing this separate propagation is reasonable. nikic: DAE already propagates liveness across call chains, so it is best to reuse existing propagation… | |||||
| PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, | PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, | ||||
| ModuleAnalysisManager &) { | ModuleAnalysisManager &) { | ||||
| bool Changed = false; | bool Changed = false; | ||||
| // First pass: Do a simple check to see if any functions can have their "..." | // First pass: Do a simple check to see if any functions can have their "..." | ||||
| // removed. We can do this if they never call va_start. This loop cannot be | // removed. We can do this if they never call va_start. This loop cannot be | ||||
| // fused with the next loop, because deleting a function invalidates | // fused with the next loop, because deleting a function invalidates | ||||
| // information computed while surveying other functions. | // information computed while surveying other functions. | ||||
| LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); | ||||
| for (Function &F : llvm::make_early_inc_range(M)) | for (Function &F : llvm::make_early_inc_range(M)) | ||||
| if (F.getFunctionType()->isVarArg()) | if (F.getFunctionType()->isVarArg()) | ||||
| Changed |= deleteDeadVarargs(F); | Changed |= deleteDeadVarargs(F); | ||||
| // Second phase: Loop through the module, determining which arguments are | // Second phase: Loop through the module, determining which arguments are | ||||
| // live. We assume all arguments are dead unless proven otherwise (allowing us | // live. We assume all arguments are dead unless proven otherwise (allowing us | ||||
| // to determine that dead arguments passed into recursive functions are dead). | // to determine that dead arguments passed into recursive functions are dead). | ||||
| LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); | ||||
| for (auto &F : M) | for (auto &F : M) | ||||
| surveyFunction(F); | surveyFunction(F); | ||||
| propagateVirtMustcallLiveness(M); | |||||
| // Now, remove all dead arguments and return values from each function in | // Now, remove all dead arguments and return values from each function in | ||||
| // turn. We use make_early_inc_range here because functions will probably get | // turn. We use make_early_inc_range here because functions will probably get | ||||
| // removed (i.e. replaced by new ones). | // removed (i.e. replaced by new ones). | ||||
| for (Function &F : llvm::make_early_inc_range(M)) | for (Function &F : llvm::make_early_inc_range(M)) | ||||
| Changed |= removeDeadStuffFromFunction(&F); | Changed |= removeDeadStuffFromFunction(&F); | ||||
| // Finally, look for any unused parameters in functions with non-local | // Finally, look for any unused parameters in functions with non-local | ||||
| // linkage and replace the passed in parameters with poison. | // linkage and replace the passed in parameters with poison. | ||||
| for (auto &F : M) | for (auto &F : M) | ||||
| Changed |= removeDeadArgumentsFromCallers(F); | Changed |= removeDeadArgumentsFromCallers(F); | ||||
| if (!Changed) | if (!Changed) | ||||
| return PreservedAnalyses::all(); | return PreservedAnalyses::all(); | ||||
| return PreservedAnalyses::none(); | return PreservedAnalyses::none(); | ||||
| } | } | ||||
Is isDeclaration() the right criterion here? Shouldn't we be checking for hasLocalLinkage()?