opt -passes="loop-deletion" crashes with 'Assertion `materialized_use_empty() && "Uses remain when a value is destroyed!"' failed.'

[mikaelholmen]

llvm commit: 66fcdfc
Reproduce with: opt -passes="loop-deletion" bbi-74244.ll -o - -S
Result:

While deleting: i16 %c.0
Use still stuck around after Def is destroyed:  %conv = sext i16 %c.0 to i32
opt: ../lib/IR/Value.cpp:102: llvm::Value::~Value(): Assertion `materialized_use_empty() && "Uses remain when a value is destroyed!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -passes=loop-deletion bbi-74244.ll -o - -S
 #0 0x0000000002e58d13 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2e58d13)
 #1 0x0000000002e56a2e llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2e56a2e)
 #2 0x0000000002e59096 SignalHandler(int) (../../main-github/llvm/build-all/bin/opt+0x2e59096)
 #3 0x00007fa59d698630 __restore_rt (/lib64/libpthread.so.0+0xf630)
 #4 0x00007fa59addf387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007fa59ade0a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007fa59add81a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007fa59add8252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000002661f42 llvm::Value::~Value() (../../main-github/llvm/build-all/bin/opt+0x2661f42)
 #9 0x00000000026619ad llvm::Value::deleteValue() (../../main-github/llvm/build-all/bin/opt+0x26619ad)
#10 0x00000000024dd8a7 llvm::BasicBlock::~BasicBlock() (../../main-github/llvm/build-all/bin/opt+0x24dd8a7)
#11 0x00000000024de9d3 llvm::BasicBlock::eraseFromParent() (../../main-github/llvm/build-all/bin/opt+0x24de9d3)
#12 0x0000000002f3d8f9 llvm::deleteDeadLoop(llvm::Loop*, llvm::DominatorTree*, llvm::ScalarEvolution*, llvm::LoopInfo*, llvm::MemorySSA*) (../../main-github/llvm/build-all/bin/opt+0x2f3d8f9)
#13 0x0000000002ba322f deleteLoopIfDead(llvm::Loop*, llvm::DominatorTree&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter&) (../../main-github/llvm/build-all/bin/opt+0x2ba322f)
#14 0x0000000002ba21f0 llvm::LoopDeletionPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x2ba21f0)
#15 0x00000000031c3b1d llvm::detail::PassModel<llvm::Loop, llvm::LoopDeletionPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x31c3b1d)
#16 0x00000000037e39df llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (../../main-github/llvm/build-all/bin/opt+0x37e39df)
#17 0x00000000037e36e3 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x37e36e3)
#18 0x00000000037e2d18 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x37e2d18)
#19 0x0000000003191b4d llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../main-github/llvm/build-all/bin/opt+0x3191b4d)
#20 0x00000000037e4852 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x37e4852)
#21 0x00000000031c311d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x31c311d)
#22 0x000000000263d59c llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x263d59c)
#23 0x0000000000ae596d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0xae596d)
#24 0x000000000264187e llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x264187e)
#25 0x0000000000ae574d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0xae574d)
#26 0x000000000263c84c llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x263c84c)
#27 0x000000000071fe20 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x71fe20)
#28 0x00000000007321f1 main (../../main-github/llvm/build-all/bin/opt+0x7321f1)
#29 0x00007fa59adcb555 __libc_start_main (/lib64/libc.so.6+0x22555)
#30 0x0000000000718410 _start (../../main-github/llvm/build-all/bin/opt+0x718410)
Abort

bbi-74244.ll.gz

[mikaelholmen]

This starts happening with commit f88a797

    [LoopDeletion] Allows deletion of possibly infinite side-effect free loops
    
    From C11 and C++11 onwards, a forward-progress requirement has been
    introduced for both languages. In the case of C, loops with non-constant
    conditionals that do not have any observable side-effects (as defined by
    6.8.5p6) can be assumed by the implementation to terminate, and in the
    case of C++, this assumption extends to all functions. The clang
    frontend will emit the `mustprogress` function attribute for C++
    functions (D86233, D85393, D86841) and emit the loop metadata
    `llvm.loop.mustprogress` for every loop in C11 or later that has a
    non-constant conditional.
    
    This patch modifies LoopDeletion so that only loops with
    the `llvm.loop.mustprogress` metadata or loops contained in functions
    that are required to make progress (`mustprogress` or `willreturn`) are
    checked for observable side-effects. If these loops do not have an
    observable side-effect, then we delete them.
    
    Loops without observable side-effects that do not satisfy the above
    conditions will not be deleted.
    
    Reviewed By: jdoerfert
    
    Differential Revision: https://reviews.llvm.org/D86844

[jdoerfert]

So far it seems the reason for the crash is: The LCSSA pass will not delete uses of the instructions in a loop that are part of unreachable blocks if the loop has no exit.

[jdoerfert]

There is two checks in LCSSA that avoid doing anything for loops w/o exit. I am not sure if the best way is:

1. Remove those checks and at least partially run some LCSSA functionality (or all of it?)
2. Run "new" code in LCSSA or loop delete especially for loops w/o exit node just to clean up the uses.

Suggestions?