Type legalizing emits invalid `extract_subvector` node

[lialan]

Problem

Hitting assertion:

llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:25712: llvm::SDValue narrowExtractedVectorBinOp(llvm::EVT, llvm::SDValue, unsigned int, const llvm::SDLoc &, llvm::SelectionDAG &, bool): Assertion `(Index % VT.getVectorNumElements()) == 0 && "Extract index is not a multiple of the vector length."' failed.

When compiling the attached program.

bug.txt

To reproduce:

llc --march=amdgcn ./bug.txt

confirmed that at commit 5d115e49ba70 the problem still exists.

Initial triage

Initial triage posted here: iree-org/iree#21646 (comment)

Problem is that when doing dagcombine we hit this assertion: https://github.com/llvm/llvm-project/pull/138279/files#diff-d0eb75096db76ab253fc7f8ae6343c4b4516fc619d851898cbdac1a5bf481941R25186-L25197

The culprit is this node:

t544: v32f32 = fdiv # D:1 t541, t464
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

where index 16 cannot be divided by vector length 3 -- which is a hard requirement for extract_subvector: the index must be a multiple of the minimum number of elements in the result type. Should look for the reason why v3f32 is a legalized type at this stage.

Simple problem analysis

The input program is trying to do reduction of a vector using @llvm.vector.reduce.fadd.v3f32 in a loop. The loop is unrolled. And then type legalizer turns the residual extraction:

t370: v51f32 = fdiv # D:1 t369, t12 // both operands are of type v51f32
...
t431: v3f32 = extract_subvector # D:1 t370, Constant:i32<48>

into:

t544: v32f32 = fdiv # D:1 t541, t464 // both operands are of type v32f32
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

without checking if it is possible to form a valid extract_subvector.

[llvmbot]

@llvm/issue-subscribers-backend-amdgpu

Author: Alan Li (lialan)

# Problem Hitting assertion: ```bash llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:25712: llvm::SDValue narrowExtractedVectorBinOp(llvm::EVT, llvm::SDValue, unsigned int, const llvm::SDLoc &, llvm::SelectionDAG &, bool): Assertion `(Index % VT.getVectorNumElements()) == 0 && "Extract index is not a multiple of the vector length."' failed. ```

When compiling the attached program.

bug.txt

To reproduce:

llc --march=amdgcn ./bug.txt

confirmed that at commit 5d115e49ba70 the problem still exists.

Initial triage

Initial triage posted here: iree-org/iree#21646 (comment)

> Problem is that when doing dagcombine we hit this assertion: https://github.com/llvm/llvm-project/pull/138279/files#diff-d0eb75096db76ab253fc7f8ae6343c4b4516fc619d851898cbdac1a5bf481941R25186-L25197

> The culprit is this node:

t544: v32f32 = fdiv # D:1 t541, t464
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

> where index 16 cannot be divided by vector length 3 -- which is a hard requirement for extract_subvector: the index must be a multiple of the minimum number of elements in the result type. Should look for the reason why v3f32 is a legalized type at this stage.

Simple problem analysis

The input program is trying to do reduction of a vector using @<!-- -->llvm.vector.reduce.fadd.v3f32 in a loop. The loop is unrolled. And then type legalizer turns the residual extraction:

t370: v51f32 = fdiv # D:1 t369, t12 // both operands are of type v51f32
...
t431: v3f32 = extract_subvector # D:1 t370, Constant:i32<48>

into:

t544: v32f32 = fdiv # D:1 t541, t464 // both operands are of type v32f32
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

without checking if it is possible to form a valid extract_subvector.

[llvmbot]

@llvm/issue-subscribers-bug

Author: Alan Li (lialan)

# Problem Hitting assertion: ```bash llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:25712: llvm::SDValue narrowExtractedVectorBinOp(llvm::EVT, llvm::SDValue, unsigned int, const llvm::SDLoc &, llvm::SelectionDAG &, bool): Assertion `(Index % VT.getVectorNumElements()) == 0 && "Extract index is not a multiple of the vector length."' failed. ```

When compiling the attached program.

bug.txt

To reproduce:

llc --march=amdgcn ./bug.txt

confirmed that at commit 5d115e49ba70 the problem still exists.

Initial triage

Initial triage posted here: iree-org/iree#21646 (comment)

> Problem is that when doing dagcombine we hit this assertion: https://github.com/llvm/llvm-project/pull/138279/files#diff-d0eb75096db76ab253fc7f8ae6343c4b4516fc619d851898cbdac1a5bf481941R25186-L25197

> The culprit is this node:

t544: v32f32 = fdiv # D:1 t541, t464
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

> where index 16 cannot be divided by vector length 3 -- which is a hard requirement for extract_subvector: the index must be a multiple of the minimum number of elements in the result type. Should look for the reason why v3f32 is a legalized type at this stage.

Simple problem analysis

The input program is trying to do reduction of a vector using @<!-- -->llvm.vector.reduce.fadd.v3f32 in a loop. The loop is unrolled. And then type legalizer turns the residual extraction:

t370: v51f32 = fdiv # D:1 t369, t12 // both operands are of type v51f32
...
t431: v3f32 = extract_subvector # D:1 t370, Constant:i32<48>

into:

