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