llvm/test/Transforms/LoopLoadElim/non-lcssa-input.ll

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

; LoopLoadElimination forms LCSSA before versioning a non-LCSSA loop, so a raw
; exit-block use is rewritten through an exit PHI instead of staying tied to the
; original loop and failing to dominate the shared exit after cloning.

define void @non_lcssa_exit_use(ptr nocapture %a, i64 %n) {
; CHECK-LABEL: define void @non_lcssa_exit_use(
; CHECK-SAME: ptr captures(none) [[A:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT:  [[FOR_BODY_LVER_CHECK:.*:]]
; CHECK-NEXT:    [[G:%.*]] = getelementptr i32, ptr [[A]], i64 -1
; CHECK-NEXT:    [[TMP0:%.*]] = sext i64 [[N]] to i128
; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i128 [[TMP0]], 1
; CHECK-NEXT:    [[SMAX:%.*]] = call i128 @llvm.smax.i128(i128 [[TMP1]], i128 1)
; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i128 [[SMAX]], -1
; CHECK-NEXT:    [[TMP3:%.*]] = trunc i128 [[TMP2]] to i64
; CHECK-NEXT:    [[TMP4:%.*]] = add i64 1, [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i64 [[TMP4]], 1
; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i128 [[TMP2]], 18446744073709551615
; CHECK-NEXT:    [[TMP7:%.*]] = or i1 [[TMP5]], [[TMP6]]
; CHECK-NEXT:    br i1 [[TMP7]], label %[[FOR_BODY_PH_LVER_ORIG:.*]], label %[[FOR_BODY_PH:.*]]
; CHECK:       [[FOR_BODY_PH_LVER_ORIG]]:
; CHECK-NEXT:    br label %[[FOR_BODY_LVER_ORIG:.*]]
; CHECK:       [[FOR_BODY_LVER_ORIG]]:
; CHECK-NEXT:    [[IV_LVER_ORIG:%.*]] = phi i64 [ [[IV_NEXT_LVER_ORIG:%.*]], %[[FOR_BODY_LVER_ORIG]] ], [ 0, %[[FOR_BODY_PH_LVER_ORIG]] ]
; CHECK-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, ptr [[G]], i64 [[IV_LVER_ORIG]]
; CHECK-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load i32, ptr [[ARRAYIDX_LVER_ORIG]], align 4
; CHECK-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[LOAD_LVER_ORIG]], 3
; CHECK-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV_LVER_ORIG]]
; CHECK-NEXT:    store i32 [[MUL_LVER_ORIG]], ptr [[ARRAYIDX2_LVER_ORIG]], align 4
; CHECK-NEXT:    [[IV_NEXT_LVER_ORIG]] = add i64 [[IV_LVER_ORIG]], 1
; CHECK-NEXT:    [[C_LVER_ORIG:%.*]] = icmp sgt i64 [[IV_NEXT_LVER_ORIG]], [[N]]
; CHECK-NEXT:    br i1 [[C_LVER_ORIG]], label %[[FOR_END_LOOPEXIT:.*]], label %[[FOR_BODY_LVER_ORIG]]
; CHECK:       [[FOR_BODY_PH]]:
; CHECK-NEXT:    [[LOAD_INITIAL:%.*]] = load i32, ptr [[G]], align 4
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[STORE_FORWARDED:%.*]] = phi i32 [ [[LOAD_INITIAL]], %[[FOR_BODY_PH]] ], [ [[MUL:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PH]] ]
; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[G]], i64 [[IV]]
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
; CHECK-NEXT:    [[MUL]] = mul i32 [[STORE_FORWARDED]], 3
; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV]]
; CHECK-NEXT:    store i32 [[MUL]], ptr [[ARRAYIDX2]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[C:%.*]] = icmp sgt i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[C]], label %[[FOR_END_LOOPEXIT2:.*]], label %[[FOR_BODY]]
; CHECK:       [[FOR_END_LOOPEXIT]]:
; CHECK-NEXT:    [[C_LCSSA_PH:%.*]] = phi i1 [ [[C_LVER_ORIG]], %[[FOR_BODY_LVER_ORIG]] ]
; CHECK-NEXT:    [[C_EXIT_PH:%.*]] = phi i1 [ [[C_LVER_ORIG]], %[[FOR_BODY_LVER_ORIG]] ]
; CHECK-NEXT:    br label %[[FOR_END:.*]]
; CHECK:       [[FOR_END_LOOPEXIT2]]:
; CHECK-NEXT:    [[C_LCSSA_PH3:%.*]] = phi i1 [ [[C]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[C_EXIT_PH4:%.*]] = phi i1 [ [[C]], %[[FOR_BODY]] ]
; CHECK-NEXT:    br label %[[FOR_END]]
; CHECK:       [[FOR_END]]:
; CHECK-NEXT:    [[C_LCSSA:%.*]] = phi i1 [ [[C_LCSSA_PH]], %[[FOR_END_LOOPEXIT]] ], [ [[C_LCSSA_PH3]], %[[FOR_END_LOOPEXIT2]] ]
; CHECK-NEXT:    [[C_EXIT:%.*]] = phi i1 [ [[C_EXIT_PH]], %[[FOR_END_LOOPEXIT]] ], [ [[C_EXIT_PH4]], %[[FOR_END_LOOPEXIT2]] ]
; CHECK-NEXT:    br i1 [[C_LCSSA]], label %[[EXIT_A:.*]], label %[[EXIT_B:.*]]
; CHECK:       [[EXIT_A]]:
; CHECK-NEXT:    ret void
; CHECK:       [[EXIT_B]]:
; CHECK-NEXT:    ret void
;
entry:
  %G = getelementptr i32, ptr %a, i64 -1
  br label %for.body

for.body:
  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
  %arrayidx = getelementptr inbounds i32, ptr %G, i64 %iv
  %load = load i32, ptr %arrayidx, align 4
  %mul = mul i32 %load, 3
  %arrayidx2 = getelementptr inbounds i32, ptr %a, i64 %iv
  store i32 %mul, ptr %arrayidx2, align 4
  %iv.next = add i64 %iv, 1
  %C = icmp sgt i64 %iv.next, %n
  br i1 %C, label %for.end, label %for.body

for.end:
  %C.exit = phi i1 [ %C, %for.body ]
  br i1 %C, label %exit.a, label %exit.b

exit.a:
  ret void

exit.b:
  ret void
}

