[InstCombine] Combine opaque pointer single index GEP and with src GEP by matching the types

[skc7]

Summary

Removing zero indices opaque pointer gep, link, has caused Instcombine pass to not combine few GepOfGep instructions which were previously possible for non-opaque pointers case.

Consider below IR : link

@ext = external hidden global [2 x [1 x float]]
%a = getelementptr inbounds [2 x [1 x float]], [2 x [1 x float]]* @ext, i64 0, i64 %c
%b = getelementptr inbounds [1 x float], [1 x float]* %a, i64 0, i64 0 
%c = getelementptr inbounds float, float* %b, i64 %in1

would be optimized to

%c = getelementptr inbounds [2 x [1 x float]], [2 x [1 x float]]* @ext, i64 0, i64 %c, i64 %in1

This is currently not happening for opaque pointer case. link

This patch tries to address this issue by combining single index gep with src gep.

[skc7]

Rebase.

[skc7]

Rebase.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2119

Do we need an explicit PtrTy->isOpaquePointerTy() check?
Do we need an one-use check on the inner (Src) gep?
Do we want to perform the same LICM-appeasing checks about their loop disposition?

llvm/test/Transforms/InstCombine/opaque-ptr-gep-of-gep.ll

2

Is explicit -opaque-pointers needed?
Just write the test to not have typed pointers to begin with.

7

It isn't obvious how these tests differ from each other.
They could use a comments.

[skc7]

Added comments to tests.

[skc7]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2119

With new changes of making opaque pointer all-zero index gep as no-op lead to these GepOfGep not getting combined. So this change is specific to opaque pointers.

Src gep can have multiple users which can be geps. This patch tries to optimize them aswell. See gepofgep4 test added below.

I'm not sure about LICM checks are required here. Please let me know if this change would cause any issue with that? I would work on fixing it.

[jmmartinez]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2126–2132

What do you think about doing the following ?

Instruction *GEP = GetElementPtrInst::Create(Src->getSourceElementType(), Src->getOperand(0), NewIndices, GEP.getName());
GEP->setIsInBounds(IsInBounds);
return GEP;

[skc7]

Update code as per @jmmartinez comments.

[skc7]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2126–2132

Updated. There were previous methods in instcombine pass using specifically GetElementPtrInst::CreateInBounds. I guess, creating GEP instruction and then setting InBounds is fine.

[nikic]

I think in terms of general approach, the better way to handle this would be to relax the Src->getResultElementType() != GEP.getSourceElementType() check to allow the transform if the types can be made to match by adding additional zero indices.

(As a meta note, I think we'd probably be better off considering GEPs with multiple dynamic indices to be non-canonical, and try to split them up instead, e.g. because this allows LICM of an invariant part. But I guess that's not our current stance. It would be interesting to hear where you have found this merging to be beneficial.)

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2130

I believe this is missing a check that the GEP source element type matches the array element type of the Src result element type. Your current code would allow combining [1 x float] and double GEPs.

[skc7]

Thanks @nikic for feedback. Made changes to match Src ResultElementType with GEP SrcElementType by adding additional zero indices to Src gep.

[skc7]

Rebase.

[skc7]

Rebase. Use -passes=instcombine in test.

[skc7]

Rebase. Ping

[skc7]

In D138637#3970359, @nikic wrote:

I think in terms of general approach, the better way to handle this would be to relax the Src->getResultElementType() != GEP.getSourceElementType() check to allow the transform if the types can be made to match by adding additional zero indices.

(As a meta note, I think we'd probably be better off considering GEPs with multiple dynamic indices to be non-canonical, and try to split them up instead, e.g. because this allows LICM of an invariant part. But I guess that's not our current stance. It would be interesting to hear where you have found this merging to be beneficial.)

Hi @nikic I have updated the patch to match the types by adding additional zero indices. Please review.

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2119

The Src->getResultElementType()->isArrayTy() check here is overly strict. Consider that the result type is something like { [0 x float] }. This can be handled the same way as [0 x float] with an extra zero index (which you do already handle, if this check is dropped).

Src gep can have multiple users which can be geps. This patch tries to optimize them aswell. See gepofgep4 test added below.

Hm, it looks like the existing transform does allow GEPs with multiple uses here, but this seems like a bug to me, because this means that we will end up repeating non-trivial address calculations, rather than performing them only once.

2147

