xref: /llvm-project/llvm/test/Analysis/ScalarEvolution/exit-count-select.ll (revision 0d38f21e4ab7fe7cebe76a9d7c218ec54dba1e98)

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s

; If m is constant, exact-not-taken is umin(n, m)
; https://alive2.llvm.org/ce/z/ZTNXgY
define void @logical_and_m_const(i32 %n) {
; CHECK-LABEL: 'logical_and_m_const'
; CHECK-NEXT:  Classifying expressions for: @logical_and_m_const
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
; CHECK-NEXT:    --> (%cond_i2 umin %cond_i) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_and_m_const
; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 2
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (2 umin %n)
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp ult i32 %i, %n
  %cond_i2 = icmp ult i32 %i, 2
  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  br i1 %cond, label %loop, label %exit
exit:
  ret void
}

; exact-not-taken is umin(2, m) because m participates in the exit branch condition.
; https://alive2.llvm.org/ce/z/rCVMmp
define void @logical_and_nonzero(i32 %m) {
; CHECK-LABEL: 'logical_and_nonzero'
; CHECK-NEXT:  Classifying expressions for: @logical_and_nonzero
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
; CHECK-NEXT:    --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_and_nonzero
; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 2
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (2 umin %m)
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp ult i32 %i, 2
  %cond_i2 = icmp ult i32 %i, %m
  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  br i1 %cond, label %loop, label %exit
exit:
  ret void
}

; exact-not-taken cannot be umin(0, m) because m never participates in the exit branch condition.
; https://alive2.llvm.org/ce/z/rlaN4a
; Instead, it should be just 0.
define void @logical_and_zero(i32 %m) {
; CHECK-LABEL: 'logical_and_zero'
; CHECK-NEXT:  Classifying expressions for: @logical_and_zero
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
; CHECK-NEXT:    --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: false LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_and_zero
; CHECK-NEXT:  Loop %loop: backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp ult i32 %i, 0
  %cond_i2 = icmp ult i32 %i, %m
  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  br i1 %cond, label %loop, label %exit
exit:
  ret void
}

; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
; preventing them from being poison.
; https://alive2.llvm.org/ce/z/8_p-zu
; Currently SCEV is conservative in this case and simply returns unknown.
define void @logical_and_inversed(i32 %n, i32 %m) {
; CHECK-LABEL: 'logical_and_inversed'
; CHECK-NEXT:  Classifying expressions for: @logical_and_inversed
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
; CHECK-NEXT:    --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_and_inversed
; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp uge i32 %i, %n
  %cond_i2 = icmp uge i32 %i, %m
  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  br i1 %cond, label %exit, label %loop
exit:
  ret void
}

; If m is constant,  exact-not-taken is umin(n, m)
; https://alive2.llvm.org/ce/z/RQmJiq
define void @logical_or_m_const(i32 %n) {
; CHECK-LABEL: 'logical_or_m_const'
; CHECK-NEXT:  Classifying expressions for: @logical_or_m_const
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
; CHECK-NEXT:    --> (true + ((true + %cond_i) umin (true + %cond_i2))) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_or_m_const
; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 2
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (2 umin %n)
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp uge i32 %i, %n
  %cond_i2 = icmp uge i32 %i, 2
  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
  br i1 %cond, label %exit, label %loop
exit:
  ret void
}

; exact-not-taken is umin(2, m) because m participates in exit branch condition.
; https://alive2.llvm.org/ce/z/zcHS_d
define void @logical_or_nonzero(i32 %m) {
; CHECK-LABEL: 'logical_or_nonzero'
; CHECK-NEXT:  Classifying expressions for: @logical_or_nonzero
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
; CHECK-NEXT:    --> (true + ((true + %cond_i) umin_seq (true + %cond_i2))) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_or_nonzero
; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 2
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (2 umin %m)
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp uge i32 %i, 2
  %cond_i2 = icmp uge i32 %i, %m
  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
  br i1 %cond, label %exit, label %loop
exit:
  ret void
}

; exact-not-taken cannot be umin(0, m) because m does not participate in exit branch condition.
; https://alive2.llvm.org/ce/z/-dUmmc
; Instead, exact-not-taken should be just 0.
define void @logical_or_zero(i32 %m) {
; CHECK-LABEL: 'logical_or_zero'
; CHECK-NEXT:  Classifying expressions for: @logical_or_zero
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
; CHECK-NEXT:    --> (true + ((true + %cond_i) umin_seq (true + %cond_i2))) U: full-set S: full-set Exits: true LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_or_zero
; CHECK-NEXT:  Loop %loop: backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i32 0
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp uge i32 %i, 0
  %cond_i2 = icmp uge i32 %i, %m
  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
  br i1 %cond, label %exit, label %loop
exit:
  ret void
}

; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
; preventing them from being poison.
; https://alive2.llvm.org/ce/z/VaCu9C
; Currently SCEV is conservative in this case and simply returns unknown.
define void @logical_or_inversed(i32 %n, i32 %m) {
; CHECK-LABEL: 'logical_or_inversed'
; CHECK-NEXT:  Classifying expressions for: @logical_or_inversed
; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %i.next = add i32 %i, 1
; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
; CHECK-NEXT:    --> (true + ((true + %cond_i) umin_seq (true + %cond_i2))) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT:  Determining loop execution counts for: @logical_or_inversed
; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
;
entry:
  br label %loop
loop:
  %i = phi i32 [0, %entry], [%i.next, %loop]
  %i.next = add i32 %i, 1
  %cond_i = icmp ult i32 %i, %n
  %cond_i2 = icmp ult i32 %i, %m
  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
  br i1 %cond, label %loop, label %exit
exit:
  ret void
}