llvm/test/Analysis/ScalarEvolution/exit-count-select.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s
   3
   4 ; If m is constant, exact-not-taken is umin(n, m)
   5 ; https://alive2.llvm.org/ce/z/ZTNXgY
   6 define void @logical_and_m_const(i32 %n) {
   7 ; CHECK-LABEL: 'logical_and_m_const'
   8 ; CHECK-NEXT:  Classifying expressions for: @logical_and_m_const
   9 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  10 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
  11 ; CHECK-NEXT:    %i.next = add i32 %i, 1
  12 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
  13 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  14 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  15 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_m_const
  16 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
  17 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
  18 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %n)
  19 ; CHECK-NEXT:   Predicates:
  20 ; CHECK:       Loop %loop: Trip multiple is 1
  21 ;
  22 entry:
  23   br label %loop
  24 loop:
  25   %i = phi i32 [0, %entry], [%i.next, %loop]
  26   %i.next = add i32 %i, 1
  27   %cond_i = icmp ult i32 %i, %n
  28   %cond_i2 = icmp ult i32 %i, 2
  29   %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  30   br i1 %cond, label %loop, label %exit
  31 exit:
  32   ret void
  33 }
  34
  35 ; exact-not-taken is umin(2, m) because m participates in the exit branch condition.
  36 ; https://alive2.llvm.org/ce/z/rCVMmp
  37 define void @logical_and_nonzero(i32 %m) {
  38 ; CHECK-LABEL: 'logical_and_nonzero'
  39 ; CHECK-NEXT:  Classifying expressions for: @logical_and_nonzero
  40 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  41 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
  42 ; CHECK-NEXT:    %i.next = add i32 %i, 1
  43 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
  44 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  45 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  46 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_nonzero
  47 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
  48 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
  49 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %m)
  50 ; CHECK-NEXT:   Predicates:
  51 ; CHECK:       Loop %loop: Trip multiple is 1
  52 ;
  53 entry:
  54   br label %loop
  55 loop:
  56   %i = phi i32 [0, %entry], [%i.next, %loop]
  57   %i.next = add i32 %i, 1
  58   %cond_i = icmp ult i32 %i, 2
  59   %cond_i2 = icmp ult i32 %i, %m
  60   %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  61   br i1 %cond, label %loop, label %exit
  62 exit:
  63   ret void
  64 }
  65
  66 ; exact-not-taken cannot be umin(0, m) because m never participates in the exit branch condition.
  67 ; https://alive2.llvm.org/ce/z/rlaN4a
  68 ; Instead, it should be just 0.
  69 define void @logical_and_zero(i32 %m) {
  70 ; CHECK-LABEL: 'logical_and_zero'
  71 ; CHECK-NEXT:  Classifying expressions for: @logical_and_zero
  72 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  73 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
  74 ; CHECK-NEXT:    %i.next = add i32 %i, 1
  75 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
  76 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  77 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  78 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_zero
  79 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
  80 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
  81 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
  82 ; CHECK-NEXT:   Predicates:
  83 ; CHECK:       Loop %loop: Trip multiple is 1
  84 ;
  85 entry:
  86   br label %loop
  87 loop:
  88   %i = phi i32 [0, %entry], [%i.next, %loop]
  89   %i.next = add i32 %i, 1
  90   %cond_i = icmp ult i32 %i, 0
  91   %cond_i2 = icmp ult i32 %i, %m
  92   %cond = select i1 %cond_i, i1 %cond_i2, i1 false
  93   br i1 %cond, label %loop, label %exit
  94 exit:
  95   ret void
  96 }
  97
  98 ; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
  99 ; preventing them from being poison.
 100 ; https://alive2.llvm.org/ce/z/8_p-zu
 101 ; Currently SCEV is conservative in this case and simply returns unknown.
 102 define void @logical_and_inversed(i32 %n, i32 %m) {
 103 ; CHECK-LABEL: 'logical_and_inversed'
 104 ; CHECK-NEXT:  Classifying expressions for: @logical_and_inversed
 105 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 106 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 107 ; CHECK-NEXT:    %i.next = add i32 %i, 1
 108 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 109 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
 110 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 111 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_inversed
 112 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 113 ; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
 114 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 115 ;
 116 entry:
 117   br label %loop
 118 loop:
 119   %i = phi i32 [0, %entry], [%i.next, %loop]
 120   %i.next = add i32 %i, 1
 121   %cond_i = icmp uge i32 %i, %n
 122   %cond_i2 = icmp uge i32 %i, %m
 123   %cond = select i1 %cond_i, i1 %cond_i2, i1 false
 124   br i1 %cond, label %exit, label %loop
 125 exit:
 126   ret void
 127 }
 128
 129 ; If m is constant,  exact-not-taken is umin(n, m)
 130 ; https://alive2.llvm.org/ce/z/RQmJiq
 131 define void @logical_or_m_const(i32 %n) {
 132 ; CHECK-LABEL: 'logical_or_m_const'
 133 ; CHECK-NEXT:  Classifying expressions for: @logical_or_m_const
 134 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 135 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
 136 ; CHECK-NEXT:    %i.next = add i32 %i, 1
 137 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
 138 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 139 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 140 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_m_const
 141 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
 142 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
 143 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %n)
 144 ; CHECK-NEXT:   Predicates:
 145 ; CHECK:       Loop %loop: Trip multiple is 1
 146 ;
 147 entry:
 148   br label %loop
 149 loop:
 150   %i = phi i32 [0, %entry], [%i.next, %loop]
 151   %i.next = add i32 %i, 1
 152   %cond_i = icmp uge i32 %i, %n
 153   %cond_i2 = icmp uge i32 %i, 2
 154   %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 155   br i1 %cond, label %exit, label %loop
 156 exit:
 157   ret void
 158 }
 159
 160 ; exact-not-taken is umin(2, m) because m participates in exit branch condition.
 161 ; https://alive2.llvm.org/ce/z/zcHS_d
 162 define void @logical_or_nonzero(i32 %m) {
 163 ; CHECK-LABEL: 'logical_or_nonzero'
 164 ; CHECK-NEXT:  Classifying expressions for: @logical_or_nonzero
 165 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 166 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
 167 ; CHECK-NEXT:    %i.next = add i32 %i, 1
 168 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
 169 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 170 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 171 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_nonzero
 172 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
 173 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
 174 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %m)
 175 ; CHECK-NEXT:   Predicates:
 176 ; CHECK:       Loop %loop: Trip multiple is 1
 177 ;
 178 entry:
 179   br label %loop
 180 loop:
 181   %i = phi i32 [0, %entry], [%i.next, %loop]
 182   %i.next = add i32 %i, 1
 183   %cond_i = icmp uge i32 %i, 2
 184   %cond_i2 = icmp uge i32 %i, %m
 185   %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 186   br i1 %cond, label %exit, label %loop
 187 exit:
 188   ret void
 189 }
 190
 191 ; exact-not-taken cannot be umin(0, m) because m does not participate in exit branch condition.
 192 ; https://alive2.llvm.org/ce/z/-dUmmc
 193 ; Instead, exact-not-taken should be just 0.
 194 define void @logical_or_zero(i32 %m) {
 195 ; CHECK-LABEL: 'logical_or_zero'
 196 ; CHECK-NEXT:  Classifying expressions for: @logical_or_zero
 197 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 198 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
 199 ; CHECK-NEXT:    %i.next = add i32 %i, 1
 200 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
 201 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 202 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 203 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_zero
 204 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
 205 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
 206 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
 207 ; CHECK-NEXT:   Predicates:
 208 ; CHECK:       Loop %loop: Trip multiple is 1
 209 ;
 210 entry:
 211   br label %loop
 212 loop:
 213   %i = phi i32 [0, %entry], [%i.next, %loop]
 214   %i.next = add i32 %i, 1
 215   %cond_i = icmp uge i32 %i, 0
 216   %cond_i2 = icmp uge i32 %i, %m
 217   %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 218   br i1 %cond, label %exit, label %loop
 219 exit:
 220   ret void
 221 }
 222
 223 ; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
 224 ; preventing them from being poison.
 225 ; https://alive2.llvm.org/ce/z/VaCu9C
 226 ; Currently SCEV is conservative in this case and simply returns unknown.
 227 define void @logical_or_inversed(i32 %n, i32 %m) {
 228 ; CHECK-LABEL: 'logical_or_inversed'
 229 ; CHECK-NEXT:  Classifying expressions for: @logical_or_inversed
 230 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 231 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 232 ; CHECK-NEXT:    %i.next = add i32 %i, 1
 233 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 234 ; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 235 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 236 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_inversed
 237 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 238 ; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
 239 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 240 ;
 241 entry:
 242   br label %loop
 243 loop:
 244   %i = phi i32 [0, %entry], [%i.next, %loop]
 245   %i.next = add i32 %i, 1
 246   %cond_i = icmp ult i32 %i, %n
 247   %cond_i2 = icmp ult i32 %i, %m
 248   %cond = select i1 %cond_i, i1 true, i1 %cond_i2
 249   br i1 %cond, label %loop, label %exit
 250 exit:
 251   ret void
 252 }