InstructionSimplify: 'extractelement' with an undef index is undef

[zvi]

Summary

An undef extract index can be arbitrarily chosen to be an
out-of-range index value, which would result in the instruction being undef.

This change closes a gap identified while working on lowering vector permute intrinsics
with variable index vectors to pure LLVM IR.

[zvi]

Hi @arsenm,

With this patch i am seeing failures in test/CodeGen/AMDGPU/indirect-addressing-si.ll . This test include extractelement instructions with undef indices, which is what this patch targets. I would appreciate your help with advice on how we can modify these tests so that they can be used safely. Please bear in mind that i have no knowledge of the AMDGPU backend.

Thanks, Zvi

[arsenm]

In D40231#929842, @zvi wrote:

Hi @arsenm,

With this patch i am seeing failures in test/CodeGen/AMDGPU/indirect-addressing-si.ll . This test include extractelement instructions with undef indices, which is what this patch targets. I would appreciate your help with advice on how we can modify these tests so that they can be used safely. Please bear in mind that i have no knowledge of the AMDGPU backend.

Thanks, Zvi

I think the point of the tests was to make sure we don't hit use of undefined register errors when it's expanded . I don't think InstructionSimplify is guaranteed during codegen, so it would be nice if there was still a way to get an undef index through codegen.

[zvi]

One option is to run llc with -O0 which will disable passes which use InstructionSimplify, but this will require changing the CHECK's to expect different generated code. If the purpose of the test is to not crash in the Verifier, are the CHECK's needed?

[arsenm]

In D40231#931175, @zvi wrote:

One option is to run llc with -O0 which will disable passes which use InstructionSimplify, but this will require changing the CHECK's to expect different generated code. If the purpose of the test is to not crash in the Verifier, are the CHECK's needed?

The checks probably aren't needed, but if this is eliminated in the IR the test isn't reaching the point it needs to. Is there another way to sneak an undef index in? i.e. some sequence that will fold to undef in the DAG that InstructionSimplify won't catch

[spatel]

In D40231#936224, @arsenm wrote:

In D40231#931175, @zvi wrote:

One option is to run llc with -O0 which will disable passes which use InstructionSimplify, but this will require changing the CHECK's to expect different generated code. If the purpose of the test is to not crash in the Verifier, are the CHECK's needed?

The checks probably aren't needed, but if this is eliminated in the IR the test isn't reaching the point it needs to. Is there another way to sneak an undef index in? i.e. some sequence that will fold to undef in the DAG that InstructionSimplify won't catch

Even if we find a loophole in InstSimplify, I think that would be a fragile solution (InstSimplify could get smarter and break the tests again). This could bite us again in the near future because over in D40390, I've suggested adding another simplification for 'insertelement' with an out-of-range index, and indirect-addressing-si.ll has tests that appear to rely on that not folding as well?

Running with -O0 seems like a good option here. Note that there's already a indirect-addressing-si-noopt.ll test file with a FIXME comment:

; FIXME: Merge into indirect-addressing-si.ll

...but maybe we should rearrange the tests so that things that are relying on undef are in that file?

[zvi]

Following Sanjay's suggestion, moving test-case from indirect-addressing-si.ll to indirect-addressing-si-noopt.ll.
If this looks ok i will commit the changes to these tests in a separate commit.

[arsenm]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

The checks were still dropped. Does -O0 prevent the inst simplify?

I really wish llc ran no IR optimizations, but we're stuck working around it

[zvi]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

llc -O0 should be running only IR passes required for functionality, so if InstSimplify is invoked, i would consider it as a bug.

[spatel]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

I was curious how we get here, so I can confirm that -O0 prevents the instsimplify. Instsimplification is being invoked via early-cse which is being added by AMDGPUPassConfig::addEarlyCSEOrGVNPass(). It should be easy enough to add a cl::opt to customize that, but I don't think we should require that for this instsimplify patch to proceed.