; Nested loops: the outer loop is in LCSSA form, but the inner (versioned) loop
; is not, because %C is used raw in the inner exit block alongside its exit PHI.

define void @nested(ptr %a, i64 %n) {
; CHECK-LABEL: define void @nested(
; CHECK-SAME: ptr [[A:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[G:%.*]] = getelementptr i32, ptr [[A]], i64 -1
; CHECK-NEXT:    [[TMP0:%.*]] = sext i64 [[N]] to i128
; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i128 [[TMP0]], 1
; CHECK-NEXT:    [[SMAX:%.*]] = call i128 @llvm.smax.i128(i128 [[TMP1]], i128 1)
; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i128 [[SMAX]], -1
; CHECK-NEXT:    br label %[[FOR_BODY_LVER_CHECK:.*]]
; CHECK:       [[FOR_BODY_LVER_CHECK]]:
; CHECK-NEXT:    [[OIV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OIV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    [[TMP3:%.*]] = trunc i128 [[TMP2]] to i64
; CHECK-NEXT:    [[TMP4:%.*]] = add i64 1, [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i64 [[TMP4]], 1
; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i128 [[TMP2]], 18446744073709551615
; CHECK-NEXT:    [[TMP7:%.*]] = or i1 [[TMP5]], [[TMP6]]
; CHECK-NEXT:    br i1 [[TMP7]], label %[[FOR_BODY_PH_LVER_ORIG:.*]], label %[[FOR_BODY_PH:.*]]
; CHECK:       [[FOR_BODY_PH_LVER_ORIG]]:
; CHECK-NEXT:    br label %[[FOR_BODY_LVER_ORIG:.*]]
; CHECK:       [[FOR_BODY_LVER_ORIG]]:
; CHECK-NEXT:    [[IV_LVER_ORIG:%.*]] = phi i64 [ 0, %[[FOR_BODY_PH_LVER_ORIG]] ], [ [[IV_NEXT_LVER_ORIG:%.*]], %[[FOR_BODY_LVER_ORIG]] ]
; CHECK-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, ptr [[G]], i64 [[IV_LVER_ORIG]]
; CHECK-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load i32, ptr [[ARRAYIDX_LVER_ORIG]], align 4
; CHECK-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[LOAD_LVER_ORIG]], 3
; CHECK-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV_LVER_ORIG]]
; CHECK-NEXT:    store i32 [[MUL_LVER_ORIG]], ptr [[ARRAYIDX2_LVER_ORIG]], align 4
; CHECK-NEXT:    [[IV_NEXT_LVER_ORIG]] = add i64 [[IV_LVER_ORIG]], 1
; CHECK-NEXT:    [[C_LVER_ORIG:%.*]] = icmp sgt i64 [[IV_NEXT_LVER_ORIG]], [[N]]
; CHECK-NEXT:    br i1 [[C_LVER_ORIG]], label %[[INNER_EXIT_LOOPEXIT:.*]], label %[[FOR_BODY_LVER_ORIG]]
; CHECK:       [[FOR_BODY_PH]]:
; CHECK-NEXT:    [[LOAD_INITIAL:%.*]] = load i32, ptr [[G]], align 4
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[STORE_FORWARDED:%.*]] = phi i32 [ [[LOAD_INITIAL]], %[[FOR_BODY_PH]] ], [ [[MUL:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, %[[FOR_BODY_PH]] ], [ [[IV_NEXT:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[G]], i64 [[IV]]
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
; CHECK-NEXT:    [[MUL]] = mul i32 [[STORE_FORWARDED]], 3
; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV]]
; CHECK-NEXT:    store i32 [[MUL]], ptr [[ARRAYIDX2]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[C:%.*]] = icmp sgt i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[C]], label %[[INNER_EXIT_LOOPEXIT3:.*]], label %[[FOR_BODY]]
; CHECK:       [[INNER_EXIT_LOOPEXIT]]:
; CHECK-NEXT:    [[C_LCSSA1_PH:%.*]] = phi i1 [ [[C_LVER_ORIG]], %[[FOR_BODY_LVER_ORIG]] ]
; CHECK-NEXT:    [[C_LCSSA_PH:%.*]] = phi i1 [ [[C_LVER_ORIG]], %[[FOR_BODY_LVER_ORIG]] ]
; CHECK-NEXT:    br label %[[INNER_EXIT:.*]]
; CHECK:       [[INNER_EXIT_LOOPEXIT3]]:
; CHECK-NEXT:    [[C_LCSSA1_PH4:%.*]] = phi i1 [ [[C]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[C_LCSSA_PH5:%.*]] = phi i1 [ [[C]], %[[FOR_BODY]] ]
; CHECK-NEXT:    br label %[[INNER_EXIT]]
; CHECK:       [[INNER_EXIT]]:
; CHECK-NEXT:    [[C_LCSSA1:%.*]] = phi i1 [ [[C_LCSSA1_PH]], %[[INNER_EXIT_LOOPEXIT]] ], [ [[C_LCSSA1_PH4]], %[[INNER_EXIT_LOOPEXIT3]] ]
; CHECK-NEXT:    [[C_LCSSA:%.*]] = phi i1 [ [[C_LCSSA_PH]], %[[INNER_EXIT_LOOPEXIT]] ], [ [[C_LCSSA_PH5]], %[[INNER_EXIT_LOOPEXIT3]] ]
; CHECK-NEXT:    br i1 [[C_LCSSA1]], label %[[OUTER_LATCH]], label %[[INNER_OTHER:.*]]
; CHECK:       [[INNER_OTHER]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[OIV_NEXT]] = add i64 [[OIV]], 1
; CHECK-NEXT:    [[OC:%.*]] = icmp slt i64 [[OIV_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[OC]], label %[[FOR_BODY_LVER_CHECK]], label %[[OUTER_EXIT:.*]]
; CHECK:       [[OUTER_EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %G = getelementptr i32, ptr %a, i64 -1
  br label %outer.header

outer.header:
  %oiv = phi i64 [ 0, %entry ], [ %oiv.next, %outer.latch ]
  br label %for.body

for.body:
  %iv = phi i64 [ 0, %outer.header ], [ %iv.next, %for.body ]
  %arrayidx = getelementptr inbounds i32, ptr %G, i64 %iv
  %load = load i32, ptr %arrayidx, align 4
  %mul = mul i32 %load, 3
  %arrayidx2 = getelementptr inbounds i32, ptr %a, i64 %iv
  store i32 %mul, ptr %arrayidx2, align 4
  %iv.next = add i64 %iv, 1
  %C = icmp sgt i64 %iv.next, %n
  br i1 %C, label %inner.exit, label %for.body

inner.exit:
  %C.lcssa = phi i1 [ %C, %for.body ]
  br i1 %C, label %outer.latch, label %inner.other

inner.other:
  br label %outer.latch

outer.latch:
  %oiv.next = add i64 %oiv, 1
  %oc = icmp slt i64 %oiv.next, %n
  br i1 %oc, label %outer.header, label %outer.exit

outer.exit:
  ret void
}