; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt < %s -passes='sroa<preserve-cfg>' -S | FileCheck %s --check-prefixes=CHECK,CHECK-PRESERVE-CFG
; RUN: opt < %s -passes='sroa<modify-cfg>' -S | FileCheck %s --check-prefixes=CHECK,CHECK-MODIFY-CFG
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-n8:16:32:64"

; Basic tree-structured merge: 4 stores of <2 x float> into <8 x float>
define <8 x float> @basic_tree_merge(<2 x float> %a, <2 x float> %b, <2 x float> %c, <2 x float> %d) {
; CHECK-LABEL: define <8 x float> @basic_tree_merge(
; CHECK-SAME: <2 x float> [[A:%.*]], <2 x float> [[B:%.*]], <2 x float> [[C:%.*]], <2 x float> [[D:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <2 x float> [[A]], <2 x float> [[B]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x float> [[C]], <2 x float> [[D]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x float> [[TMP0]], <4 x float> [[TMP1]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
; CHECK-NEXT:    ret <8 x float> [[TMP2]]
;
entry:
  %alloca = alloca [8 x float]

  %ptr0 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 0
  store <2 x float> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 2
  store <2 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 4
  store <2 x float> %c, ptr %ptr2

  %ptr3 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 6
  store <2 x float> %d, ptr %ptr3

  %result = load <8 x float>, ptr %alloca
  ret <8 x float> %result
}

define void @multiple_partitions(<2 x float> %a, <2 x float> %b, <2 x float> %c, <2 x float> %d, ptr %e, ptr %f) {
; CHECK-LABEL: define void @multiple_partitions(
; CHECK-SAME: <2 x float> [[A:%.*]], <2 x float> [[B:%.*]], <2 x float> [[C:%.*]], <2 x float> [[D:%.*]], ptr [[E:%.*]], ptr [[F:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <2 x float> [[A]], <2 x float> [[B]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x float> [[C]], <2 x float> [[D]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    store <4 x float> [[TMP0]], ptr [[E]], align 16
; CHECK-NEXT:    store <4 x float> [[TMP1]], ptr [[F]], align 16
; CHECK-NEXT:    ret void
;
entry:
  %alloca = alloca [8 x float]

  %ptr0 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 0
  store <2 x float> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 2
  store <2 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 4
  store <2 x float> %c, ptr %ptr2

  %ptr3 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 6
  store <2 x float> %d, ptr %ptr3

  %result1 = load <4 x float>, ptr %alloca

  %ptr_offset4 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 4
  %result2 = load <4 x float>, ptr %ptr_offset4

  store <4 x float> %result1, ptr %e
  store <4 x float> %result2, ptr %f

  ret void
}

; Out-of-order stores: stores happen in non-sequential order
define <8 x i32> @out_of_order_stores(<2 x i32> %a, <2 x i32> %b, <2 x i32> %c, <2 x i32> %d) {
; CHECK-LABEL: define <8 x i32> @out_of_order_stores(
; CHECK-SAME: <2 x i32> [[A:%.*]], <2 x i32> [[B:%.*]], <2 x i32> [[C:%.*]], <2 x i32> [[D:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <2 x i32> [[A]], <2 x i32> [[B]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x i32> [[C]], <2 x i32> [[D]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32> [[TMP0]], <4 x i32> [[TMP1]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
; CHECK-NEXT:    ret <8 x i32> [[TMP2]]
;
entry:
  %alloca = alloca [8 x i32]

  %ptr2 = getelementptr inbounds [8 x i32], ptr %alloca, i32 0, i32 4
  store <2 x i32> %c, ptr %ptr2

  %ptr0 = getelementptr inbounds [8 x i32], ptr %alloca, i32 0, i32 0
  store <2 x i32> %a, ptr %ptr0

  %ptr3 = getelementptr inbounds [8 x i32], ptr %alloca, i32 0, i32 6
  store <2 x i32> %d, ptr %ptr3

  %ptr1 = getelementptr inbounds [8 x i32], ptr %alloca, i32 0, i32 2
  store <2 x i32> %b, ptr %ptr1

  %result = load <8 x i32>, ptr %alloca
  ret <8 x i32> %result
}

; Single element stores: 8 stores of <1 x i16> into <8 x i16>
define <8 x i16> @single_element_stores(<1 x i16> %a, <1 x i16> %b, <1 x i16> %c, <1 x i16> %d, <1 x i16> %e, <1 x i16> %f, <1 x i16> %g, <1 x i16> %h) {
; CHECK-LABEL: define <8 x i16> @single_element_stores(
; CHECK-SAME: <1 x i16> [[A:%.*]], <1 x i16> [[B:%.*]], <1 x i16> [[C:%.*]], <1 x i16> [[D:%.*]], <1 x i16> [[E:%.*]], <1 x i16> [[F:%.*]], <1 x i16> [[G:%.*]], <1 x i16> [[H:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <1 x i16> [[A]], <1 x i16> [[B]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <1 x i16> [[C]], <1 x i16> [[D]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <1 x i16> [[E]], <1 x i16> [[F]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <1 x i16> [[G]], <1 x i16> [[H]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP4:%.*]] = shufflevector <2 x i16> [[TMP0]], <2 x i16> [[TMP1]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <2 x i16> [[TMP2]], <2 x i16> [[TMP3]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[TMP4]], <4 x i16> [[TMP5]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
; CHECK-NEXT:    ret <8 x i16> [[TMP6]]
;
entry:
  %alloca = alloca [8 x i16]

  %ptr0 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 0
  store <1 x i16> %a, ptr %ptr0
  %ptr1 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 1
  store <1 x i16> %b, ptr %ptr1
  %ptr2 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 2
  store <1 x i16> %c, ptr %ptr2
  %ptr3 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 3
  store <1 x i16> %d, ptr %ptr3
  %ptr4 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 4
  store <1 x i16> %e, ptr %ptr4
  %ptr5 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 5
  store <1 x i16> %f, ptr %ptr5
  %ptr6 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 6
  store <1 x i16> %g, ptr %ptr6
  %ptr7 = getelementptr inbounds [8 x i16], ptr %alloca, i32 0, i32 7
  store <1 x i16> %h, ptr %ptr7

  %result = load <8 x i16>, ptr %alloca
  ret <8 x i16> %result
}

; Non-power-of-2: 3 stores of <2 x float> into <6 x float>
define <6 x float> @non_power_of_2(<2 x float> %a, <2 x float> %b, <2 x float> %c) {
; CHECK-LABEL: define <6 x float> @non_power_of_2(
; CHECK-SAME: <2 x float> [[A:%.*]], <2 x float> [[B:%.*]], <2 x float> [[C:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <2 x float> [[A]], <2 x float> [[B]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x float> [[C]], <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 poison, i32 poison>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x float> [[TMP0]], <4 x float> [[TMP1]], <6 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5>
; CHECK-NEXT:    ret <6 x float> [[TMP2]]
;
entry:
  %alloca = alloca [6 x float]

  %ptr0 = getelementptr inbounds [6 x float], ptr %alloca, i32 0, i32 0
  store <2 x float> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [6 x float], ptr %alloca, i32 0, i32 2
  store <2 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [6 x float], ptr %alloca, i32 0, i32 4
  store <2 x float> %c, ptr %ptr2

  %result = load <6 x float>, ptr %alloca
  ret <6 x float> %result
}

; Store with different size of vectors
define <7 x float> @store_with_different_size_of_vectors(<1 x float> %a, <4 x float> %b, <2 x float> %c) {
; CHECK-LABEL: define <7 x float> @store_with_different_size_of_vectors(
; CHECK-SAME: <1 x float> [[A:%.*]], <4 x float> [[B:%.*]], <2 x float> [[C:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <1 x float> [[A]], <1 x float> poison, <4 x i32> <i32 0, i32 poison, i32 poison, i32 poison>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x float> [[TMP0]], <4 x float> [[B]], <5 x i32> <i32 0, i32 4, i32 5, i32 6, i32 7>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <2 x float> [[C]], <2 x float> poison, <5 x i32> <i32 0, i32 1, i32 poison, i32 poison, i32 poison>
; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <5 x float> [[TMP1]], <5 x float> [[TMP2]], <7 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6>
; CHECK-NEXT:    ret <7 x float> [[TMP3]]
;
entry:
  %alloca = alloca [7 x float]

  %ptr0 = getelementptr inbounds [7 x float], ptr %alloca, i32 0, i32 0
  store <1 x float> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [7 x float], ptr %alloca, i32 0, i32 1
  store <4 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [7 x float], ptr %alloca, i32 0, i32 5
  store <2 x float> %c, ptr %ptr2

  %result = load <7 x float>, ptr %alloca
  ret <7 x float> %result
}

; Load and store with different element type
define <4 x double> @load_store_different_element_type(<2 x i32> %a, <2 x float> %b, <2 x float> %c, <2 x i32> %d) {
; CHECK-LABEL: define <4 x double> @load_store_different_element_type(
; CHECK-SAME: <2 x i32> [[A:%.*]], <2 x float> [[B:%.*]], <2 x float> [[C:%.*]], <2 x i32> [[D:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = bitcast <2 x i32> [[A]] to <1 x double>
; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <2 x float> [[B]] to <1 x double>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <1 x double> [[TMP0]], <1 x double> [[TMP1]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP3:%.*]] = bitcast <2 x float> [[C]] to <1 x double>
; CHECK-NEXT:    [[TMP4:%.*]] = bitcast <2 x i32> [[D]] to <1 x double>
; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <1 x double> [[TMP3]], <1 x double> [[TMP4]], <2 x i32> <i32 0, i32 1>
; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> [[TMP5]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    ret <4 x double> [[TMP6]]
;
entry:
  %alloca = alloca [8 x float]

  %ptr0 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 0
  store <2 x i32> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 2
  store <2 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 4
  store <2 x float> %c, ptr %ptr2

  %ptr3 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 6
  store <2 x i32> %d, ptr %ptr3

  %result = load <4 x double>, ptr %alloca
  ret <4 x double> %result
}

define <8 x float> @bitcast_needed(<2 x i32> %a, <2 x i16> %b, <12 x i8> %c, <1 x i64> %d) {
; CHECK-LABEL: define <8 x float> @bitcast_needed(
; CHECK-SAME: <2 x i32> [[A:%.*]], <2 x i16> [[B:%.*]], <12 x i8> [[C:%.*]], <1 x i64> [[D:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = bitcast <2 x i32> [[A]] to <2 x float>
; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <2 x i16> [[B]] to <1 x float>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <1 x float> [[TMP1]], <1 x float> poison, <2 x i32> <i32 0, i32 poison>
; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x float> [[TMP0]], <2 x float> [[TMP2]], <3 x i32> <i32 0, i32 1, i32 2>
; CHECK-NEXT:    [[TMP5:%.*]] = bitcast <12 x i8> [[C]] to <3 x float>
; CHECK-NEXT:    [[TMP4:%.*]] = bitcast <1 x i64> [[D]] to <2 x float>
; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <2 x float> [[TMP4]], <2 x float> poison, <3 x i32> <i32 0, i32 1, i32 poison>
; CHECK-NEXT:    [[TMP7:%.*]] = shufflevector <3 x float> [[TMP5]], <3 x float> [[TMP9]], <5 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4>
; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <3 x float> [[TMP3]], <3 x float> poison, <5 x i32> <i32 0, i32 1, i32 2, i32 poison, i32 poison>
; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <5 x float> [[TMP8]], <5 x float> [[TMP7]], <8 x i32> <i32 0, i32 1, i32 2, i32 5, i32 6, i32 7, i32 8, i32 9>
; CHECK-NEXT:    ret <8 x float> [[TMP6]]
;
entry:
  %alloca = alloca [8 x float]

  %ptr0 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 0
  store <2 x i32> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 2
  store <2 x i16> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 3
  store <12 x i8> %c, ptr %ptr2

  %ptr3 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 6
  store <1 x i64> %d, ptr %ptr3

  %result = load <8 x float>, ptr %alloca
  ret <8 x float> %result
}

define <8 x float> @load_in_different_blocks(<2 x float> %a, <2 x float> %b, <2 x float> %c, <2 x float> %d, i1 %cond) {
; CHECK-LABEL: define <8 x float> @load_in_different_blocks(
; CHECK-SAME: <2 x float> [[A:%.*]], <2 x float> [[B:%.*]], <2 x float> [[C:%.*]], <2 x float> [[D:%.*]], i1 [[COND:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[TMP0:%.*]] = shufflevector <2 x float> [[A]], <2 x float> [[B]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x float> [[C]], <2 x float> [[D]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x float> [[TMP0]], <4 x float> [[TMP1]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
; CHECK-NEXT:    br i1 [[COND]], label %[[TRUEBRANCH:.*]], label %[[FALSEBRANCH:.*]]
; CHECK:       [[TRUEBRANCH]]:
; CHECK-NEXT:    br label %[[FALSEBRANCH]]
; CHECK:       [[FALSEBRANCH]]:
; CHECK-NEXT:    [[RESULT:%.*]] = phi <8 x float> [ poison, %[[ENTRY]] ], [ [[TMP2]], %[[TRUEBRANCH]] ]
; CHECK-NEXT:    ret <8 x float> [[RESULT]]
;
entry:
  %alloca = alloca [8 x float]

  %ptr0 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 0
  store <2 x float> %a, ptr %ptr0

  %ptr1 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 2
  store <2 x float> %b, ptr %ptr1

  %ptr2 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 4
  store <2 x float> %c, ptr %ptr2

  %ptr3 = getelementptr inbounds [8 x float], ptr %alloca, i32 0, i32 6
  store <2 x float> %d, ptr %ptr3

  br i1 %cond, label %TrueBranch, label %FalseBranch

TrueBranch:
  %load1 = load <8 x float>, ptr %alloca
  br label %FalseBranch

FalseBranch:
  %result = phi <8 x float> [ poison, %entry ], [ %load1, %TrueBranch ]
  ret <8 x float> %result
}

;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
; CHECK-MODIFY-CFG: {{.*}}
; CHECK-PRESERVE-CFG: {{.*}}