Don't we need to only drop the last zero from NewIndices? Consider something like getelementptr [3 x [2 x [1 x float]]], ptr %p, i64 %x followed by getelementptr float, ptr %gep, i64 %y. I think your current code will convert this into getelementptr [3 x [2 x [1 x float]]], ptr %p, i64 %x, i64 %y, while the correct result would be getelementptr [3 x [2 x [1 x float]]], ptr %p, i64 %x, i64 0, i64 %y.

llvm/test/Transforms/InstCombine/opaque-ptr-gep-of-gep.ll

2

The triple can be dropped here. Please also use update_test_checks.py to generate check lines.

[skc7]

Remove check for src array type.
Drop last zero from resulting NewIndices after matching the types.
Drop triple from test. Updated test checks with update_test_checks.py.
Added new tests for struct of array type and to check new zero index in resulting gep.

[skc7]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2119

Previously with non-opaque pointer case aswell, GEPs with multiple uses were optimized. Will there be any issue if we do so now with opaque pointers case ?
example with non opaque pointers and multiple uses case : https://llvm.godbolt.org/z/oEGE3736f

[skc7]

Rebase

[skc7]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2147

Hi @nikic. I have made the changes to check if zeroes have been appended to NewIndices after types matching and if so, last zero will be erased and then GEP indices will be appended. Please review.

[skc7]

Rebase. Ping

[skc7]

Rebase

[skc7]

Hi @nikic. I have made the changes that were suggested previously. Could you please review?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

return IsInBounds
                ? GetElementPtrInst::CreateInBounds(Src->getSourceElementType(),
                                                    Src->getOperand(0), Indices,
                                                    GEP.getName())
                : GetElementPtrInst::Create(Src->getSourceElementType(),
                                            Src->getOperand(0), Indices,
                                            GEP.getName());
   }
 
+  // Combine opaque pointer GEPs with GEP having single index and by matching
+  // the types.
+  if (PtrTy->isOpaquePointerTy() &&
+      Src->getResultElementType() != GEP.getSourceElementType() &&
+      GEP.getNumIndices() == 1) {
+    Type *SrcElemTy = GEP.getSourceElementType();
+    Type *ResElemTy = Src->getResultElementType();
+    Type *ElemTy = ResElemTy;
+    SmallVector<Value *, 16> NewIndices;
+    NewIndices.append(Src->idx_begin(), Src->idx_end());
+    Type *IntIdxTy = DL.getIndexType(PtrTy);
+    unsigned BitWidth = DL.getTypeSizeInBits(IntIdxTy);
+    auto *Zero =
+        ConstantInt::get(Type::getIntNTy(Src->getContext(), BitWidth), 0);
+
+    // Try to add additional zero indices to Src to make the
+    // Src ResultElementType match with GEP SourceElementType
+    while (ElemTy != SrcElemTy) {
+      Type *NextTy = GetElementPtrInst::getTypeAtIndex(ElemTy, (uint64_t)0);
+      if (!NextTy)
+        break;
+      NewIndices.push_back(Zero);
+      ElemTy = NextTy;
+    }
+
+    // Combine the two Geps if Src ResultElementType now
+    // matches with GEP SourceElementType.
+    if (ElemTy == SrcElemTy) {
+      // Erase the last zero from NewIndices if zeroes have been appended by
+      // previous step.
+      if (NewIndices.size() > Src->getNumIndices())
+        NewIndices.erase(NewIndices.end() - 1);
+      NewIndices.append(GEP.idx_begin(), GEP.idx_end());
+      bool IsInBounds = isMergedGEPInBounds(*Src, *cast<GEPOperator>(&GEP));
+      GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
+          Src->getSourceElementType(), Src->getOperand(0), NewIndices,
+          GEP.getName());
+      NewGEP->setIsInBounds(IsInBounds);
+      return NewGEP;
+    }
+  }
+
   if (Src->getResultElementType() != GEP.getSourceElementType())
     return nullptr;
 
   SmallVector<Value*, 8> Indices;
 
   // Find out whether the last index in the source GEP is a sequential idx.
   bool EndsWithSequential = false;
   for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src);