[zvi]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

If the test is intended to cover post-isel handling of undef operands, consider replacing with a .mir test.

[spatel]

LGTM. We have at least 2 suggestions to improve the AMDGPU tests, but we shouldn't need to hold up this patch for that fix.

[arsenm]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

A MIR test doesn't make sense because this is supposed to test the initial MIR emission

[arsenm]

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

24

It looks like that is disabled for -O0, and I would expect the check lines to work as-is for -O0

[zvi]

Preseve migrated test-case's CHECK:'s which as @arnsenm pointed out can used as-is for -O0.

[arsenm]

LGTM

[zvi]

Final rebase

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &,
   }
 
   // If extracting a specified index from the vector, see if we can recursively
   // find a previously computed scalar that was inserted into the vector.
   if (auto *IdxC = dyn_cast<ConstantInt>(Idx))
     if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue()))
       return Elt;
 
+  // An undef extract index can be arbitrarily chosen to be an out-of-range
+  // index value, which would result in the instruction being undef.
+  if (isa<UndefValue>(Idx))
+    return UndefValue::get(Vec->getType()->getVectorElementType());
+
   return nullptr;
 }
 
 Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx,
                                         const SimplifyQuery &Q) {
   return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit);
 }
 

test/CodeGen/AMDGPU/indirect-addressing-si-noopt.ll

 ; CHECK-NEXT: buffer_store_dwordx4 v{{\[}}[[ELT0]]:
 define amdgpu_kernel void @insert_wo_offset(<4 x float> addrspace(1)* %out, i32 %in) {
 entry:
   %ins = insertelement <4 x float> <float 1.0, float 2.0, float 3.0, float 4.0>, float 5.0, i32 %in
   store <4 x float> %ins, <4 x float> addrspace(1)* %out
   ret void
 }
 
+; Make sure we don't hit use of undefined register errors when expanding an
+; extract with undef index.
+
+; CHECK-LABEL: {{^}}extract_adjacent_blocks:
+; CHECK: s_load_dword [[ARG:s[0-9]+]]
+; CHECK: s_cmp_lg_u32
+; CHECK: s_cbranch_scc1 [[BB4:BB[0-9]+_[0-9]+]]
+
+; CHECK: buffer_load_dwordx4
+; CHECK: s_mov_b32 m0,
+; CHECK: v_movrels_b32_e32
+
+; CHECK: s_branch [[ENDBB:BB[0-9]+_[0-9]+]]
+
+; CHECK: [[BB4]]:
+; CHECK: buffer_load_dwordx4
+; CHECK: s_mov_b32 m0,
+; CHECK: v_movrels_b32_e32
+
+; CHECK: [[ENDBB]]:
+; CHECK: buffer_store_dword
+; CHECK: s_endpgm
+
+define amdgpu_kernel void @extract_adjacent_blocks(i32 %arg) #0 {
+bb:
+  %tmp = icmp eq i32 %arg, 0
+  br i1 %tmp, label %bb1, label %bb4
+
+bb1:
+  %tmp2 = load volatile <4 x float>, <4 x float> addrspace(1)* undef
+  %tmp3 = extractelement <4 x float> %tmp2, i32 undef
+  call void asm sideeffect "; reg use $0", "v"(<4 x float> %tmp2) #0 ; Prevent block optimize out
+  br label %bb7
+
+bb4:
+  %tmp5 = load volatile <4 x float>, <4 x float> addrspace(1)* undef
+  %tmp6 = extractelement <4 x float> %tmp5, i32 undef
+  call void asm sideeffect "; reg use $0", "v"(<4 x float> %tmp5) #0 ; Prevent block optimize out
+  br label %bb7
+
+bb7:
+  %tmp8 = phi float [ %tmp3, %bb1 ], [ %tmp6, %bb4 ]
+  store volatile float %tmp8, float addrspace(1)* undef
+  ret void
+}

