This is an archive of the discontinued LLVM Phabricator instance.

[ArgPromotion] Remove dead code produced by removing dead arguments
ClosedPublic

Authored by jrbyrnes on Mar 17 2023, 1:18 PM.

Details

Summary

ArgPromotion currently produces phantom / dead loads. A good example of this is store-into-inself.ll. First, ArgPromo finds the promotable argument %p in @l. Then it inserts a load of %p in the caller, and passes instead the loaded value / transforms the function body. PromoteMem2Reg is able to optimize out the entire function body, resulting in an unused argument. In a subsequent doPromotion iteration, it removes the dead argument, resulting in a dead load in the caller. These dead loads may reduce effectiveness of other transformations (e.g. SimplifyCFG, MergedLoadStoreMotion).

This patch removes loads and geps that are made dead in the caller after removal of dead args.

Diff Detail

Event Timeline

jrbyrnes created this revision.Mar 17 2023, 1:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2023, 1:18 PM
jrbyrnes requested review of this revision.Mar 17 2023, 1:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2023, 1:18 PM
jrbyrnes edited the summary of this revision. (Show Details)Mar 17 2023, 1:23 PM
nikic requested changes to this revision.Mar 17 2023, 1:33 PM

Please add a PhaseOrdering test that demonstrates why it it useful to do this as part of ArgumentPromotion, rather than letting other passes clean this up.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
282

This implementation looks too complicated. It should be enough to collect all potentially dead arguments and then call RecursivelyDeleteTriviallyDeadInstructionsPermissive() on the vector.

llvm/test/Transforms/ArgumentPromotion/propagate-remove-dead-args.ll
1

Add --function-signature or --version 2.

6

nounwind not needed?

32

fastcc not needed?

This revision now requires changes to proceed.Mar 17 2023, 1:33 PM
jrbyrnes updated this revision to Diff 507449.Mar 22 2023, 11:39 AM
jrbyrnes marked 4 inline comments as done.

Thanks @nikic for your comments. Added the PhaseOrdering test to demonstrate impact patch has on subsequent passes. Also, cleaned up implementation w/ use of API.

This looks good to me, but could you please pre-commit the new tests with baseline check lines, and then rebase this patch so that only the test diff is visible?

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
260

Don't think we need this comment given the assert on the next line...

jrbyrnes updated this revision to Diff 507474.Mar 22 2023, 12:36 PM

Rebase to show diff.

Summary of impact on PhaseOrdering test: During argPromotion of @phantomLoad, we introduce some loads of %this in @badChild. In a subsequent iteration of doPromotion we remove dead %this from @phantomLoad argument. This patch removes also the dead loads in @badChild. This allows argPromotion of @badChild to promote %this which cleans up the if.then and if.else blocks a bit. Then, MergedLoadStoreMotion is able to completely sink the CFG due to cleaned structure, and SimplifyCFG is able to remove it altogether.

nikic accepted this revision.Mar 22 2023, 1:19 PM

LGTM

Thanks for the PhaseOrdering test, I think I get the problem now. ArgPromotion is the first pass in the CGSCC pipeline, and works a bit unusually in that promotion will insert loads in the caller (outside the current SCC). This means the we run ArgPromotion on a child function, which inserts instructions in the parent and simplify the child. Then we run ArgPromotion on the parent, but at this point the parent has not been simplified yet. As such, it is important for ArgPromotion to clean up instructions it inserts. There's possibly some phase ordering improvement we could make here, but I don't see anything obvious. (Just moving ArgPromotion to the end of the CGSCC pipeline would cause the reverse issue that function simplification can not make use of the promotion for cleanup.)

This revision is now accepted and ready to land.Mar 22 2023, 1:19 PM
This revision was landed with ongoing or failed builds.Mar 23 2023, 9:48 AM
This revision was automatically updated to reflect the committed changes.
uabelho added a subscriber: uabelho.EditedMar 23 2023, 10:32 PM

Hi,

The following seems to crash ArgumentPromotion with this patch:

clang -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -O3 -o foo2.obj foo2.c

Result:

