xref: /llvm-project/llvm/test/Transforms/FixIrreducible/basic.ll (revision fa4cc9ddd58eb9fef2497e678873ff3b495340a3)

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s
; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s
; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s

define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
; CHECK-LABEL: @basic(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       left:
; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[L:%.*]] = add i32 [[L_PHI]], 1
; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       right:
; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
; CHECK-NEXT:    ret i32 [[Z]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
;
entry:
  br i1 %PredEntry, label %left, label %right

left:
  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  %L = add i32 %L.phi, 1
  br i1 %PredLeft, label %right, label %exit

right:
  %R.phi = phi i32 [%Y, %entry], [%L, %left]
  br i1 %PredRight, label %left, label %exit

exit:
  %Z = phi i32 [%L, %left], [%R.phi, %right]
  ret i32 %Z
}

define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
; CHECK-LABEL: @feedback_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       left:
; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       right:
; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
; CHECK-NEXT:    ret i32 [[Z]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
;
entry:
  br i1 %PredEntry, label %left, label %right

left:
  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  br i1 %PredLeft, label %right, label %exit

right:
  %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]
  br i1 %PredRight, label %left, label %exit

exit:
  %Z = phi i32 [%L.phi, %left], [%R.phi, %right]
  ret i32 %Z
}

define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @multiple_predecessors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[EXIT:%.*]]
; CHECK:       D:
; CHECK-NEXT:    [[D_PHI:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI]], 1
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
; CHECK:       exit:
; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ [[D_INC]], [[D]] ]
; CHECK-NEXT:    ret i32 [[RET]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ]
; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ]
; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ]
; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.inc = add i32 %X, 1
  br i1 %PredA, label %C, label %D

B:
  br i1 %PredB, label %D, label %C

C:
  %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]
  br i1 %PredC, label %D, label %exit

D:
  %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]
  %D.inc = add i32 %D.phi, 1
  br i1 %PredD, label %exit, label %C

exit:
  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
  ret i32 %ret
}

define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @separate_predecessors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       C:
; CHECK-NEXT:    [[C_PHI:%.*]] = phi i32 [ [[D_INC:%.*]], [[D:%.*]] ], [ [[C_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    [[D_INC]] = add i32 [[D_PHI_MOVED:%.*]], 1
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[C:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[D_INC]], [[D]] ]
; CHECK-NEXT:    ret i32 [[RET]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ poison, [[B]] ], [ [[X]], [[A]] ]
; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[Y:%.*]], [[B]] ], [ poison, [[A]] ]
; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ true, [[B]] ], [ false, [[A]] ]
; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D]], label [[C]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.inc = add i32 %X, 1
  br label %C

B:
  br label %D

C:
  %C.phi = phi i32 [%X, %A], [%D.inc, %D]
  br i1 %PredC, label %exit, label %D

D:
  %D.phi = phi i32 [%Y, %B], [%C.phi, %C]
  %D.inc = add i32 %D.phi, 1
  br i1 %PredD, label %exit, label %C

exit:
  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
  ret i32 %ret
}

define void @four_headers(i1 %PredEntry, i1 %PredX, i1  %PredY, i1 %PredD) {
; CHECK-LABEL: @four_headers(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDY_INV:%.*]] = xor i1 [[PREDY:%.*]], true
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]]
; CHECK:       X:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       Y:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       A:
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[C:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[A:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ [[PREDY_INV]], [[Y]] ], [ false, [[X]] ]
; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[C]] ], [ true, [[Y]] ], [ false, [[X]] ]
; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ false, [[C]] ], [ false, [[Y]] ], [ [[PREDX:%.*]], [[X]] ]
; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[IRR_GUARD1:%.*]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[IRR_GUARD2:%.*]]
; CHECK:       irr.guard2:
; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B]]
;
entry:
  br i1 %PredEntry, label %X, label %Y

X:
  br i1 %PredX, label %A, label %B

Y:
  br i1 %PredY, label %C, label %D

A:
  br label %B

B:
  br label %C

C:
  br label %D

D:
  br i1 %PredD, label %exit, label %A

exit:
  ret void
}

define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @hidden_nodes(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_PHI:%.*]] = phi i32 [ [[C_INC:%.*]], [[E:%.*]] ], [ [[A_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[A_PHI]], 1
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       B:
; CHECK-NEXT:    br label [[C:%.*]]
; CHECK:       C:
; CHECK-NEXT:    [[C_INC]] = add i32 [[B_PHI_MOVED:%.*]], 1
; CHECK-NEXT:    br label [[D:%.*]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E]]
; CHECK:       E:
; CHECK-NEXT:    br label [[A:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 [[B_PHI_MOVED]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[A_PHI_MOVED]] = phi i32 [ [[A_PHI_MOVED]], [[A]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ [[A_INC]], [[A]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[A]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.phi = phi i32 [%X, %entry], [%C.inc, %E]
  %A.inc = add i32 %A.phi, 1
  br label %B

B:
  %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]
  br label %C

C:
  %C.inc = add i32 %B.phi, 1
  br label %D

D:
  br i1 %PredD, label %exit, label %E

E:
  br label %A

exit:
  ret i32 %B.phi
}