t544: v32f32 = fdiv # D:1 t541, t464 // both operands are of type v32f32
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>

without checking if it is possible to form a valid extract_subvector.

[lialan]

Further narrowed the emitting of problematic v3f32 node down to:
DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR, where a v64f32 is split into two v32f32, where the extracting of subvector v3f32 from v64f32 index 48 is then converted into extracting of subvector of the higher part v32f32, with index 48 - 32 = 16.

[lialan]

It looks like when we split vectors we had assumptions that the size of extracted subvector length is always power-of-2, and the 3-element vector breaks the assumption.

[lialan]

Either the above issue, or the v3f32 were not legalized (into v4f32) properly when going into the operation. I think it is the type legalization issue.

[arsenm]

v3f32 extract result should be directly legal. We can implement that with a direct COPY instruction

[arsenm]

Reduced:

define void @vector_extract_assert(ptr addrspace(7) %arg0, ptr addrspace(1) %arg1) {
  %val = load <51 x float>, ptr addrspace(1) %arg1, align 4
  store <51 x float> %val, ptr addrspace(7) %arg0, align 4
  ret void
}

Plus the expansion of the buffer resource:

define void @vector_extract_assert({ ptr addrspace(8), i32 } %arg0, ptr addrspace(1) %arg1) {
  %arg0.rsrc = extractvalue { ptr addrspace(8), i32 } %arg0, 0
  %arg0.off = extractvalue { ptr addrspace(8), i32 } %arg0, 1
  %val = load <51 x float>, ptr addrspace(1) %arg1, align 4
  %val.slice.0 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.0, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.off, i32 0, i32 0)
  %arg0.part.4 = add nuw i32 %arg0.off, 16
  %val.slice.4 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 4, i32 5, i32 6, i32 7>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.4, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.4, i32 0, i32 0)
  %arg0.part.8 = add nuw i32 %arg0.off, 32
  %val.slice.8 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 8, i32 9, i32 10, i32 11>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.8, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.8, i32 0, i32 0)
  %arg0.part.12 = add nuw i32 %arg0.off, 48
  %val.slice.12 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 12, i32 13, i32 14, i32 15>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.12, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.12, i32 0, i32 0)
  %arg0.part.16 = add nuw i32 %arg0.off, 64
  %val.slice.16 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 16, i32 17, i32 18, i32 19>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.16, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.16, i32 0, i32 0)
  %arg0.part.20 = add nuw i32 %arg0.off, 80
  %val.slice.20 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 20, i32 21, i32 22, i32 23>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.20, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.20, i32 0, i32 0)
  %arg0.part.24 = add nuw i32 %arg0.off, 96
  %val.slice.24 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 24, i32 25, i32 26, i32 27>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.24, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.24, i32 0, i32 0)
  %arg0.part.28 = add nuw i32 %arg0.off, 112
  %val.slice.28 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 28, i32 29, i32 30, i32 31>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.28, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.28, i32 0, i32 0)
  %arg0.part.32 = add nuw i32 %arg0.off, 128
  %val.slice.32 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 32, i32 33, i32 34, i32 35>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.32, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.32, i32 0, i32 0)
  %arg0.part.36 = add nuw i32 %arg0.off, 144
  %val.slice.36 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 36, i32 37, i32 38, i32 39>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.36, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.36, i32 0, i32 0)
  %arg0.part.40 = add nuw i32 %arg0.off, 160
  %val.slice.40 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 40, i32 41, i32 42, i32 43>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.40, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.40, i32 0, i32 0)
  %arg0.part.44 = add nuw i32 %arg0.off, 176
  %val.slice.44 = shufflevector <51 x float> %val, <51 x float> poison, <4 x i32> <i32 44, i32 45, i32 46, i32 47>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.44, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.44, i32 0, i32 0)
  %arg0.part.48 = add nuw i32 %arg0.off, 192
  %val.slice.48 = shufflevector <51 x float> %val, <51 x float> poison, <3 x i32> <i32 48, i32 49, i32 50>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v3f32(<3 x float> %val.slice.48, ptr addrspace(8) align 4 %arg0.rsrc, i32 %arg0.part.48, i32 0, i32 0)
  ret void
}

Reduced post-expansion:

define <3 x float> @vector_extract_assert(ptr addrspace(1) %ptr) {
  %val = load <51 x float>, ptr addrspace(1) %ptr, align 4
  %val.slice.0 = shufflevector <51 x float> %val, <51 x float> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  call void @llvm.amdgcn.raw.ptr.buffer.store.v4f32(<4 x float> %val.slice.0, ptr addrspace(8) null, i32 0, i32 0, i32 0)
  %val.slice.48 = shufflevector <51 x float> %val, <51 x float> zeroinitializer, <3 x i32> <i32 48, i32 49, i32 50>
  ret <3 x float> %val.slice.48
}

[arsenm]

More manageable sized vector:

define <3 x float> @vector_extract_assert(ptr addrspace(1) %ptr) {
  %val = load <7 x float>, ptr addrspace(1) %ptr, align 4
  %extract.subvector = shufflevector <7 x float> %val, <7 x float> zeroinitializer, <3 x i32> <i32 4, i32 5, i32 6>
  ret <3 x float> %extract.subvector
}