llvm-reduce assertion failure

[nikic]

For https://gist.github.com/nikic/0e4c3a7e4783ceeb15b5f9fab1b22809 with

#!/bin/sh
! build/bin/opt -S -slp-vectorizer < $1 > /dev/null

build/bin/llvm-reduce --test crash.sh test.ll results in the following assertion failure:

llvm-reduce: /home/npopov/repos/llvm-project/llvm/tools/llvm-reduce/deltas/Delta.cpp:271: void llvm::runDeltaPass(llvm::TestRunner&, llvm::ReductionFunc): Assertion `Targets == NoChunksCounter.count() && "number of chunks changes when reducing"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build/bin/llvm-reduce --test crash.sh out.ll
 #0 0x000000000288cf91 PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x000000000288ac74 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f34e1ac8dc0 __restore_rt (/lib64/libc.so.6+0x54dc0)
 #3 0x00007f34e1b1556c __pthread_kill_implementation (/lib64/libc.so.6+0xa156c)
 #4 0x00007f34e1ac8d16 gsignal (/lib64/libc.so.6+0x54d16)
 #5 0x00007f34e1a9c7f3 abort (/lib64/libc.so.6+0x287f3)
 #6 0x00007f34e1a9c71b _nl_load_domain.cold (/lib64/libc.so.6+0x2871b)
 #7 0x00007f34e1ac1c66 (/lib64/libc.so.6+0x4dc66)
 #8 0x00000000004e263a llvm::runDeltaPass(llvm::TestRunner&, llvm::function_ref<void (llvm::Oracle&, ReducerWorkItem&)>) (build/bin/llvm-reduce+0x4e263a)
 #9 0x00000000004d45c5 llvm::runDeltaPasses(llvm::TestRunner&, int) (build/bin/llvm-reduce+0x4d45c5)
#10 0x0000000000413f1b main (build/bin/llvm-reduce+0x413f1b)
#11 0x00007f34e1ab3eb0 __libc_start_call_main (/lib64/libc.so.6+0x3feb0)
#12 0x00007f34e1ab3f60 __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x3ff60)
#13 0x00000000004d1d65 _start (build/bin/llvm-reduce+0x4d1d65)
Aborted (core dumped)

cc @regehr

[regehr]

thanks!

just a note here that this reduction works fine if you make the interestingness test more specific:

#!/bin/sh
opt -S -slp-vectorizer < $1 -o /dev/null 2>&1 | grep 'Scalar already in tree'

the issue with your test above is that it finds things like "module verifier fails" to be interesting, which is too broad of a criterion for what you most likely intended

this IR file exposes at least one bug in the BasicBlocks delta pass which I know needs work but I'm not certain how to fix yet. I'm starting an extended trip tomorrow and probably won't get to this bug in the near future, not sure if @arsenm or @aeubanks has time to look at the BasicBlocks pass.

[regehr]

also there's another bug here, this one in the main delta loop, that ends up saving invalid IR into reduced.ll when we reduce using Nikita's original interestingness test

[regehr]

well, I modified writeOutput() to call the module verifier before saving the module and then also shell out to opt -verify after saving the module to a file. at some point the first call passes and the second one fails. so we're either somehow invoking the module verifier wrong or it's missing a check that is present in the IR parser.

[nikic]

@regehr What's the error message? There are some things that are checked in the IR/BC parser rather than verifier, but generally those things should also have an assertion checking them (which is why it has to happen in the parser).

[regehr]

ok, the issue is that our basic block pass sometimes creates phi nodes with zero incoming values, and then the module verifier fails to check that condition (despite the fact that it claims to check it, in a comment at the top of the file). if we apply the verifier patch below, it detects the invalid code created by the basic block pass, and then llvm-reduce becomes capable of reducing your file even with your original, broader interestingness test.

I ran ninja check after adding this patch and there's one failing test: LLVM-Unit :: IR/./IRTests/18/35

but also, a change to the module verifier is a bit outside my comfort zone, especially just before I get on some long plane flights. is someone more experienced at pushing this sort of change comfortable doing that?

diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp
index 2e208a086820..e743e8ea1f40 100644
--- a/llvm/lib/IR/Verifier.cpp
+++ b/llvm/lib/IR/Verifier.cpp
@@ -3159,6 +3159,9 @@ void Verifier::visitPHINode(PHINode &PN) {
   // Check that a PHI doesn't yield a Token.
   Check(!PN.getType()->isTokenTy(), "PHI nodes cannot have token type!");
 
+  // Every PHI must have at least one incoming value.
+  Check(PN.getNumIncomingValues() >= 1, "PHI node has no incoming values", &PN);
+
   // Check that all of the values of the PHI node have the same type as the
   // result, and that the incoming blocks are really basic blocks.
   for (Value *IncValue : PN.incoming_values()) {

[regehr]

the test that fails is this one. do we want the module verifier to ignore phi nodes that lack incoming values?

TEST(BasicBlockTest, EmptyPhi) {
  LLVMContext Ctx;

  Module *M = new Module("MyModule", Ctx);
  FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
  Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);

  BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
  ReturnInst::Create(Ctx, BB1);

  Type *Ty = Type::getInt32PtrTy(Ctx);
  BasicBlock *BB2 = BasicBlock::Create(Ctx, "", F);
  PHINode::Create(Ty, 0, "", BB2);
  ReturnInst::Create(Ctx, BB2);
  EXPECT_FALSE(verifyModule(*M, &errs()));
}

[nikic]

It looks like we went in the direction of allowing zero-input phis (in unreachable blocks), see https://reviews.llvm.org/rG9eb2c0113dfe. But it doesn't looks like this was fully implemented, if the IR parser still rejects it. cc @rotateright

[regehr]

ah, thanks, I didn't know this history. I would strongly advocate trying to keep the module verifier in sync with the parser, though of course we avoid getting burned by this mismatch here if we fix the issue in llvm-reduce (the issue is not as simple as making sure unreachable blocks get deleted, there are deeper issues).

anyhow at the very least we should delete the currently-incorrect comment at the top of the module verifier.

[rotateright]

Killing the comment is easy enough :)
15090af

I haven't made a parser change in a long time, so I'll need to look at how to do that. Are we saying that we want to accept something like this:

define void @dead_phi() {
entry:
  br label %entry

return:
  %r = phi i32
  ret void
}

...as valid IR?

[nikic]

Yes -- though we might want to make the syntax %r = phi i32 [], at least that seems more consistent to me.