test/Transforms/LoopSimplify/AMDGPU/separate-nested-loop-divergent.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt -S -passes=loop-simplify -mtriple=amdgcn-amd-amdhsa < %s | FileCheck %s --check-prefix=AMDGPU
; RUN: opt -S -passes=loop-simplify < %s | FileCheck %s --check-prefix=GENERIC

; A loop with two backedges where the "continue" backedge is selected by a
; per-lane condition. On a target with branch divergence the loop is not
; separated into a nested loop; a unique backedge block is inserted instead.

define amdgpu_kernel void @continue_loop(i32 %n, ptr addrspace(1) %p, ptr addrspace(1) %out) {
; AMDGPU-LABEL: define amdgpu_kernel void @continue_loop(
; AMDGPU-SAME: i32 [[N:%.*]], ptr addrspace(1) [[P:%.*]], ptr addrspace(1) [[OUT:%.*]]) {
; AMDGPU-NEXT:  [[ENTRY:.*]]:
; AMDGPU-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; AMDGPU-NEXT:    br label %[[HEADER:.*]]
; AMDGPU:       [[HEADER]]:
; AMDGPU-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[HEADER_BACKEDGE:.*]] ]
; AMDGPU-NEXT:    [[ACC:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[ACC_BE:%.*]], %[[HEADER_BACKEDGE]] ]
; AMDGPU-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; AMDGPU-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[P]], i32 [[I]]
; AMDGPU-NEXT:    [[V:%.*]] = load i32, ptr addrspace(1) [[GEP]], align 4
; AMDGPU-NEXT:    [[BITS:%.*]] = lshr i32 [[V]], [[TID]]
; AMDGPU-NEXT:    [[BIT:%.*]] = and i32 [[BITS]], 1
; AMDGPU-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[BIT]], 0
; AMDGPU-NEXT:    br i1 [[IS_ZERO]], label %[[CONTINUE:.*]], label %[[UPDATE:.*]]
; AMDGPU:       [[CONTINUE]]:
; AMDGPU-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C1]], label %[[HEADER_BACKEDGE]], label %[[EXIT:.*]]
; AMDGPU:       [[HEADER_BACKEDGE]]:
; AMDGPU-NEXT:    [[ACC_BE]] = phi i32 [ [[ACC]], %[[CONTINUE]] ], [ [[ACC_NEXT:%.*]], %[[UPDATE]] ]
; AMDGPU-NEXT:    br label %[[HEADER]]
; AMDGPU:       [[UPDATE]]:
; AMDGPU-NEXT:    [[ACC_NEXT]] = add i32 [[ACC]], [[V]]
; AMDGPU-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C2]], label %[[HEADER_BACKEDGE]], label %[[EXIT]]
; AMDGPU:       [[EXIT]]:
; AMDGPU-NEXT:    [[R:%.*]] = phi i32 [ [[ACC]], %[[CONTINUE]] ], [ [[ACC_NEXT]], %[[UPDATE]] ]
; AMDGPU-NEXT:    [[OUT_GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[OUT]], i32 [[TID]]
; AMDGPU-NEXT:    store i32 [[R]], ptr addrspace(1) [[OUT_GEP]], align 4
; AMDGPU-NEXT:    ret void
;
; GENERIC-LABEL: define amdgpu_kernel void @continue_loop(
; GENERIC-SAME: i32 [[N:%.*]], ptr addrspace(1) [[P:%.*]], ptr addrspace(1) [[OUT:%.*]]) {
; GENERIC-NEXT:  [[ENTRY:.*]]:
; GENERIC-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; GENERIC-NEXT:    br label %[[HEADER_OUTER:.*]]
; GENERIC:       [[HEADER_OUTER]]:
; GENERIC-NEXT:    [[I_PH:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[UPDATE:.*]] ], [ 0, %[[ENTRY]] ]
; GENERIC-NEXT:    [[ACC_PH:%.*]] = phi i32 [ [[ACC_NEXT:%.*]], %[[UPDATE]] ], [ 0, %[[ENTRY]] ]
; GENERIC-NEXT:    br label %[[HEADER:.*]]
; GENERIC:       [[HEADER]]:
; GENERIC-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT]], %[[CONTINUE:.*]] ], [ [[I_PH]], %[[HEADER_OUTER]] ]
; GENERIC-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; GENERIC-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[P]], i32 [[I]]
; GENERIC-NEXT:    [[V:%.*]] = load i32, ptr addrspace(1) [[GEP]], align 4
; GENERIC-NEXT:    [[BITS:%.*]] = lshr i32 [[V]], [[TID]]
; GENERIC-NEXT:    [[BIT:%.*]] = and i32 [[BITS]], 1
; GENERIC-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[BIT]], 0
; GENERIC-NEXT:    br i1 [[IS_ZERO]], label %[[CONTINUE]], label %[[UPDATE]]
; GENERIC:       [[CONTINUE]]:
; GENERIC-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C1]], label %[[HEADER]], label %[[EXIT_LOOPEXIT:.*]]
; GENERIC:       [[UPDATE]]:
; GENERIC-NEXT:    [[ACC_NEXT]] = add i32 [[ACC_PH]], [[V]]
; GENERIC-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C2]], label %[[HEADER_OUTER]], label %[[EXIT_LOOPEXIT1:.*]]
; GENERIC:       [[EXIT_LOOPEXIT]]:
; GENERIC-NEXT:    br label %[[EXIT:.*]]
; GENERIC:       [[EXIT_LOOPEXIT1]]:
; GENERIC-NEXT:    br label %[[EXIT]]
; GENERIC:       [[EXIT]]:
; GENERIC-NEXT:    [[R:%.*]] = phi i32 [ [[ACC_PH]], %[[EXIT_LOOPEXIT]] ], [ [[ACC_NEXT]], %[[EXIT_LOOPEXIT1]] ]
; GENERIC-NEXT:    [[OUT_GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[OUT]], i32 [[TID]]
; GENERIC-NEXT:    store i32 [[R]], ptr addrspace(1) [[OUT_GEP]], align 4
; GENERIC-NEXT:    ret void
;
entry:
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
  br label %header

header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %continue ], [ %i.next, %update ]
  %acc = phi i32 [ 0, %entry ], [ %acc, %continue ], [ %acc.next, %update ]
  %i.next = add i32 %i, 1
  %gep = getelementptr i32, ptr addrspace(1) %p, i32 %i
  %v = load i32, ptr addrspace(1) %gep, align 4
  %bits = lshr i32 %v, %tid
  %bit = and i32 %bits, 1
  %is.zero = icmp eq i32 %bit, 0
  br i1 %is.zero, label %continue, label %update

