shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Analysis/ScalarEvolution/exit-count-select.ll
Philip Reames 0d38f21e4a [SCEV] Extend type hint in analysis output to all backedge kinds 
This extends the work from 7755c26 to all of the different backend
taken count kinds that we print for the scev analysis printer.  As
before, the goal is to cut down on confusion as i4 -1 is a very
different (unsigned) value from i32 -1.
2024-03-06 13:08:05 -08:00

247 lines
12 KiB
LLVM
Raw Permalink Blame History

; 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
}
Reference in New Issue View Git Blame Copy Permalink