Assertion `ChainNode->getOpcode() != ISD::DELETED_NODE && "Deleted node left in chain"' failed.

[Quuxplusone]

Bugzilla Link	PR31710
Status	RESOLVED FIXED
Importance	P normal
Reported by	Kevin P. Neal (kpn@neutralgood.org)
Reported on	2017-01-20 12:37:04 -0800
Last modified on	2017-01-31 11:03:29 -0800
Version	4.0
Hardware	Other Linux
CC	hans@chromium.org, llvm-bugs@justinbogner.com, llvm-bugs@lists.llvm.org, uweigand@de.ibm.com
Fixed by commit(s)
Attachments	bugpoint-reduced-simplified.bc (4432 bytes, application/octet-stream) UpdateChains.patch (2309 bytes, text/plain)
Blocks	PR31622
Blocked by
See also

Created attachment 17874
The reduced bitcode that triggers the assertion.

Bug found when running 4.0.0rc1 on Linux on System/Z.

+ exec /sas3rd/wky/mva-alzx/lzx/llvm/llvm-400rc1/install/stock/bin/llc bugpoint-
reduced-simplified.bc
llc:
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:2264:
void llvm::SelectionDAGISel::UpdateChains(llvm::SDNode*, llvm::SDValue, const
llvm::SmallVectorImpl<llvm::SDNode*>&, bool): Assertion `ChainNode->getOpcode()
!= ISD::DELETED_NODE && "Deleted node left in chain"' failed.
#0 0x0000000081a66d8a llvm::sys::PrintStackTrace(llvm::raw_ostream&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Support/Unix/Signals.inc:402:0
#1 0x0000000081a6719a PrintStackTraceSignalHandler(void*)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Support/Unix/Signals.inc:466:0
#2 0x0000000081a64dc6 llvm::sys::RunSignalHandlers()
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Support/Signals.cpp:44:0
#3 0x0000000081a66406 SignalHandler(int)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Support/Unix/Signals.inc:253:0
#4 0x00000000946e039e
#5 0x000003ffa49ba830 __GI_raise /usr/src/debug/glibc-2.17-
c758a686/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x000003ffa49bc0b8 __GI_abort /usr/src/debug/glibc-2.17-
c758a686/stdlib/abort.c:92:0
#7 0x000003ffa49b2886 __assert_fail_base /usr/src/debug/glibc-2.17-
c758a686/assert/assert.c:53:0
#8 0x000003ffa49b2914 (/lib64/libc.so.6+0x32914)
#9 0x000000008187ebf6 llvm::SelectionDAGISel::UpdateChains(llvm::SDNode*,
llvm::SDValue, llvm::SmallVectorImpl<llvm::SDNode*> const&, bool)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:2268:0
#10 0x0000000081887582 llvm::SelectionDAGISel::SelectCodeCommon(llvm::SDNode*,
unsigned char const*, unsigned int)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:3540:0
#11 0x000000008088b294 (anonymous
namespace)::SystemZDAGToDAGISel::SelectCode(llvm::SDNode*)
/sasusr/u/saskpn/clvm/4.0.0rc1/LZXND/lib/Target/SystemZ/SystemZGenDAGISel.inc:25634:0
#12 0x0000000080895280 (anonymous
namespace)::SystemZDAGToDAGISel::Select(llvm::SDNode*)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp:1350:0
#13 0x0000000081877f5c llvm::SelectionDAGISel::DoInstructionSelection()
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:955:0
#14 0x0000000081877640 llvm::SelectionDAGISel::CodeGenAndEmitDAG()
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:861:0
#15 0x0000000081875cfc
llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction,
true, false, void>, false, true>,
llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true,
false, void>, false, true>, bool&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:684:0
#16 0x000000008187afc8
llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1561:0
#17 0x000000008187497e
llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:509:0
#18 0x000000008088b1c2 (anonymous
namespace)::SystemZDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp:338:0
#19 0x0000000080ed09e2
llvm::MachineFunctionPass::runOnFunction(llvm::Function&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#20 0x000000008147e726 llvm::FPPassManager::runOnFunction(llvm::Function&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#21 0x000000008147e974 llvm::FPPassManager::runOnModule(llvm::Module&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#22 0x000000008147ee3c (anonymous
namespace)::MPPassManager::runOnModule(llvm::Module&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#23 0x000000008147f730 llvm::legacy::PassManagerImpl::run(llvm::Module&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#24 0x000000008147fa90 llvm::legacy::PassManager::run(llvm::Module&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/lib/IR/LegacyPassManager.cpp:1724:0
#25 0x00000000807fef7a compileModule(char**, llvm::LLVMContext&)
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/tools/llc/llc.cpp:530:0
#26 0x00000000807fd330 main
/sasusr/u/saskpn/clvm/4.0.0rc1/llvm/tools/llc/llc.cpp:285:0
#27 0x000003ffa49a4572 __libc_start_main /usr/src/debug/glibc-2.17-
c758a686/csu/libc-start.c:308:0
#28 0x00000000807faf76 _start (/sas3rd/wky/mva-alzx/lzx/llvm/llvm-
400rc1/install/stock/bin/llc+0x807faf76)
Stack dump:
0.  Program arguments: /sas3rd/wky/mva-alzx/lzx/llvm/llvm-
400rc1/install/stock/bin/llc bugpoint-reduced-simplified.bc
1.  Running pass 'Function Pass Manager' on module 'bugpoint-reduced-
simplified.bc'.
2.  Running pass 'SystemZ DAG->DAG Pattern Instruction Selection' on function
'@btldata'