continue:
  %c1 = icmp slt i32 %i.next, %n
  br i1 %c1, label %header, label %exit

update:
  %acc.next = add i32 %acc, %v
  %c2 = icmp slt i32 %i.next, %n
  br i1 %c2, label %header, label %exit

exit:
  %r = phi i32 [ %acc, %continue ], [ %acc.next, %update ]
  %out.gep = getelementptr i32, ptr addrspace(1) %out, i32 %tid
  store i32 %r, ptr addrspace(1) %out.gep, align 4
  ret void
}

; A function that executes with a single lane has no branch divergence, so
; the nested loop is still separated.

define amdgpu_kernel void @continue_loop_single_lane(i32 %n, ptr addrspace(1) %p, ptr addrspace(1) %out) #0 {
; AMDGPU-LABEL: define amdgpu_kernel void @continue_loop_single_lane(
; AMDGPU-SAME: i32 [[N:%.*]], ptr addrspace(1) [[P:%.*]], ptr addrspace(1) [[OUT:%.*]]) #[[ATTR0:[0-9]+]] {
; AMDGPU-NEXT:  [[ENTRY:.*]]:
; AMDGPU-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; AMDGPU-NEXT:    br label %[[HEADER_OUTER:.*]]
; AMDGPU:       [[HEADER_OUTER]]:
; AMDGPU-NEXT:    [[I_PH:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[UPDATE:.*]] ], [ 0, %[[ENTRY]] ]
; AMDGPU-NEXT:    [[ACC_PH:%.*]] = phi i32 [ [[ACC_NEXT:%.*]], %[[UPDATE]] ], [ 0, %[[ENTRY]] ]
; AMDGPU-NEXT:    br label %[[HEADER:.*]]
; AMDGPU:       [[HEADER]]:
; AMDGPU-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT]], %[[CONTINUE:.*]] ], [ [[I_PH]], %[[HEADER_OUTER]] ]
; AMDGPU-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; AMDGPU-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[P]], i32 [[I]]
; AMDGPU-NEXT:    [[V:%.*]] = load i32, ptr addrspace(1) [[GEP]], align 4
; AMDGPU-NEXT:    [[BITS:%.*]] = lshr i32 [[V]], [[TID]]
; AMDGPU-NEXT:    [[BIT:%.*]] = and i32 [[BITS]], 1
; AMDGPU-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[BIT]], 0
; AMDGPU-NEXT:    br i1 [[IS_ZERO]], label %[[CONTINUE]], label %[[UPDATE]]
; AMDGPU:       [[CONTINUE]]:
; AMDGPU-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C1]], label %[[HEADER]], label %[[EXIT_LOOPEXIT:.*]]
; AMDGPU:       [[UPDATE]]:
; AMDGPU-NEXT:    [[ACC_NEXT]] = add i32 [[ACC_PH]], [[V]]
; AMDGPU-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C2]], label %[[HEADER_OUTER]], label %[[EXIT_LOOPEXIT1:.*]]
; AMDGPU:       [[EXIT_LOOPEXIT]]:
; AMDGPU-NEXT:    br label %[[EXIT:.*]]
; AMDGPU:       [[EXIT_LOOPEXIT1]]:
; AMDGPU-NEXT:    br label %[[EXIT]]
; AMDGPU:       [[EXIT]]:
; AMDGPU-NEXT:    [[R:%.*]] = phi i32 [ [[ACC_PH]], %[[EXIT_LOOPEXIT]] ], [ [[ACC_NEXT]], %[[EXIT_LOOPEXIT1]] ]
; AMDGPU-NEXT:    store i32 [[R]], ptr addrspace(1) [[OUT]], align 4
; AMDGPU-NEXT:    ret void
;
; GENERIC-LABEL: define amdgpu_kernel void @continue_loop_single_lane(
; GENERIC-SAME: i32 [[N:%.*]], ptr addrspace(1) [[P:%.*]], ptr addrspace(1) [[OUT:%.*]]) #[[ATTR0:[0-9]+]] {
; GENERIC-NEXT:  [[ENTRY:.*]]:
; GENERIC-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; GENERIC-NEXT:    br label %[[HEADER_OUTER:.*]]
; GENERIC:       [[HEADER_OUTER]]:
; GENERIC-NEXT:    [[I_PH:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[UPDATE:.*]] ], [ 0, %[[ENTRY]] ]
; GENERIC-NEXT:    [[ACC_PH:%.*]] = phi i32 [ [[ACC_NEXT:%.*]], %[[UPDATE]] ], [ 0, %[[ENTRY]] ]
; GENERIC-NEXT:    br label %[[HEADER:.*]]
; GENERIC:       [[HEADER]]:
; GENERIC-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT]], %[[CONTINUE:.*]] ], [ [[I_PH]], %[[HEADER_OUTER]] ]
; GENERIC-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; GENERIC-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr addrspace(1) [[P]], i32 [[I]]
; GENERIC-NEXT:    [[V:%.*]] = load i32, ptr addrspace(1) [[GEP]], align 4
; GENERIC-NEXT:    [[BITS:%.*]] = lshr i32 [[V]], [[TID]]
; GENERIC-NEXT:    [[BIT:%.*]] = and i32 [[BITS]], 1
; GENERIC-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[BIT]], 0
; GENERIC-NEXT:    br i1 [[IS_ZERO]], label %[[CONTINUE]], label %[[UPDATE]]
; GENERIC:       [[CONTINUE]]:
; GENERIC-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C1]], label %[[HEADER]], label %[[EXIT_LOOPEXIT:.*]]
; GENERIC:       [[UPDATE]]:
; GENERIC-NEXT:    [[ACC_NEXT]] = add i32 [[ACC_PH]], [[V]]
; GENERIC-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C2]], label %[[HEADER_OUTER]], label %[[EXIT_LOOPEXIT1:.*]]
; GENERIC:       [[EXIT_LOOPEXIT]]:
; GENERIC-NEXT:    br label %[[EXIT:.*]]
; GENERIC:       [[EXIT_LOOPEXIT1]]:
; GENERIC-NEXT:    br label %[[EXIT]]
; GENERIC:       [[EXIT]]:
; GENERIC-NEXT:    [[R:%.*]] = phi i32 [ [[ACC_PH]], %[[EXIT_LOOPEXIT]] ], [ [[ACC_NEXT]], %[[EXIT_LOOPEXIT1]] ]
; GENERIC-NEXT:    store i32 [[R]], ptr addrspace(1) [[OUT]], align 4
; GENERIC-NEXT:    ret void
;
entry:
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
  br label %header

