[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

2114

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

2114

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

2121–2127

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

2121–2127

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

2125

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

2114

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.

2142

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

2114

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

2142

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.