clang: ../include/llvm/Support/Casting.h:657: decltype(auto) llvm::dyn_cast(From &) [To = llvm::Instruction, From = llvm::WeakTrackingVH]: Assertion `detail::isPresent(Val) && "dyn_cast on a non-existent value"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: build-all/bin/clang -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -O3 -o foo2.obj foo2.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000002ff8598 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/clang+0x2ff8598)
 #1 0x0000000002ff612e llvm::sys::RunSignalHandlers() (build-all/bin/clang+0x2ff612e)
 #2 0x0000000002ff8c16 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007efccbc19630 __restore_rt sigaction.c:0:0
 #4 0x00007efcc9360387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007efcc9361a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007efcc93591a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007efcc9359252 (/lib64/libc.so.6+0x2f252)
 #8 0x000000000309d12d (build-all/bin/clang+0x309d12d)
 #9 0x00000000041f341e doPromotion(llvm::Function*, llvm::AnalysisManager<llvm::Function>&, llvm::DenseMap<llvm::Argument*, llvm::SmallVector<std::pair<long, (anonymous namespace)::ArgPart>, 4u>, llvm::DenseMapInfo<llvm::Argument*, void>, llvm::detail::DenseMapPair<llvm::Argument*, llvm::SmallVector<std::pair<long, (anonymous namespace)::ArgPart>, 4u>>> const&) ArgumentPromotion.cpp:0:0
#10 0x00000000041ee86b llvm::ArgumentPromotionPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x41ee86b)
#11 0x000000000413528d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::ArgumentPromotionPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#12 0x00000000020a4c74 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x20a4c74)
#13 0x000000000412a84d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#14 0x00000000020a80f2 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x20a80f2)
#15 0x0000000004143f9d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#16 0x00000000020a6bab llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x20a6bab)
#17 0x000000000412aafd llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#18 0x0000000002a0dceb llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x2a0dceb)
#19 0x0000000004255fea llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x4255fea)
#20 0x000000000413128d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#21 0x0000000002a0dceb llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x2a0dceb)
#22 0x00000000031dec5f (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>&, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile>>&) BackendUtil.cpp:0:0
#23 0x00000000031d7d75 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (build-all/bin/clang+0x31d7d75)
#24 0x00000000040767e2 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) crtstuff.c:0:0
#25 0x0000000004b0d0e3 clang::ParseAST(clang::Sema&, bool, bool) (build-all/bin/clang+0x4b0d0e3)
#26 0x000000000398bec6 clang::FrontendAction::Execute() (build-all/bin/clang+0x398bec6)
#27 0x00000000038f7674 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (build-all/bin/clang+0x38f7674)
#28 0x0000000003a4fc2b clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (build-all/bin/clang+0x3a4fc2b)
#29 0x0000000000a5f2cc cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (build-all/bin/clang+0xa5f2cc)
#30 0x0000000000a5b2c0 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#31 0x0000000000a5a3f6 clang_main(int, char**, llvm::ToolContext const&) (build-all/bin/clang+0xa5a3f6)
#32 0x0000000000a6ad51 main (build-all/bin/clang+0xa6ad51)
#33 0x00007efcc934c555 __libc_start_main (/lib64/libc.so.6+0x22555)
#34 0x0000000000a56cbb _start (build-all/bin/clang+0xa56cbb)
Abort (core dumped)

Hi,

The following seems to crash ArgumentPromotion with this patch:

clang -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -O3 -o foo2.obj foo2.c

Result:

clang: ../include/llvm/Support/Casting.h:657: decltype(auto) llvm::dyn_cast(From &) [To = llvm::Instruction, From = llvm::WeakTrackingVH]: Assertion `detail::isPresent(Val) && "dyn_cast on a non-existent value"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: build-all/bin/clang -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -O3 -o foo2.obj foo2.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000002ff8598 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/clang+0x2ff8598)
 #1 0x0000000002ff612e llvm::sys::RunSignalHandlers() (build-all/bin/clang+0x2ff612e)
 #2 0x0000000002ff8c16 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007efccbc19630 __restore_rt sigaction.c:0:0
 #4 0x00007efcc9360387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007efcc9361a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007efcc93591a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007efcc9359252 (/lib64/libc.so.6+0x2f252)
 #8 0x000000000309d12d (build-all/bin/clang+0x309d12d)
 #9 0x00000000041f341e doPromotion(llvm::Function*, llvm::AnalysisManager<llvm::Function>&, llvm::DenseMap<llvm::Argument*, llvm::SmallVector<std::pair<long, (anonymous namespace)::ArgPart>, 4u>, llvm::DenseMapInfo<llvm::Argument*, void>, llvm::detail::DenseMapPair<llvm::Argument*, llvm::SmallVector<std::pair<long, (anonymous namespace)::ArgPart>, 4u>>> const&) ArgumentPromotion.cpp:0:0
#10 0x00000000041ee86b llvm::ArgumentPromotionPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x41ee86b)
#11 0x000000000413528d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::ArgumentPromotionPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#12 0x00000000020a4c74 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x20a4c74)
#13 0x000000000412a84d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#14 0x00000000020a80f2 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (build-all/bin/clang+0x20a80f2)
#15 0x0000000004143f9d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) crtstuff.c:0:0
#16 0x00000000020a6bab llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x20a6bab)
#17 0x000000000412aafd llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#18 0x0000000002a0dceb llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x2a0dceb)
#19 0x0000000004255fea llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x4255fea)
#20 0x000000000413128d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#21 0x0000000002a0dceb llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/clang+0x2a0dceb)
#22 0x00000000031dec5f (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>&, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile>>&) BackendUtil.cpp:0:0
#23 0x00000000031d7d75 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (build-all/bin/clang+0x31d7d75)
#24 0x00000000040767e2 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) crtstuff.c:0:0
#25 0x0000000004b0d0e3 clang::ParseAST(clang::Sema&, bool, bool) (build-all/bin/clang+0x4b0d0e3)
#26 0x000000000398bec6 clang::FrontendAction::Execute() (build-all/bin/clang+0x398bec6)
#27 0x00000000038f7674 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (build-all/bin/clang+0x38f7674)
#28 0x0000000003a4fc2b clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (build-all/bin/clang+0x3a4fc2b)
#29 0x0000000000a5f2cc cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (build-all/bin/clang+0xa5f2cc)
#30 0x0000000000a5b2c0 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#31 0x0000000000a5a3f6 clang_main(int, char**, llvm::ToolContext const&) (build-all/bin/clang+0xa5a3f6)
#32 0x0000000000a6ad51 main (build-all/bin/clang+0xa6ad51)
#33 0x00007efcc934c555 __libc_start_main (/lib64/libc.so.6+0x22555)
#34 0x0000000000a56cbb _start (build-all/bin/clang+0xa56cbb)
Abort (core dumped)

Reduced opt reproducer

opt -passes="argpromotion" bbi-80617.ll -o /dev/null

nikic added a comment.Mar 24 2023, 4:48 AM

Minimal test case:

define internal ptr @callee(ptr %dead) {
  ret ptr null
}

define void @caller() {
  %ret = call ptr @callee(ptr null)
  %ret2 = call ptr @callee(ptr %ret)
  ret void
}

Wow, thanks for finding that and for the quick work!