llvm/test/Transforms/InstCombine/opaque-ptr-gep-of-gep.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=instcombine %s | FileCheck %s
+
+@ext1 = external hidden global [2 x [1 x float]]
+@ext2 = external hidden global [2 x [2 x [1 x float]]]
+@ext3 = external hidden global { [2 x [1 x float]] }
+@ext4 = external hidden global [3 x [2 x [1 x float]]]
+
+; Test to check if instcombine pass combines opaque pointer gepofgep with src array type
+; and current gep having single index.
+define void @gepofgep1(i64 %in1, i64 %in2, ptr %out) {
+; CHECK-LABEL: @gepofgep1(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [2 x [1 x float]], ptr @ext1, i64 0, i64 [[IN1:%.*]], i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [2 x [1 x float]], ptr @ext1, i64 0, i64 %in1
+  %b = getelementptr inbounds float, ptr %a, i64 %in2
+  store ptr %b, ptr %out
+  ret void
+}
+
+; Test to check if instcombine pass doesn't combine opaque pointer gepofgep with src array type
+; and current gep having more than one index.
+define void @gepofgep2(i64 %in1, i64 %in2, ptr %out) {
+; CHECK-LABEL: @gepofgep2(
+; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [2 x [2 x [1 x float]]], ptr @ext2, i64 0, i64 [[IN1:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [1 x float], ptr [[A]], i64 0, i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [2 x [2 x [1 x float]]], ptr @ext2, i64 0, i64 %in1
+  %b = getelementptr inbounds [1 x float], ptr %a, i64 0, i64 %in2
+  store ptr %b, ptr %out
+  ret void
+}
+
+; Test to check if instcombine pass combines opaque pointer gepofgep with src of higher dimension array type
+; and current gep having single index.
+define void @gepofgep3(i64 %in1, i64 %in2, ptr %out) {
+; CHECK-LABEL: @gepofgep3(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [2 x [2 x [1 x float]]], ptr @ext2, i64 [[IN1:%.*]], i64 0, i64 0, i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [2 x [2 x [1 x float]]], ptr @ext2, i64 %in1
+  %b = getelementptr inbounds float, ptr %a, i64 %in2
+  store ptr %b, ptr %out
+  ret void
+}
+
+; Test to check if instcombine pass combines opaque pointer gepofgep with src of array type having more than one user
+; and current gep having single index.
+define void @gepofgep4(i64 %in1, i64 %in2, ptr %out1, ptr %out2) {
+; CHECK-LABEL: @gepofgep4(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [2 x [1 x float]], ptr @ext1, i64 0, i64 [[IN1:%.*]], i64 [[IN1]]
+; CHECK-NEXT:    [[C:%.*]] = getelementptr inbounds [2 x [1 x float]], ptr @ext1, i64 0, i64 [[IN1]], i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT1:%.*]], align 8
+; CHECK-NEXT:    store ptr [[C]], ptr [[OUT2:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [2 x [1 x float]], ptr @ext1, i64 0, i64 %in1
+  %b = getelementptr inbounds float, ptr %a, i64 %in1
+  %c = getelementptr inbounds float, ptr %a, i64 %in2
+  store ptr %b, ptr %out1
+  store ptr %c, ptr %out2
+  ret void
+}
+
+; Test to check if instcombine pass combines opaque pointer gepofgep with src of struct type with array inside and
+; current gep having single index.
+define void @gepofgep5(i64 %in1, i64 %in2, ptr %out) {
+; CHECK-LABEL: @gepofgep5(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [2 x [1 x float]], ptr @ext3, i64 0, i64 [[IN1:%.*]], i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [2 x [1 x float]], ptr @ext3, i64 0, i64 %in1
+  %b = getelementptr inbounds float, ptr %a, i64 %in2
+  store ptr %b, ptr %out
+  ret void
+}
+
+; Test to check if instcombine pass combines opaque pointer gepofgep with src array type
+; and current gep having single index. Check if resulting gep has additional zero after src indices.
+define void @gepofgep6(i64 %in1, i64 %in2, ptr %out) {
+; CHECK-LABEL: @gepofgep6(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [3 x [2 x [1 x float]]], ptr @ext4, i64 0, i64 [[IN1:%.*]], i64 0, i64 [[IN2:%.*]]
+; CHECK-NEXT:    store ptr [[B]], ptr [[OUT:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %a = getelementptr inbounds [3 x [2 x [1 x float]]], ptr @ext4, i64 0, i64 %in1
+  %b = getelementptr inbounds float, ptr %a, i64 %in2
+  store ptr %b, ptr %out
+  ret void
+}