Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[AArch64][SVE][SelectionDAG] infinite loop caused by legalizing & combining CONCAT_VECTORS #63322

Closed
FLZ101 opened this issue Jun 15, 2023 · 5 comments
Closed

[AArch64][SVE][SelectionDAG] infinite loop caused by legalizing & combining CONCAT_VECTORS #63322

FLZ101 opened this issue Jun 15, 2023 · 5 comments
Labels
llvm:codegen

Comments

@FLZ101
Copy link
Contributor

FLZ101 commented Jun 15, 2023 •
edited by VoltrexKeyva 

$ clang --version
clang version 17.0.0 (https://github.com/llvm/llvm-project.git f9d0bf06319203a8cbb47d89c2f39d2c782f3887)
Target: aarch64-unknown-linux-gnu
Thread model: posix
; RUN: llc -O3 -mcpu=neoverse-n2 < %s | FileCheck %s
; CHECK: allocno_reload_assign:

; Function Attrs: nocallback nofree nosync nounwind willreturn writeonly
declare void @llvm.masked.scatter.nxv16i8.nxv16p0(<vscale x 16 x i8>, <vscale x 16 x ptr>, i32 immarg, <vscale x 16 x i1>) #0

define fastcc i8 @allocno_reload_assign() {
  br label %1

1:                                                ; preds = %1, %0
  call void @llvm.masked.scatter.nxv16i8.nxv16p0(<vscale x 16 x i8> zeroinitializer, <vscale x 16 x ptr> zeroinitializer, i32 0, <vscale x 16 x i1> xor (<vscale x 16 x i1> shufflevector (<vscale x 16 x i1> icmp eq (<vscale x 16 x ptr> insertelement (<vscale x 16 x ptr> poison, ptr null, i64 0), <vscale x 16 x ptr> zeroinitializer), <vscale x 16 x i1> poison, <vscale x 16 x i32> zeroinitializer), <vscale x 16 x i1> shufflevector (<vscale x 16 x i1> insertelement (<vscale x 16 x i1> poison, i1 true, i32 0), <vscale x 16 x i1> poison, <vscale x 16 x i32> zeroinitializer)))
  br label %1
}

; uselistorder directives
uselistorder <vscale x 16 x i1> poison, { 1, 2, 0 }

attributes #0 = { nocallback nofree nosync nounwind willreturn writeonly }
LLVM ERROR: SmallVector unable to grow. Requested capacity (4294967296) is larger than maximum value for size type (4294967295)
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ../../../../build-x/bin/llc -O3 -mcpu=neoverse-n2 issue-4803-reduced.ll
1.      Running pass 'Function Pass Manager' on module 'issue-4803-reduced.ll'.
2.      Running pass 'AArch64 Instruction Selection' on function '@allocno_reload_assign'
 #0 0x00000000039978dc llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:22
 #1 0x0000000003997c38 PrintStackTraceSignalHandler(void*) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:675:1
 #2 0x0000000003995a48 llvm::sys::RunSignalHandlers() /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/Signals.cpp:104:20
 #3 0x00000000039972b0 SignalHandler(int) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x0000ffffb8714698 (linux-vdso.so.1+0x698)
 #5 0x0000ffffb81b2200 raise (/lib64/libc.so.6+0x33200)
 #6 0x0000ffffb81b35ac abort (/lib64/libc.so.6+0x345ac)
 #7 0x00000000038f077c llvm::report_fatal_error(llvm::Twine const&, bool) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/ErrorHandling.cpp:125:9
 #8 0x000000000390a568 report_at_maximum_capacity(unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/SmallVector.cpp:77:56
 #9 0x000000000390a5f8 unsigned long getNewCapacity<unsigned int>(unsigned long, unsigned long, unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/SmallVector.cpp:102:3
#10 0x000000000390a7bc llvm::SmallVectorBase<unsigned int>::grow_pod(void*, unsigned long, unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Support/SmallVector.cpp:140:46
#11 0x0000000001a2e2f8 llvm::SmallVectorTemplateCommon<llvm::SDNode*, void>::grow_pod(unsigned long, unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/include/llvm/ADT/SmallVector.h:142:3
#12 0x0000000001a2bd9c llvm::SmallVectorTemplateBase<llvm::SDNode*, true>::grow(unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/include/llvm/ADT/SmallVector.h:529:71
#13 0x0000000001a28730 llvm::SDNode* const* llvm::SmallVectorTemplateCommon<llvm::SDNode*, void>::reserveForParamAndGetAddressImpl<llvm::SmallVectorTemplateBase<llvm::SDNode*, true>>(llvm::SmallVectorTemplateBase<llvm::SDNode*, true>*, llvm::SDNode* const&, unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/include/llvm/ADT/SmallVector.h:247:30
#14 0x0000000001a237a0 llvm::SmallVectorTemplateBase<llvm::SDNode*, true>::reserveForParamAndGetAddress(llvm::SDNode*&, unsigned long) /home/z30026696/opt/llvm/src/llvm-project/llvm/include/llvm/ADT/SmallVector.h:542:3
#15 0x0000000001a1d364 llvm::SmallVectorTemplateBase<llvm::SDNode*, true>::push_back(llvm::SDNode*) /home/z30026696/opt/llvm/src/llvm-project/llvm/include/llvm/ADT/SmallVector.h:566:14
#16 0x00000000035df55c (anonymous namespace)::DAGCombiner::AddToWorklist(llvm::SDNode*, bool) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:280:27
#17 0x00000000035df068 (anonymous namespace)::DAGCombiner::AddToWorklistWithUsers(llvm::SDNode*) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:207:5
#18 0x00000000035e3cb8 (anonymous namespace)::DAGCombiner::Run(llvm::CombineLevel) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1807:7
#19 0x000000000365ffd0 llvm::SelectionDAG::Combine(llvm::CombineLevel, llvm::AAResults*, llvm::CodeGenOpt::Level) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:27459:3
#20 0x00000000037b0f30 llvm::SelectionDAGISel::CodeGenAndEmitDAG() /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:924:61
#21 0x00000000037afc04 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&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:702:1
#22 0x00000000037b4248 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1705:33
#23 0x00000000037aebd4 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:483:7
#24 0x000000000194e594 (anonymous namespace)::AArch64DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp:57:0
#25 0x0000000002a4b8f4 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:91:33
#26 0x0000000003140a7c llvm::FPPassManager::runOnFunction(llvm::Function&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1435:40
#27 0x0000000003140c7c llvm::FPPassManager::runOnModule(llvm::Module&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:29
#28 0x0000000003141044 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1550:38
#29 0x000000000313ccfc llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:535:55
#30 0x00000000031417a4 llvm::legacy::PassManager::run(llvm::Module&) /home/z30026696/opt/llvm/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1677:17
#31 0x00000000016d9b5c compileModule(char**, llvm::LLVMContext&) /home/z30026696/opt/llvm/src/llvm-project/llvm/tools/llc/llc.cpp:759:66
#32 0x00000000016d7e2c main /home/z30026696/opt/llvm/src/llvm-project/llvm/tools/llc/llc.cpp:420:35
#33 0x0000ffffb819fbe0 __libc_start_main (/lib64/libc.so.6+0x20be0)
#34 0x00000000016d6e84 _start (../../../../build-x/bin/llc+0x16d6e84)
Aborted (core dumped)
@FLZ101
Copy link
Contributor Author

FLZ101 commented Jun 15, 2023 •
edited

I found the error "SmallVector unable to grow" is due to an infinite loop caused by legalizing & combining CONCAT_VECTORS.

t4091: nxv16i1 = concat_vectors t123, undef:nxv4i1, undef:nxv4i1, undef:nxv4i1

t4094: nxv16i1 = concat_vectors t4092, undef:nxv8i1
	t4092: nxv8i1 = concat_vectors t123, undef:nxv4i1

t4095: nxv16i1 = concat_vectors t123, undef:nxv4i1, undef:nxv4i1, undef:nxv4i1

During legalizing, t4091 is converted to t4094 and t4092. During combining, t4094 and t4092 is converted to t4095. Note that t4091 and t4095 have exactly the same form.

@FLZ101
Copy link
Contributor Author

FLZ101 commented Jun 15, 2023

The legalizing happens in AArch64TargetLowering::LowerCONCAT_VECTORS():

    // Concat each pair of subvectors and pack into the lower half of the array.
    SmallVector<SDValue> ConcatOps(Op->op_begin(), Op->op_end());
    while (ConcatOps.size() > 1) {
      for (unsigned I = 0, E = ConcatOps.size(); I != E; I += 2) {
        SDValue V1 = ConcatOps[I];
        SDValue V2 = ConcatOps[I + 1];
        EVT SubVT = V1.getValueType();
        EVT PairVT = SubVT.getDoubleNumVectorElementsVT(*DAG.getContext());
        ConcatOps[I / 2] =
            DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(Op), PairVT, V1, V2);
      }
      ConcatOps.resize(ConcatOps.size() / 2);
    }
    return ConcatOps[0];

