[InstCombine] Fix a vector-of-pointers instcombine undef bug.

[sheredom]

Summary

This commit fixes a really fun bug with inst combine where you have a
vector-of-pointers and only one element of this vector is used.
InstCombine correctly notes that an element is not used, and then will
go back through a gep into that vector-of-pointers and set all vector
elements to undef. This is fine in all cases except that the langref
(and a ton of places in the optimizer) requires that indexing into a
struct has the same index for each element of the vector-of-pointers.

To fix the bug I've just made the gep/undef propagation check that the
current type being indexed into is not a struct when doing the undef
propagation.

[spatel]

We clearly need to fix the bug (crash). @reames or someone else with more GEP experience should have a look though. I've just pointed out some minor bits to clean up.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

1177

nit: variables/parameters should (unfortunately) be capitalized, so:
i -> Index
isIndexStruct -> IsIndexStruct
?

Also, don't need to explicitly state the return type?

1193

element this -> element of this?

1206–1208

No need for braces here.

1211–1215

No need for braces here.

test/Transforms/InstCombine/vector-of-pointers.ll

1–4 ↗

(On Diff #194814)

I would prefer to put this test in the same file that D57468 used since that was where the bug was introduced:
llvm/trunk/test/Transforms/InstCombine/vec_demanded_elts.ll

Also, please use this script to automatically create/update the CHECK lines (that makes it easier to update in the future):
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py

[reames]

I think you might be overcomplicating this. I'd suggest the following:

1. scan all index types for a gep
2. run current code, but if any operand was gep, skip the recursive call on the operand

It's slightly less powerful, but correct, and easy. And frankly, optimize geps of struct types is probably rare enough we don't care.

p.s. Agreed on the location of test file, please add to existing tests.

[sheredom]

In D60600#1470778, @reames wrote:

I think you might be overcomplicating this. I'd suggest the following:

1. scan all index types for a gep
2. run current code, but if any operand was gep, skip the recursive call on the operand

It's slightly less powerful, but correct, and easy. And frankly, optimize geps of struct types is probably rare enough we don't care.

p.s. Agreed on the location of test file, please add to existing tests.

I don't really understand what your suggestion is here sorry - let me try and rephrase the suggestion and see if we agree?

1. You are saying that vector-of-pointers-to-struct is something that is rarely seen.
2. Your suggestion to fix this issue is to basically bail out of doing the get element ptr recursive simplify call if we see a vector-of-pointers-to-struct?

For 1., the reason I filed this bug is we have a bunch of code that has vector-of-pointers-to-struct, we use this to handle row-major matrices in our graphics stack. I want us to be as optimal as possible in this case, which leads me into 2. - is there any strong reason why we shouldn't do the more powerful thing here? EG. is there something intrinsically wrong/fragile with my approach that worries you going forward?

[sheredom]

Fix some review comments by @spatel

[sheredom]

@reames ping?

[spatel]

A fuzzer found what looks like the same bug in PR41624:
https://bugs.llvm.org/show_bug.cgi?id=41624

@sheredom - can you confirm? (and may want to add this minimal test to the patch for more coverage)

define i32* @PR41624(<2 x { i32, i32 }*> %a) {
  %w = getelementptr { i32, i32 }, <2 x { i32, i32 }*> %a, <2 x i64> <i64 5, i64 undef>, <2 x i32> <i32 0, i32 0>
  %r = extractelement <2 x i32*> %w, i1 0
  ret i32* %r
}

[sheredom]

@spatel yup its the same bug, and my fix fixes it to. I'll add it to my test changes.

[sheredom]

Added the extra test case that @spatel found that my change also fixes.

[reames]

In D60600#1475212, @sheredom wrote:

In D60600#1470778, @reames wrote:

I think you might be overcomplicating this. I'd suggest the following:

1. scan all index types for a gep
2. run current code, but if any operand was gep, skip the recursive call on the operand

It's slightly less powerful, but correct, and easy. And frankly, optimize geps of struct types is probably rare enough we don't care.

p.s. Agreed on the location of test file, please add to existing tests.

I don't really understand what your suggestion is here sorry - let me try and rephrase the suggestion and see if we agree?

I submitted a version along what I proposed as https://reviews.llvm.org/rL359633. Please confirm that fixes your crash. If you want to work on a better version of the fix, I'm happy to review, but I wanted to make sure the crash was resolved.

[reames]

As noted in the bug, I think the "right" fix here is to change the LangRef.

Requiring integer constant indices just based on the type being indexed seems to be a bad idea, and without some strong justification, I'd argue should simply be removed. If you want such geps to be better optimized, making hem behave like all other geps is better than special casing any particular transform. (Like this one.) To be clear, I'm suggesting allowing arbitrary constants as operands to said geps, not arbitrary values.

[sheredom]

In D60600#1485496, @reames wrote:

In D60600#1475212, @sheredom wrote:

In D60600#1470778, @reames wrote:

I think you might be overcomplicating this. I'd suggest the following:

1. scan all index types for a gep
2. run current code, but if any operand was gep, skip the recursive call on the operand

It's slightly less powerful, but correct, and easy. And frankly, optimize geps of struct types is probably rare enough we don't care.

p.s. Agreed on the location of test file, please add to existing tests.

I don't really understand what your suggestion is here sorry - let me try and rephrase the suggestion and see if we agree?

I submitted a version along what I proposed as https://reviews.llvm.org/rL359633. Please confirm that fixes your crash. If you want to work on a better version of the fix, I'm happy to review, but I wanted to make sure the crash was resolved.

I can confirm your fix does fix my crash.

I guess by 'better version of the fix' you mean relaxing the langref and dealing with the fallout? The only intermediate fix would be what this review originally proposed.

Is there any way to get the history of why the lang ref had the struct-index restriction it did? My only notion is that it is to ensure that each element of the vector-of-pointers had the same 'depth' of GEP.

[reames]

Removing self from old stale review.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
   switch (I->getOpcode()) {
   default: break;
 
   case Instruction::GetElementPtr: {
     // Conservatively track the demanded elements back through any vector
     // operands we may have.  We know there must be at least one, or we
     // wouldn't have a vector result to get here. Note that we intentionally
     // merge the undef bits here since gepping with either an undef base or
-    // index results in undef. 
-    for (unsigned i = 0; i < I->getNumOperands(); i++) {
-      if (isa<UndefValue>(I->getOperand(i))) {
+    // index results in undef.
+
+    auto simplifyGEPOperand = [&](unsigned Idx, bool IsIndexStruct) {
+      if (isa<UndefValue>(I->getOperand(Idx))) {
         // If the entire vector is undefined, just return this info.
         UndefElts = EltMask;
-        return nullptr;
+        return true;
       }
-      if (I->getOperand(i)->getType()->isVectorTy()) {
+
+      if (!IsIndexStruct && I->getOperand(Idx)->getType()->isVectorTy()) {
+        // If we have a vector of indices into a struct element of the GEP, and
+        // change a single element of this into an undef while preserving the
+        // others, that breaks the guarantee that each index of a
+        // vector-of-pointers into a struct will have the same index.
         APInt UndefEltsOp(VWidth, 0);
-        simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp);
+        simplifyAndSetOp(I, Idx, DemandedElts, UndefEltsOp);
         UndefElts |= UndefEltsOp;
       }
+
+      return false;
+    };
+
+    if (simplifyGEPOperand(0, false))
+      return nullptr;
+
+    gep_type_iterator GTI = gep_type_begin(cast<GetElementPtrInst>(I));
+    for (unsigned Idx = 1; Idx < I->getNumOperands(); Idx++, GTI++) {
+      if (simplifyGEPOperand(Idx, GTI.isStruct()))
+        return nullptr;
     }
 
     break;
   }
   case Instruction::InsertElement: {
     // If this is a variable index, we don't know which element it overwrites.
     // demand exactly the same input as we produce.
     ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
     if (!Idx) {
       // Note that we can't propagate undef elt info, because we don't know
       // which elt is getting updated.
       simplifyAndSetOp(I, 0, DemandedElts, UndefElts2);
       break;
     }
 
     // The element inserted overwrites whatever was there, so the input demanded
     // set is simpler than the output set.
     unsigned IdxNo = Idx->getZExtValue();
     APInt PreInsertDemandedElts = DemandedElts;

test/Transforms/InstCombine/vec_demanded_elts.ll

 ; CHECK-NEXT:    ret i32* undef
 ;
   %basevec = insertelement <2 x i32*> undef, i32* %base, i32 0
   %idxvec = insertelement <2 x i64> undef, i64 %idx, i32 1
   %gep = getelementptr i32, <2 x i32*> %basevec, <2 x i64> %idxvec
   %ee = extractelement <2 x i32*> %gep, i32 1
   ret i32* %ee
 }
+
+%foo = type { float, i8 }
+
+define void @gep_vector_of_pointers_to_struct(float* %out, [2 x %foo]* %in) {
+; CHECK-LABEL: @gep_vector_of_pointers_to_struct(
+; CHECK-NEXT:    [[B:%.*]] = insertelement <2 x [2 x %foo]*> undef, [2 x %foo]* [[IN:%.*]], i32 1
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [2 x %foo], <2 x [2 x %foo]*> [[B]], <2 x i64> <i64 undef, i64 0>, <2 x i64> <i64 undef, i64 1>, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[BC:%.*]] = bitcast <2 x float*> [[GEP]] to <2 x i32*>
+; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <2 x i32*> [[BC]], i64 1
+; CHECK-NEXT:    [[LOAD1:%.*]] = load i32, i32* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast float* [[OUT:%.*]] to i32*
+; CHECK-NEXT:    store i32 [[LOAD1]], i32* [[TMP2]], align 4
+; CHECK-NEXT:    ret void
+;
+  %a = insertelement <2 x [2 x %foo]*> undef, [2 x %foo]* %in, i32 0
+  %b = insertelement <2 x [2 x %foo]*> %a, [2 x %foo]* %in, i32 1
+  %gep = getelementptr [2 x %foo], <2 x [2 x %foo]*> %b, <2 x i32> zeroinitializer, <2 x i32> <i32 0, i32 1>, <2 x i32> zeroinitializer
+  %extract = extractelement <2 x float*> %gep, i64 1
+  %load = load float, float* %extract, align 4
+  store float %load, float* %out
+  ret void
+}
+
+define i32* @PR41624(<2 x { i32, i32 }*> %a) {
+; CHECK-LABEL: @PR41624(
+; CHECK-NEXT:    [[W:%.*]] = getelementptr { i32, i32 }, <2 x { i32, i32 }*> [[A:%.*]], <2 x i64> <i64 5, i64 undef>, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = extractelement <2 x i32*> [[W]], i1 false
+; CHECK-NEXT:    ret i32* [[R]]
+;
+  %w = getelementptr { i32, i32 }, <2 x { i32, i32 }*> %a, <2 x i64> <i64 5, i64 undef>, <2 x i32> <i32 0, i32 0>
+  %r = extractelement <2 x i32*> %w, i1 0
+  ret i32* %r
+}