llvm/test/Transforms/InstCombine/extractelement-strided-ptr-vector.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt -S -passes=instcombine < %s | FileCheck %s

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

@g = external global [4 x i64]

; A variable extract from a table of pointers into one object at a constant
; stride is address arithmetic, so it folds to a single GEP.
define ptr @strided(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @strided(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 3
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP2]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %g1 = getelementptr i8, ptr %b, i64 8
  %g2 = getelementptr i8, ptr %b, i64 16
  %g3 = getelementptr i8, ptr %b, i64 24
  %v0 = insertelement <4 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <4 x ptr> %v0, ptr %g1, i64 1
  %v2 = insertelement <4 x ptr> %v1, ptr %g2, i64 2
  %v3 = insertelement <4 x ptr> %v2, ptr %g3, i64 3
  %r = extractelement <4 x ptr> %v3, i32 %i
  ret ptr %r
}

; The base element may itself sit at a non-zero offset.
define ptr @strided_nonzero_base(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @strided_nonzero_base(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 2
; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP2]]
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[TMP3]], i64 4
; CHECK-NEXT:    ret ptr [[R]]
;
  %g0 = getelementptr i8, ptr %b, i64 4
  %g1 = getelementptr i8, ptr %b, i64 8
  %v0 = insertelement <2 x ptr> poison, ptr %g0, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %g1, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; The stride may be negative. The address is rebuilt from the common base, not
; from element 0: an inbounds GEP that leaves the object is poison, and lane 0
; must not hand that poison to a lane the extract actually selects.
define ptr @strided_negative_poison_base(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @strided_negative_poison_base(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i64 [[TMP1]], -2
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP3]]
; CHECK-NEXT:    [[R1:%.*]] = getelementptr i8, ptr [[R]], i64 6
; CHECK-NEXT:    ret ptr [[R1]]
;
  %g0 = getelementptr inbounds i8, ptr %b, i64 6
  %g1 = getelementptr inbounds i8, ptr %b, i64 4
  %v0 = insertelement <2 x ptr> poison, ptr %g0, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %g1, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; Same, with a zero stride: every element holds the same address, but only the