test/CodeGen/AMDGPU/indirect-addressing-si.ll

 bb1:
   store volatile i32 %live.out.val, i32 addrspace(1)* undef
   br label %bb2
 
 bb2:
   ret void
 }
 
-; GCN-LABEL: {{^}}extract_adjacent_blocks:
-; GCN: s_load_dword [[ARG:s[0-9]+]]
-; GCN: s_cmp_lg_u32
-; GCN: s_cbranch_scc0 [[BB4:BB[0-9]+_[0-9]+]]
-
-; GCN: buffer_load_dwordx4
-; MOVREL: s_mov_b32 m0,
-; MOVREL: v_movrels_b32_e32
-
-; IDXMODE: s_set_gpr_idx_on s{{[0-9]+}}, src0
-; IDXMODE: v_mov_b32_e32
-; IDXMODE: s_set_gpr_idx_off
-
-; GCN: s_branch [[ENDBB:BB[0-9]+_[0-9]+]]
-
-; GCN: [[BB4]]:
-; GCN: buffer_load_dwordx4
-; MOVREL: s_mov_b32 m0,
-; MOVREL: v_movrels_b32_e32
-
-; IDXMODE: s_set_gpr_idx_on
-; IDXMODE: v_mov_b32_e32
-; IDXMODE: s_set_gpr_idx_off
-
-; GCN: [[ENDBB]]:
-; GCN: buffer_store_dword
-; GCN: s_endpgm
-define amdgpu_kernel void @extract_adjacent_blocks(i32 %arg) #0 {
-bb:
-  %tmp = icmp eq i32 %arg, 0
-  br i1 %tmp, label %bb1, label %bb4
-
-bb1:
-  %tmp2 = load volatile <4 x float>, <4 x float> addrspace(1)* undef
-  %tmp3 = extractelement <4 x float> %tmp2, i32 undef
-  call void asm sideeffect "; reg use $0", "v"(<4 x float> %tmp2) #0 ; Prevent block optimize out
-  br label %bb7
-
-bb4:
-  %tmp5 = load volatile <4 x float>, <4 x float> addrspace(1)* undef
-  %tmp6 = extractelement <4 x float> %tmp5, i32 undef
-  call void asm sideeffect "; reg use $0", "v"(<4 x float> %tmp5) #0 ; Prevent block optimize out
-  br label %bb7
-
-bb7:
-  %tmp8 = phi float [ %tmp3, %bb1 ], [ %tmp6, %bb4 ]
-  store volatile float %tmp8, float addrspace(1)* undef
-  ret void
-}
 
 ; GCN-LABEL: {{^}}insert_adjacent_blocks:
 ; GCN: s_load_dword [[ARG:s[0-9]+]]
 ; GCN: s_cmp_lg_u32
 ; GCN: s_cbranch_scc0 [[BB4:BB[0-9]+_[0-9]+]]
 
 ; GCN: buffer_load_dwordx4
 ; MOVREL: s_mov_b32 m0,

test/Transforms/InstSimplify/2011-09-05-InsertExtractValue.ll

define i8 @test4(<8 x i8> %V) {
   %add     = add <8 x i8> %V, bitcast (double 0x319BEB8FD172E36 to <8 x i8>)
   %extract = extractelement <8 x i8> %add, i32 6
   ret i8 %extract
 ; CHECK-LABEL: @test4(
 ; CHECK: %[[add:.*]] = add <8 x i8> %V, bitcast (<1 x double> <double 0x319BEB8FD172E36> to <8 x i8>)
 ; CHECK-NEXT: %[[extract:.*]] = extractelement <8 x i8> %[[add]], i32 6
 ; CHECK-NEXT: ret i8 %[[extract]]
 }
+
+define i32 @test5(<4 x i32> %V) {
+  %extract = extractelement <4 x i32> %V, i32 undef
+  ret i32 %extract
+}
+; CHECK-LABEL: @test5(
+; CHECK: ret i32 undef