[Quuxplusone]

Attached bugpoint-reduced-simplified.bc (4432 bytes, application/octet-stream): The reduced bitcode that triggers the assertion.

[Quuxplusone]

Confirmed.

[Quuxplusone]

Here's a simplified version of the test case:

target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-a:8:16-n32:64"
target triple = "s390x-redhat-linux"

define void @btldata(i64 *%u0, i32 **%p0, i32** %p1, i32** %p3, i32** %p5,
i32** %p7) {
entry:
  %x0 = load i32*, i32** %p0, align 8, !tbaa !1
  store i64 0, i64* %u0, align 8, !tbaa !7

  %x1 = load i32*, i32** %p1, align 8, !tbaa !1
  %x2 = load i32, i32* %x1, align 4, !tbaa !5
  %x2ext = sext i32 %x2 to i64
  store i32 %x2, i32* %x1, align 4, !tbaa !5

  %x3 = load i32*, i32** %p3, align 8, !tbaa !1
  %ptr = getelementptr inbounds i32, i32* %x3, i64 %x2ext
  %x4 = load i32, i32* %ptr, align 4, !tbaa !5
  %x4inc = add nsw i32 %x4, 1
  store i32 %x4inc, i32* %ptr, align 4, !tbaa !5

  store i64 undef, i64* %u0, align 8, !tbaa !7

  %x5 = load i32*, i32** %p5, align 8, !tbaa !1
  %x6 = load i32, i32* %x5, align 4, !tbaa !5
  store i32 %x6, i32* %x5, align 4, !tbaa !5

  %x7 = load i32*, i32** %p7, align 8, !tbaa !1
  %x8 = load i32, i32* %x7, align 4, !tbaa !5
  %x8inc = add nsw i32 %x8, 1
  store i32 %x8inc, i32* %x7, align 4, !tbaa !5

  ret void
}

!1 = !{!2, !2, i64 0}
!2 = !{!"any pointer", !3, i64 0}
!3 = !{!"omnipotent char", !4, i64 0}
!4 = !{!"Simple C/C++ TBAA"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !3, i64 0}
!7 = !{!8, !8, i64 0}
!8 = !{!"long", !3, i64 0}

[Quuxplusone]