; base is known to be defined.
define ptr @zero_stride_poison_base(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @zero_stride_poison_base(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[B]], i64 4
; CHECK-NEXT:    ret ptr [[R]]
;
  %g0 = getelementptr inbounds i8, ptr %b, i64 4
  %g1 = getelementptr i8, ptr %b, i64 4
  %v0 = insertelement <2 x ptr> poison, ptr %g0, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %g1, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; The addrspacecast itself is the common base and already lives in the address
; space of the result.
define ptr @addrspacecast_base(ptr addrspace(1) %b, i32 %i) {
; CHECK-LABEL: define ptr @addrspacecast_base(
; CHECK-SAME: ptr addrspace(1) [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[C:%.*]] = addrspacecast ptr addrspace(1) [[B]] to ptr
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 3
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[C]], i64 [[TMP2]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %c = addrspacecast ptr addrspace(1) %b to ptr
  %g1 = getelementptr i8, ptr %c, i64 8
  %v0 = insertelement <2 x ptr> poison, ptr %c, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %g1, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; Negative: each element is cast separately, so there is no common base.
define ptr @addrspacecast_per_element(ptr addrspace(1) %b, i32 %i) {
; CHECK-LABEL: define ptr @addrspacecast_per_element(
; CHECK-SAME: ptr addrspace(1) [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[G1:%.*]] = getelementptr i8, ptr addrspace(1) [[B]], i64 8
; CHECK-NEXT:    [[C0:%.*]] = addrspacecast ptr addrspace(1) [[B]] to ptr
; CHECK-NEXT:    [[C1:%.*]] = addrspacecast ptr addrspace(1) [[G1]] to ptr
; CHECK-NEXT:    [[V0:%.*]] = insertelement <2 x ptr> poison, ptr [[C0]], i64 0
; CHECK-NEXT:    [[V1:%.*]] = insertelement <2 x ptr> [[V0]], ptr [[C1]], i64 1
; CHECK-NEXT:    [[R:%.*]] = extractelement <2 x ptr> [[V1]], i32 [[I]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %g1 = getelementptr i8, ptr addrspace(1) %b, i64 8
  %c0 = addrspacecast ptr addrspace(1) %b to ptr
  %c1 = addrspacecast ptr addrspace(1) %g1 to ptr
  %v0 = insertelement <2 x ptr> poison, ptr %c0, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %c1, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; Inserts need not appear in index order.
define ptr @strided_out_of_order(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @strided_out_of_order(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 3
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP2]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %g1 = getelementptr i8, ptr %b, i64 8
  %v0 = insertelement <2 x ptr> poison, ptr %g1, i64 1
  %v1 = insertelement <2 x ptr> %v0, ptr %b, i64 0
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; The vector need not come from an insertelement chain: a constant table of
; addresses into one global is strided too.
define ptr @strided_constant_vector(i32 %i) {
; CHECK-LABEL: define ptr @strided_constant_vector(
; CHECK-SAME: i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 3
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr @g, i64 [[TMP2]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %r = extractelement <4 x ptr> <ptr @g, ptr getelementptr (i8, ptr @g, i64 8), ptr getelementptr (i8, ptr @g, i64 16), ptr getelementptr (i8, ptr @g, i64 24)>, i32 %i
  ret ptr %r
}

; A shuffle reverses the table, which negates the stride.
define ptr @strided_through_shuffle(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @strided_through_shuffle(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[I]] to i64
; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i64 [[TMP1]], -8
; CHECK-NEXT:    [[R:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP3]]
; CHECK-NEXT:    [[R1:%.*]] = getelementptr i8, ptr [[R]], i64 8
; CHECK-NEXT:    ret ptr [[R1]]
;
  %g1 = getelementptr i8, ptr %b, i64 8
  %v0 = insertelement <2 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %g1, i64 1
  %s = shufflevector <2 x ptr> %v1, <2 x ptr> poison, <2 x i32> <i32 1, i32 0>
  %r = extractelement <2 x ptr> %s, i32 %i
  ret ptr %r
}

; Degenerate: a one-element vector has no stride to speak of, and the only
; in-range index is 0, so this is left to the existing folds.
define ptr @single_element(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @single_element(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[V0:%.*]] = insertelement <1 x ptr> poison, ptr [[B]], i64 0
; CHECK-NEXT:    [[R:%.*]] = extractelement <1 x ptr> [[V0]], i32 [[I]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %v0 = insertelement <1 x ptr> poison, ptr %b, i64 0
  %r = extractelement <1 x ptr> %v0, i32 %i
  ret ptr %r
}

; All elements equal: the extract is just that pointer.
define ptr @zero_stride(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @zero_stride(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    ret ptr [[B]]
;
  %v0 = insertelement <2 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %b, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; Negative: offsets 0, 8, 12, 24 are not an arithmetic sequence.
define ptr @irregular_stride(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @irregular_stride(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[G1:%.*]] = getelementptr i8, ptr [[B]], i64 8
; CHECK-NEXT:    [[G2:%.*]] = getelementptr i8, ptr [[B]], i64 12
; CHECK-NEXT:    [[G3:%.*]] = getelementptr i8, ptr [[B]], i64 24
; CHECK-NEXT:    [[V0:%.*]] = insertelement <4 x ptr> poison, ptr [[B]], i64 0
; CHECK-NEXT:    [[V1:%.*]] = insertelement <4 x ptr> [[V0]], ptr [[G1]], i64 1
; CHECK-NEXT:    [[V2:%.*]] = insertelement <4 x ptr> [[V1]], ptr [[G2]], i64 2
; CHECK-NEXT:    [[V3:%.*]] = insertelement <4 x ptr> [[V2]], ptr [[G3]], i64 3
; CHECK-NEXT:    [[R:%.*]] = extractelement <4 x ptr> [[V3]], i32 [[I]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %g1 = getelementptr i8, ptr %b, i64 8
  %g2 = getelementptr i8, ptr %b, i64 12
  %g3 = getelementptr i8, ptr %b, i64 24
  %v0 = insertelement <4 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <4 x ptr> %v0, ptr %g1, i64 1
  %v2 = insertelement <4 x ptr> %v1, ptr %g2, i64 2
  %v3 = insertelement <4 x ptr> %v2, ptr %g3, i64 3
  %r = extractelement <4 x ptr> %v3, i32 %i
  ret ptr %r
}

; Negative: elements point into two unrelated objects.
define ptr @two_bases(ptr %b, ptr %c, i32 %i) {
; CHECK-LABEL: define ptr @two_bases(
; CHECK-SAME: ptr [[B:%.*]], ptr [[C:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[V0:%.*]] = insertelement <2 x ptr> poison, ptr [[B]], i64 0
; CHECK-NEXT:    [[V1:%.*]] = insertelement <2 x ptr> [[V0]], ptr [[C]], i64 1
; CHECK-NEXT:    [[R:%.*]] = extractelement <2 x ptr> [[V1]], i32 [[I]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %v0 = insertelement <2 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <2 x ptr> %v0, ptr %c, i64 1
  %r = extractelement <2 x ptr> %v1, i32 %i
  ret ptr %r
}

; Negative: element 3 is never defined. It reads back as poison, which is its
; own base, so the elements are not all offsets into one object.
define ptr @partially_defined(ptr %b, i32 %i) {
; CHECK-LABEL: define ptr @partially_defined(
; CHECK-SAME: ptr [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[G1:%.*]] = getelementptr i8, ptr [[B]], i64 8
; CHECK-NEXT:    [[G2:%.*]] = getelementptr i8, ptr [[B]], i64 16
; CHECK-NEXT:    [[V0:%.*]] = insertelement <4 x ptr> poison, ptr [[B]], i64 0
; CHECK-NEXT:    [[V1:%.*]] = insertelement <4 x ptr> [[V0]], ptr [[G1]], i64 1
; CHECK-NEXT:    [[V2:%.*]] = insertelement <4 x ptr> [[V1]], ptr [[G2]], i64 2
; CHECK-NEXT:    [[R:%.*]] = extractelement <4 x ptr> [[V2]], i32 [[I]]
; CHECK-NEXT:    ret ptr [[R]]
;
  %g1 = getelementptr i8, ptr %b, i64 8
  %g2 = getelementptr i8, ptr %b, i64 16
  %v0 = insertelement <4 x ptr> poison, ptr %b, i64 0
  %v1 = insertelement <4 x ptr> %v0, ptr %g1, i64 1
  %v2 = insertelement <4 x ptr> %v1, ptr %g2, i64 2
  %r = extractelement <4 x ptr> %v2, i32 %i
  ret ptr %r
}

; Negative: a non-pointer vector is left to the existing folds.
define i32 @not_pointers(i32 %a, i32 %b, i32 %i) {
; CHECK-LABEL: define i32 @not_pointers(
; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]], i32 [[I:%.*]]) {
; CHECK-NEXT:    [[V0:%.*]] = insertelement <2 x i32> poison, i32 [[A]], i64 0
; CHECK-NEXT:    [[V1:%.*]] = insertelement <2 x i32> [[V0]], i32 [[B]], i64 1
; CHECK-NEXT:    [[R:%.*]] = extractelement <2 x i32> [[V1]], i32 [[I]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %v0 = insertelement <2 x i32> poison, i32 %a, i64 0
  %v1 = insertelement <2 x i32> %v0, i32 %b, i64 1
  %r = extractelement <2 x i32> %v1, i32 %i
  ret i32 %r
}