header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %continue ], [ %i.next, %update ]
  %acc = phi i32 [ 0, %entry ], [ %acc, %continue ], [ %acc.next, %update ]
  %i.next = add i32 %i, 1
  %gep = getelementptr i32, ptr addrspace(1) %p, i32 %i
  %v = load i32, ptr addrspace(1) %gep, align 4
  %bits = lshr i32 %v, %tid
  %bit = and i32 %bits, 1
  %is.zero = icmp eq i32 %bit, 0
  br i1 %is.zero, label %continue, label %update

continue:
  %c1 = icmp slt i32 %i.next, %n
  br i1 %c1, label %header, label %exit

update:
  %acc.next = add i32 %acc, %v
  %c2 = icmp slt i32 %i.next, %n
  br i1 %c2, label %header, label %exit

exit:
  %r = phi i32 [ %acc, %continue ], [ %acc.next, %update ]
  store i32 %r, ptr addrspace(1) %out, align 4
  ret void
}

; A degenerate header PHI (%p) is folded before the backedges are merged, so
; it does not turn into a PHI cycle through the unique backedge block.

define i32 @degenerate_header_phi(i32 %n) {
; AMDGPU-LABEL: define i32 @degenerate_header_phi(
; AMDGPU-SAME: i32 [[N:%.*]]) {
; AMDGPU-NEXT:  [[ENTRY:.*]]:
; AMDGPU-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; AMDGPU-NEXT:    br label %[[HEADER:.*]]
; AMDGPU:       [[HEADER]]:
; AMDGPU-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[HEADER_BACKEDGE:.*]] ]
; AMDGPU-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; AMDGPU-NEXT:    [[COND:%.*]] = icmp eq i32 [[I]], [[TID]]
; AMDGPU-NEXT:    br i1 [[COND]], label %[[L1:.*]], label %[[L2:.*]]
; AMDGPU:       [[L1]]:
; AMDGPU-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C1]], label %[[HEADER_BACKEDGE]], label %[[EXIT:.*]]
; AMDGPU:       [[HEADER_BACKEDGE]]:
; AMDGPU-NEXT:    br label %[[HEADER]]
; AMDGPU:       [[L2]]:
; AMDGPU-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; AMDGPU-NEXT:    br i1 [[C2]], label %[[HEADER_BACKEDGE]], label %[[EXIT]]
; AMDGPU:       [[EXIT]]:
; AMDGPU-NEXT:    [[R:%.*]] = add i32 [[I]], 0
; AMDGPU-NEXT:    ret i32 [[R]]
;
; GENERIC-LABEL: define i32 @degenerate_header_phi(
; GENERIC-SAME: i32 [[N:%.*]]) {
; GENERIC-NEXT:  [[ENTRY:.*]]:
; GENERIC-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
; GENERIC-NEXT:    br label %[[HEADER:.*]]
; GENERIC:       [[HEADER]]:
; GENERIC-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[HEADER_BACKEDGE:.*]] ]
; GENERIC-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
; GENERIC-NEXT:    [[COND:%.*]] = icmp eq i32 [[I]], [[TID]]
; GENERIC-NEXT:    br i1 [[COND]], label %[[L1:.*]], label %[[L2:.*]]
; GENERIC:       [[L1]]:
; GENERIC-NEXT:    [[C1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C1]], label %[[HEADER_BACKEDGE]], label %[[EXIT:.*]]
; GENERIC:       [[HEADER_BACKEDGE]]:
; GENERIC-NEXT:    br label %[[HEADER]]
; GENERIC:       [[L2]]:
; GENERIC-NEXT:    [[C2:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
; GENERIC-NEXT:    br i1 [[C2]], label %[[HEADER_BACKEDGE]], label %[[EXIT]]
; GENERIC:       [[EXIT]]:
; GENERIC-NEXT:    [[R:%.*]] = add i32 [[I]], 0
; GENERIC-NEXT:    ret i32 [[R]]
;
entry:
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
  br label %header

header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %l1 ], [ %i.next, %l2 ]
  %p = phi i32 [ 0, %entry ], [ %p, %l1 ], [ 0, %l2 ]
  %i.next = add i32 %i, 1
  %cond = icmp eq i32 %i, %tid
  br i1 %cond, label %l1, label %l2

l1:
  %c1 = icmp slt i32 %i.next, %n
  br i1 %c1, label %header, label %exit

l2:
  %c2 = icmp slt i32 %i.next, %n
  br i1 %c2, label %header, label %exit

exit:
  %r = add i32 %i, %p
  ret i32 %r
}

declare i32 @llvm.amdgcn.workitem.id.x()

attributes #0 = { "amdgpu-flat-work-group-size"="1,1" "amdgpu-no-wwm" }