The combining happens in DAGCombiner::visitCONCAT_VECTORS():

    // If the input is a concat_vectors, just make a larger concat by padding
    // with smaller undefs.
    if (In.getOpcode() == ISD::CONCAT_VECTORS && In.hasOneUse()) {
      unsigned NumOps = N->getNumOperands() * In.getNumOperands();
      SmallVector<SDValue, 4> Ops(In->op_begin(), In->op_end());
      Ops.resize(NumOps, DAG.getUNDEF(Ops[0].getValueType()));
      return DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(N), VT, Ops);
    }

@FLZ101
Copy link
Contributor Author

FLZ101 commented Jun 15, 2023

This issue is related to [DAG] Fold concat_vectors(concat_vectors(x,y),concat_vectors(a,b)).

@FLZ101
Copy link
Contributor Author

FLZ101 commented Jun 15, 2023 •
edited

Modifying DAGCombiner::visitCONCAT_VECTORS() as follows could fix the issue:

@@ -23167,7 +23167,8 @@ SDValue DAGCombiner::visitCONCAT_VECTORS(SDNode *N) {
 
     // If the input is a concat_vectors, just make a larger concat by padding
     // with smaller undefs.
-    if (In.getOpcode() == ISD::CONCAT_VECTORS && In.hasOneUse()) {
+    if (In.getOpcode() == ISD::CONCAT_VECTORS && In.hasOneUse() &&
+        (!In.getValueType().isScalableVector() || !LegalDAG)) {
       unsigned NumOps = N->getNumOperands() * In.getNumOperands();
       SmallVector<SDValue, 4> Ops(In->op_begin(), In->op_end());
       Ops.resize(NumOps, DAG.getUNDEF(Ops[0].getValueType()));

However I am not sure whether it is the right fix.

@EugeneZelenko EugeneZelenko added backend:AArch64 SVE ARM Scalable Vector Extensions and removed new issue labels Jun 15, 2023
@llvmbot
Copy link
Collaborator

llvmbot commented Jun 15, 2023

@llvm/issue-subscribers-backend-aarch64

@EugeneZelenko EugeneZelenko added llvm:codegen and removed backend:AArch64 SVE ARM Scalable Vector Extensions labels Jun 27, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
llvm:codegen
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@EugeneZelenko @FLZ101 @llvmbot