"Fusion candidate not initialized properly!" in loop-fusion pass with new-PM

[bjope]

Bugzilla Link	51035
Version	trunk
OS	Linux
Attachments	loop-fusion-candidate-problem.ll
CC	@aeubanks,@fhahn,@mikaelholmen,@sidbav

Extended Description

When doing some tests with fuzzy pass pipelines in opt we hit some assertions in the loop-fusion pass

Running
opt -passes='function(loop-fusion)' -S -o - loop-fusion-candidate-problem.ll
results in an assertion in FusionCandidate::reportInvalidCandidate:

opt: ../lib/Transforms/Scalar/LoopFuse.cpp:374: bool {anonymous}::FusionCandidate::reportInvalidCandidate(llvm::Statistic&) const: Assertion `L && Preheader && "Fusion candidate not initialized properly!"' failed.
PLEASE submit a bug report to ... and include the crash backtrace.
Stack dump:
0. Program arguments: /bin/opt -passes=function(loop-fusion) -S -o - loop-fusion-candidate-problem.ll
#​0 0x00000000030e09a8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/bin/opt+0x30e09a8)
#​1 0x00000000030de47e SignalHandler(int) Signals.cpp:0:0
#​2 0x00007f4bcdf87630 __restore_rt sigaction.c:0:0
#​3 0x00007f4bcb8e4387 raise (/lib64/libc.so.6+0x36387)
#​4 0x00007f4bcb8e5a78 abort (/lib64/libc.so.6+0x37a78)
#​5 0x00007f4bcb8dd1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
#​6 0x00007f4bcb8dd252 (/lib64/libc.so.6+0x2f252)
#​7 0x0000000002fb7e0c (/bin/opt+0x2fb7e0c)
#​8 0x0000000002fba9b5 (anonymous namespace)::LoopFuser::collectFusionCandidates(llvm::SmallVector<llvm::Loop*, 4u> const&) LoopFuse.cpp:0:0
#​9 0x0000000002fc41fb (anonymous namespace)::LoopFuser::fuseLoops(llvm::Function&) LoopFuse.cpp:0:0
#​10 0x0000000002fc5353 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (/bin/opt+0x2fc5353)
#​11 0x00000000033bda1e llvm::detail::PassModel<llvm::Function, llvm::LoopFusePass, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (//bin/opt+0x33bda1e)
#​12 0x00000000027ef715 llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (/bin/opt+0x27ef715)
#​13 0x0000000000cfdb0e llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (//bin/opt+0xcfdb0e)
#​14 0x00000000027ee24e llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (/bin/opt+0x27ee24e)
#​15 0x0000000000779a6e llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (/bin/opt+0x779a6e)
#​16 0x00000000027ebb18 llvm::PassManager<llvm::Module, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (/bin/opt+0x27ebb18)
#​17 0x000000000078538b llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRefllvm::StringRef, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (/bin/opt+0x78538b)
#​18 0x00000000006b4865 main (/bin/opt+0x6b4865)

The same thing happens with
opt -enable-new-pm=1 -loop-fusion -S -o - loop-fusion-candidate-problem.ll
but not with
opt -enable-new-pm=0 -loop-fusion -S -o - loop-fusion-candidate-problem.ll

Looking at LoopFuse.cpp it looks like with the legacy PM the pass requires LoopSimplify to be run before the pass. So the pass implementation in some sense expects the loops to be in loop simplify form (at least that is what has been tested in the past with legacy PM). But with the new pass manager there is no such requirement.

It is perhaps also a bit silly that the FusionCandidate c'tor is calling reportInvalidCandidate without first verifying that the CFG requirements are valid. Normally when constructing FusionCandidate objects, the new object is validated post construction by using one of the isEligibleForFusion/verify member functions. But the c'tor itself is doing similar verification, but without checking the CFG requirement before calling reportInvalidCandidate.
A possible fix/workaround would be to also add such checks in the c'tor like this:

diff --git a/llvm/lib/Transforms/Scalar/LoopFuse.cpp b/llvm/lib/Transforms/Scalar/LoopFuse.cpp
index 889358bade31..e411861e2b09 100644
--- a/llvm/lib/Transforms/Scalar/LoopFuse.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopFuse.cpp
@@ -192,6 +192,12 @@ struct FusionCandidate {
GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)),
Peeled(false), DT(DT), PDT(PDT), ORE(ORE) {

• if (!isValid()) {

•  LLVM_DEBUG(dbgs() << "FC has invalid CFG requirements!\n");
  

•  invalidate();
  

•  return;
  

• }
• // Walk over all blocks in the loop and check for conditions that may
  // prevent fusion. For each block, walk over all instructions and collect
  // the memory reads and writes If any instructions that prevent fusion are

But maybe there are other problems hiding here as well. Unless the loop simplify form is forced somehow. One difference between the pass managers would be that the pass either would perform loop-fusion (including loop-simplify) on the given example, or just failing to identify any valid candidates and skip transformation altogether.

[aeubanks]

I'd vote for manually making all loops in the function into loop-simplify form to match the legacy pass.

[bjope]

I'd vote for manually making all loops in the function into loop-simplify
form to match the legacy pass.

Either the pass need to
a) skip doing transforms if the input IR isn't satisfying certain requirements
b) make sure the loop-simplify form requirement is fulfilled by first transforming the IR to loop simplify form
c) drop the pre-requirement on loop simplify form and handle non-simplified loops on the fly somehow

I would say that legacy pass is using the (b) solution. But I'd also say that it is done automatically. So what do you mean by doing it "manually"?

[aeubanks]

I mean do what LoopSimplifyPass::run() does, as in copy its implementation into LoopFuse. Or even better, just run LoopSimplifyPass before LoopFusePass.

The new PM doesn't have pass dependencies, so just add the LoopSimplify pass right before the LoopFuse pass to do the same thing.

[Narutoworld]

Is there anyone who have already worked on this issue ?

[bjope]

Is there anyone who have already worked on this issue ?

Don't think so. And it is not assigned to anyone, so it is up for grabs.

[Narutoworld]

Thanks, I will try to solve it.

[Narutoworld]

I have updated the patch for this issue.

[Narutoworld]

Patch accepted and commited, we can closed this issue.

[mikaelholmen]

Thanks @Narutoworld

[mikaelholmen]

I ran some more tests with loop-fusion and with
opt -passes="loop-fusion" bbi-58003.ll -o /dev/null
I still hit

opt: ../lib/Transforms/Scalar/LoopFuse.cpp:376: bool (anonymous namespace)::FusionCandidate::reportInvalidCandidate(llvm::Statistic &) const: Assertion `L && Preheader && "Fusion candidate not initialized properly!"' failed.

even with the fix in eda3c93
bbi-58003.ll.gz

[Narutoworld]

Hi, @mikaelholmen
I just run bbi-58003.ll with opt -passes="loop-fusion" bbi-58003.ll -S.
But I don't hit any exception.

[mikaelholmen]

Strange, I tried on latest top-of-tree 0c1f9b3 now, and it fails there too