diff --git a/llvm/test/Transforms/InstCombine/gep-canonicalize-constant-indices.ll b/llvm/test/Transforms/InstCombine/gep-canonicalize-constant-indices.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/gep-canonicalize-constant-indices.ll @@ -0,0 +1,127 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=instcombine -opaque-pointers -S | FileCheck %s + +; Constant-indexed GEP instructions in a chain of GEP instructions should be +; swapped to the end whenever such transformation is valid. This allows them to +; be merged. + +declare void @use(i1) + + +; The constant-indexed GEP instruction should be swapped to the end, even +; without merging. +; result = (((i32*) p + a) + b) + 1 +define ptr @basic(ptr %p, i64 %a, i64 %b) { +; CHECK-LABEL: @basic( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 [[A:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[TMP2]], i64 [[B:%.*]] +; CHECK-NEXT: ret ptr [[TMP3]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds i32, ptr %1, i64 %a + %3 = getelementptr inbounds i32, ptr %2, i64 %b + ret ptr %3 +} + +; GEP with the last index being a constant should also be swapped. +define ptr @partialConstant1(ptr %p, i64 %a, i64 %b) { +; CHECK-LABEL: @partialConstant1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[B:%.*]] +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds [4 x i32], ptr %p, i64 %a, i64 1 + %2 = getelementptr inbounds i32, ptr %p, i64 %b + ret ptr %2 +} + +; Negative test. GEP should not be swapped if the last index is not a constant. +define ptr @partialConstant2(ptr %p, i64 %a, i64 %b) { +; CHECK-LABEL: @partialConstant2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[B:%.*]] +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds [4 x i32], ptr %p, i64 1, i64 %a + %2 = getelementptr inbounds i32, ptr %p, i64 %b + ret ptr %2 +} + +; Constant-indexed GEP are merged after swawpping. +; result = ((i32*) p + a) + 3 +define ptr @merge(ptr %p, i64 %a) { +; CHECK-LABEL: @merge( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 [[A:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[TMP2]], i64 2 +; CHECK-NEXT: ret ptr [[TMP3]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds i32, ptr %1, i64 %a + %3 = getelementptr inbounds i32, ptr %2, i64 2 + ret ptr %3 +} + +; Multiple constant-indexed GEP. Note that the first two cannot be merged at +; first, but after the second and third are merged, the result can be merged +; with the first one on the next pass. +; result = (<3 x i32>*) ((i16*) ((i8*) ptr + a) + (a * b)) + 9 +define ptr @nested(ptr %p, i64 %a, i64 %b) { +; CHECK-LABEL: @nested( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds <3 x i32>, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i8, ptr [[TMP1]], i64 [[A:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[A]], [[B:%.*]] +; CHECK-NEXT: [[TMP4:%.*]] = getelementptr inbounds <5 x i32>, ptr [[TMP2]], i64 4 +; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i16, ptr [[TMP4]], i64 [[TMP3]] +; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds <4 x i32>, ptr [[TMP5]], i64 1 +; CHECK-NEXT: ret ptr [[TMP6]] +; + %1 = getelementptr inbounds <3 x i32>, ptr %p, i64 1 + %2 = getelementptr inbounds i8, ptr %1, i64 %a + %3 = mul i64 %a, %b + %4 = getelementptr inbounds <5 x i32>, ptr %2, i64 4 + %5 = getelementptr inbounds i16, ptr %4, i64 %3 + %6 = getelementptr inbounds <4 x i32>, ptr %5, i64 1 + ret ptr %6 +} + +; It is valid to swap if the source operand of the first GEP has multiple uses. +define ptr @multipleUses1(ptr %p) { +; CHECK-LABEL: @multipleUses1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = ptrtoint ptr [[P]] to i64 +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 [[TMP2]] +; CHECK-NEXT: ret ptr [[TMP3]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = ptrtoint ptr %p to i64 + %3 = getelementptr inbounds i32, ptr %1, i64 %2 + ret ptr %3 +} + +; It is valid to swap if the second GEP has multiple uses. +define ptr @multipleUses2(ptr %p, i64 %a) { +; CHECK-LABEL: @multipleUses2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 [[A:%.*]] +; CHECK-NEXT: call void @use(ptr nonnull [[TMP2]]) +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds i32, ptr %1, i64 %a + call void @use(ptr %2) + ret ptr %2 +} + +; Negative test. It is not valid to swap if the first GEP has multiple uses. +define ptr @multipleUses3(ptr %p) { +; CHECK-LABEL: @multipleUses3( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = ptrtoint ptr [[TMP1]] to i64 +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 [[TMP2]] +; CHECK-NEXT: ret ptr [[TMP3]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = ptrtoint ptr %1 to i64 + %3 = getelementptr inbounds i32, ptr %1, i64 %2 + ret ptr %3 +} diff --git a/llvm/test/Transforms/InstCombine/gep-merge-constant-indices.ll b/llvm/test/Transforms/InstCombine/gep-merge-constant-indices.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/gep-merge-constant-indices.ll @@ -0,0 +1,285 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=instcombine -opaque-pointers -S | FileCheck %s + +; Test merging GEP of GEP with constant indices. + +target datalayout = "i24:8:8" + +%struct.A = type { [123 x i8], i32 } +%struct.B = type { i8, [3 x i16], %struct.A, float } +%struct.C = type { i8, i32, i32 } + +; result = (i32*) p + 3 +define ptr @mergeBasic(ptr %p) { +; CHECK-LABEL: @mergeBasic( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 3 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds i32, ptr %1, i64 2 + ret ptr %2 +} + +; First GEP is merged into the second. +; result = (i8*) p + 10 +define ptr @mergeDifferentTypes(ptr %p) { +; CHECK-LABEL: @mergeDifferentTypes( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i8, ptr [[P:%.*]], i64 10 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds i8, ptr %p, i64 2 + %2 = getelementptr inbounds i64, ptr %1, i64 1 + ret ptr %2 +} + +; Second GEP is merged into the first. +; result = (i8*) p + 10 +define ptr @mergeReverse(ptr %p) { +; CHECK-LABEL: @mergeReverse( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i8, ptr [[TMP1]], i64 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 1 + %2 = getelementptr inbounds i8, ptr %1, i64 2 + ret ptr %2 +} + +; Offsets of first and last GEP cancel out. +; result = p +define ptr @zeroSum(ptr %p) { +; CHECK-LABEL: @zeroSum( +; CHECK-NEXT: ret ptr [[P:%.*]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds i8, ptr %1, i64 -4 + ret ptr %2 +} + +; result = (i8*) (([20 x i8]*) p + 1) + 17 +define ptr @array1(ptr %p) { +; CHECK-LABEL: @array1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds [20 x i8], ptr [[P:%.*]], i64 1, i64 17 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds [20 x i8], ptr %p, i64 1, i64 1 + %2 = getelementptr inbounds i64, ptr %1, i64 2 + ret ptr %2 +} + +; result = (i8*) p + 14 +define ptr @array2(ptr %p, i64 %a) { +; CHECK-LABEL: @array2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds [7 x i32], ptr [[P:%.*]], i64 0, i64 3 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i8, ptr [[TMP1]], i64 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds [7 x i32], ptr %p, i64 0, i64 3 + %2 = getelementptr inbounds i8, ptr %1, i64 2 + ret ptr %2 +} + +; result = (i8*) (([3 x i8]*) p + 6) + 2 +define ptr @array3(ptr %p) { +; CHECK-LABEL: @array3( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 2 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [3 x i8], ptr [[TMP1]], i64 1, i64 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 2 + %2 = getelementptr inbounds [3 x i8], ptr %1, i64 1, i64 1 + ret ptr %2 +} + +; result = (struct.C*) p + 3 +define ptr @struct1(ptr %p) { +; CHECK-LABEL: @struct1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 3 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 3 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 1 + ret ptr %2 +} + +; result = &((struct.A*) p - 1).member1 +define ptr @struct2(ptr %p) { +; CHECK-LABEL: @struct2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds [[STRUCT_A:%.*]], ptr [[P:%.*]], i64 -1, i32 1 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds %struct.A, ptr %p, i64 0, i32 1 + %2 = getelementptr inbounds i8, ptr %1, i64 -128 + ret ptr %2 +} + +; result = (i8*) p - 4 +define ptr @struct3(ptr %p, i64 %a) { +; CHECK-LABEL: @struct3( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i8, ptr [[P:%.*]], i64 -4 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds i8, ptr %p, i64 -128 + %2 = getelementptr inbounds %struct.A, ptr %1, i64 0, i32 1 + ret ptr %2 +} +; result = ((struct.C*) p + 1).member2 +define ptr @struct4(ptr %p, i64 %a) { +; CHECK-LABEL: @struct4( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 1 + ret ptr %2 +} + +; result = (i8*) &((struct.B) p)[0].member2.member0 + 7 +define ptr @structStruct(ptr %p) { +; CHECK-LABEL: @structStruct( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds [[STRUCT_B:%.*]], ptr [[P:%.*]], i64 0, i32 2, i32 0, i64 7 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds %struct.B, ptr %p, i64 0, i32 2, i32 0, i64 3 + %2 = getelementptr inbounds %struct.A, ptr %1, i64 0, i32 0, i64 4 + ret ptr %2 +} + +; First GEP offset is not divisible by last GEP's source element size, but first +; GEP points to an array such that the last GEP offset is divisible by the +; array's element size, so the first GEP can be rewritten with an extra index. +; result = (i16*) &((struct.B*) p)[0].member1 + 2 +define ptr @appendIndex(ptr %p) { +; CHECK-LABEL: @appendIndex( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds [[STRUCT_B:%.*]], ptr [[P:%.*]], i64 0, i32 1, i64 2 +; CHECK-NEXT: ret ptr [[TMP1]] +; + %1 = getelementptr inbounds %struct.B, ptr %p, i64 0, i32 1 + %2 = getelementptr inbounds i32, ptr %1, i64 1 + ret ptr %2 +} + +; result = (i8*) &((struct.A*) &((struct.B*) p)[0].member2).member0 + 2 +define ptr @appendIndexReverse(ptr %p) { +; CHECK-LABEL: @appendIndexReverse( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_B:%.*]], ptr [[TMP1]], i64 0, i32 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.B, ptr %1, i64 0, i32 1 + ret ptr %2 +} + +; Constant-indexed GEP can be merged if the sum of offsets aliases a member's +; address of one of the GEP instructions. +; result = &((struct.C*) p + 2).member1 +define ptr @structMemberAliasing(ptr %p, i64 %a) { +; CHECK-LABEL: @structMemberAliasing( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 1, i32 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i64, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 1, i32 2 + ret ptr %2 +} + +; Negative test. Offset of either GEP is not divisible by the other's size. +; Here i24 is 8-bit aligned. +define ptr @notDivisible(ptr %p) { +; CHECK-LABEL: @notDivisible( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i24, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[TMP1]], i64 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i24, ptr %p, i64 1 + %2 = getelementptr inbounds i32, ptr %1, i64 1 + ret ptr %2 +} + +; Two GEP instructions can be merged if one is constant-indexed and the other +; is a sequential type with a constant last index, and the constant offset is +; divisible by the sequential type size. +; result = (i32*) (([4 x i32]*) p + a) + 3 +define ptr @partialConstant1(ptr %p, i64 %a) { +; CHECK-LABEL: @partialConstant1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [4 x i32], ptr [[TMP1]], i64 [[A:%.*]], i64 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds [4 x i32], ptr %1, i64 %a, i64 2 + ret ptr %2 +} + +; Negative test. Similar to above, but two GEP should not be merged if the +; constant offset is not divisible. +define ptr @partialConstant2(ptr %p, i64 %a) { +; CHECK-LABEL: @partialConstant2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [4 x i64], ptr [[TMP1]], i64 [[A:%.*]], i64 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds [4 x i64], ptr %1, i64 %a, i64 2 + ret ptr %2 +} + +; Negative test. Similar to above, but two GEP should not be merged if there is +; another use of the first GEP by the second GEP. +define ptr @partialConstant3(ptr %p) { +; CHECK-LABEL: @partialConstant3( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = ptrtoint ptr [[TMP1]] to i64 +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds [4 x i64], ptr [[TMP1]], i64 [[TMP2]], i64 2 +; CHECK-NEXT: ret ptr [[TMP3]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = ptrtoint ptr %1 to i64 + %3 = getelementptr inbounds [4 x i64], ptr %1, i64 %2, i64 2 + ret ptr %3 +} + +; Two GEP instructions can be merged if one is constant-indexed and the other +; is an aggregate type with a constant last index, and the resulting pointer +; address by adding the constant offset aliases the address of another member. +; result = &((struct.C*) p + a).member2 +define ptr @partialConstantMemberAliasing1(ptr %p, i64 %a) { +; CHECK-LABEL: @partialConstantMemberAliasing1( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 [[A:%.*]], i32 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 %a, i32 1 + ret ptr %2 +} + +; Negative test. Similar to above, but the new address does not alias the +; address of another member. +define ptr @partialConstantMemberAliasing2(ptr %p, i64 %a) { +; CHECK-LABEL: @partialConstantMemberAliasing2( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i8, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 [[A:%.*]], i32 1 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i8, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 %a, i32 1 + ret ptr %2 +} + +; Negative test. Similar to above, but the new address falls outside the address +; range of the object currently pointed by the non-constant GEP. +define ptr @partialConstantMemberAliasing3(ptr %p, i64 %a) { +; CHECK-LABEL: @partialConstantMemberAliasing3( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 1 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_C:%.*]], ptr [[TMP1]], i64 [[A:%.*]], i32 2 +; CHECK-NEXT: ret ptr [[TMP2]] +; + %1 = getelementptr inbounds i32, ptr %p, i64 1 + %2 = getelementptr inbounds %struct.C, ptr %1, i64 %a, i32 2 + ret ptr %2 +}