Instruction selection proceeds normally until this stage:

  t0: ch = EntryToken
    t6: i64,ch = CopyFromReg t0, Register:i64 %vreg2
  t78: i64,ch = load<LD8[%p1](tbaa=<0x6cb9e28>)> t0, t6, undef:i64
    t8: i64,ch = CopyFromReg t0, Register:i64 %vreg3
  t72: i64,ch = load<LD8[%p3](tbaa=<0x6cb9e28>)> t0, t8, undef:i64
  t76: i64,ch = load<LD4[%x1](tbaa=<0x6cba388>), sext from i32> t0, t78, undef:i64
      t2: i64,ch = CopyFromReg t0, Register:i64 %vreg0
    t64: ch = store<ST8[%u0](tbaa=<0x6cb9b28>)> t0, Constant:i64<0>, t2, undef:i64
  t83: ch = TokenFactor t64, t76:1, t78:1
    t24: i64 = shl t76, Constant:i32<2>
  t25: i64 = add t72, t24
  t70: i32,ch = load<LD4[%ptr](tbaa=<0x6cba388>)> t0, t25, undef:i64
  t71: ch = TokenFactor t83, t70:1
    t28: i32 = add t70, Constant:i32<1>
  t56: ch = store<ST4[%ptr](tbaa=<0x6cba388>)> t71, t28, t25, undef:i64
  t82: ch = TokenFactor t56, t71, t83, t72:1
    t13: i64,ch = load<LD8[FixedStack-1]> t0, FrameIndex:i64<-1>, undef:i64
  t36: i64,ch = LG<Mem:LD8[%p7](tbaa=<0x6cb9e28>)> t13, TargetConstant:i64<0>, Register:i64 %noreg, t82
      t58: ch = TokenFactor t83, t56
    t85: ch = TokenFactor t58, t82
  t43: i32,ch = ASI<Mem:ST4[%x7](tbaa=<0x6cba388>) LD4[%x7](tbaa=<0x6cba388>)> t36, TargetConstant:i64<0>, TargetConstant:i64<1>, t85
  t86: i32 = TargetConstant<1>
    t45: ch = TokenFactor t43:1, t36:1, t43:1
  t41: ch = Return t45

At this point, the store in t56 is the next node to select, and the matcher
recognizes another opportunity to use an in-memory operation (ASI) to replace
the load-add-store sequence.  Once this is done, the UpdateChains routine is
called.  This gets nodes t56, t70 and t71 as "ChainNodesMatched".

Since t56 is the target node, nothing is done.  Then, the chain output of t70
is replaced by the chain output of the target node using
ReplaceAllUsesOfValueWith.  Note that in particular one user of t70:1 is node
t71, which is "ch = TokenFactor t83, t70:1".  After replacement, we get instead
"ch = TokenFactor t83, t56", which now matches exactly the already-existing
node t58.  Therefore, node t71 is deleted and replaced by t58.

However, t71 was (and still is) in the ChainNodesMatched array, and is being
processed next.  At this point, it is a deleted node, and the assertion
triggers.

Now, I'm not sure there's anything actually wrong here -- if the code would
simply skip the deleted node instead of failing an assertion, everything would
appear to be working fine ...

[Quuxplusone]

Justin, it seems this problem (details in comment #3) might have been caused by your commit r271733 --- this watches out for chain nodes deleted in SelectCodeCommon, but not for chain nodes deleted during processing in UpdateChains itself. Can you have a look?

[Quuxplusone]

Attached UpdateChains.patch (2309 bytes, text/plain): Patch to work around the issue

[Quuxplusone]

This patch does indeed fix the problem for me, thanks.

[Quuxplusone]

I really appreciate the work you guys are putting into this fix. We'll be running tests over here at SAS hopefully tomorrow.

But, is there any chance of getting this fix into the 4.0 release?

[Quuxplusone]

(In reply to comment #7)
> I really appreciate the work you guys are putting into this fix.  We'll be
> running tests over here at SAS hopefully tomorrow.
>
> But, is there any chance of getting this fix into the 4.0 release?

Marking as a tentative blocker to keep it on the release radar.

[Quuxplusone]

Justin, are you planning to check your patch from comment #5 in, or are you still looking for some alternative solution?

[Quuxplusone]

A build of SAS for Linux on z with an rc1 compiler plus this change has no assertions and passes basic sanity checks.

[Quuxplusone]

Ulrich Weigand wrote:
> Justin, are you planning to check your patch from comment #5 in, or are you
still looking for some alternative solution?

Yeah, that's the best I can come up with. I Put the patch up for review, so
PTAL and LGTM it if you're happy:

  http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170123/424283.html

[Quuxplusone]

Fixed on trunk in r293522.

Hans: would you mind cherry picking this into 4.0?

[Quuxplusone]

(In reply to comment #12)
> Fixed on trunk in r293522.
>
> Hans: would you mind cherry picking this into 4.0?

Merged in r293650.