llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
   3
   4 ; Tests for checking the trip multiple in loops where we cmp induction variables
   5 ; against Min/Max SCEVs
   6
   7 define void @nomulitply(i32 noundef %a, i32 noundef %b) {
   8 ; CHECK-LABEL: 'nomulitply'
   9 ; CHECK-NEXT:  Classifying expressions for: @nomulitply
  10 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %a, i32 %b
  11 ; CHECK-NEXT:    --> (%a umin %b) U: full-set S: full-set
  12 ; CHECK-NEXT:    %i.08 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  13 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + (%a umin %b)) LoopDispositions: { %for.body: Computable }
  14 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.08, 1
  15 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: (%a umin %b) LoopDispositions: { %for.body: Computable }
  16 ; CHECK-NEXT:  Determining loop execution counts for: @nomulitply
  17 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (%a umin %b))
  18 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
  19 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (%a umin %b))
  20 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (%a umin %b))
  21 ; CHECK-NEXT:   Predicates:
  22 ; CHECK:       Loop %for.body: Trip multiple is 1
  23 ;
  24 ; No information about a or b. Trip multiple is 1.
  25 ; void nomulitple(unsigned a, unsigned b) {
  26 ;   int N = a < b ? a : b;
  27 ;   for (int i = 0; i < N; ++i) {
  28 ;     foo();
  29 ;   }
  30 ; }
  31
  32 entry:
  33   %cmp = icmp ult i32 %a, %b
  34   %cond = select i1 %cmp, i32 %a, i32 %b
  35   %cmp17 = icmp sgt i32 %cond, 0
  36   br i1 %cmp17, label %for.body, label %for.cond.cleanup
  37
  38 for.cond.cleanup:                                 ; preds = %for.body, %entry
  39   ret void
  40
  41 for.body:                                         ; preds = %entry, %for.body
  42   %i.08 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  43   tail call void (...) @foo() #2
  44   %inc = add nuw nsw i32 %i.08, 1
  45   %exitcond.not = icmp eq i32 %inc, %cond
  46   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
  47 }
  48
  49 define void @umin(i32 noundef %a, i32 noundef %b) {
  50 ; CHECK-LABEL: 'umin'
  51 ; CHECK-NEXT:  Classifying expressions for: @umin
  52 ; CHECK-NEXT:    %mul = shl i32 %a, 1
  53 ; CHECK-NEXT:    --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)
  54 ; CHECK-NEXT:    %mul1 = shl i32 %b, 2
  55 ; CHECK-NEXT:    --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)
  56 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
  57 ; CHECK-NEXT:    --> ((2 * %a) umin (4 * %b)) U: [0,-3) S: [-2147483648,2147483647)
  58 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  59 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a) umin (4 * %b))) LoopDispositions: { %for.body: Computable }
  60 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
  61 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a) umin (4 * %b)) LoopDispositions: { %for.body: Computable }
  62 ; CHECK-NEXT:  Determining loop execution counts for: @umin
  63 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
  64 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
  65 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
  66 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a) umin (4 * %b)))
  67 ; CHECK-NEXT:   Predicates:
  68 ; CHECK:       Loop %for.body: Trip multiple is 1
  69 ;
  70 ; void umin(unsigned a, unsigned b) {
  71 ;   a *= 2;
  72 ;   b *= 4;
  73 ;   int N = a < b ? a : b;
  74 ;   for (int i = 0; i < N; ++i) {
  75 ;     foo();
  76 ;   }
  77 ;  }
  78
  79 entry:
  80   %mul = shl i32 %a, 1
  81   %mul1 = shl i32 %b, 2
  82   %cmp = icmp ult i32 %mul, %mul1
  83   %cond = select i1 %cmp, i32 %mul, i32 %mul1
  84   %cmp210 = icmp sgt i32 %cond, 0
  85   br i1 %cmp210, label %for.body, label %for.cond.cleanup
  86
  87 for.cond.cleanup:                                 ; preds = %for.body, %entry
  88   ret void
  89
  90 for.body:                                         ; preds = %entry, %for.body
  91   %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  92   tail call void (...) @foo() #2
  93   %inc = add nuw nsw i32 %i.011, 1
  94   %exitcond.not = icmp eq i32 %inc, %cond
  95   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
  96 }
  97
  98
  99 define void @umax(i32 noundef %a, i32 noundef %b) {
 100 ; CHECK-LABEL: 'umax'
 101 ; CHECK-NEXT:  Classifying expressions for: @umax
 102 ; CHECK-NEXT:    %mul = shl i32 %a, 1
 103 ; CHECK-NEXT:    --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)
 104 ; CHECK-NEXT:    %mul1 = shl i32 %b, 2
 105 ; CHECK-NEXT:    --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)
 106 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
 107 ; CHECK-NEXT:    --> ((2 * %a) umax (4 * %b)) U: [0,-1) S: [-2147483648,2147483647)
 108 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 109 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a) umax (4 * %b))) LoopDispositions: { %for.body: Computable }
 110 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
 111 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a) umax (4 * %b)) LoopDispositions: { %for.body: Computable }
 112 ; CHECK-NEXT:  Determining loop execution counts for: @umax
 113 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
 114 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
 115 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
 116 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a) umax (4 * %b)))
 117 ; CHECK-NEXT:   Predicates:
 118 ; CHECK:       Loop %for.body: Trip multiple is 2
 119 ;
 120
 121 ; void umax(unsigned a, unsigned b) {
 122 ;   a *= 2;
 123 ;   b *= 4;
 124 ;   int N = a > b ? a : b;
 125 ;   for (int i = 0; i < N; ++i) {
 126 ;     foo();
 127 ;   }
 128 ; }
 129
 130 entry:
 131   %mul = shl i32 %a, 1
 132   %mul1 = shl i32 %b, 2
 133   %cmp = icmp ugt i32 %mul, %mul1
 134   %cond = select i1 %cmp, i32 %mul, i32 %mul1
 135   %cmp210 = icmp sgt i32 %cond, 0
 136   br i1 %cmp210, label %for.body, label %for.cond.cleanup
 137
 138 for.cond.cleanup:                                 ; preds = %for.body, %entry
 139   ret void
 140
 141 for.body:                                         ; preds = %entry, %for.body
 142   %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 143   tail call void (...) @foo() #2
 144   %inc = add nuw nsw i32 %i.011, 1
 145   %exitcond.not = icmp eq i32 %inc, %cond
 146   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 147 }
 148
 149 define void @smin(i32 noundef %a, i32 noundef %b) {
 150 ; CHECK-LABEL: 'smin'
 151 ; CHECK-NEXT:  Classifying expressions for: @smin
 152 ; CHECK-NEXT:    %mul = shl nsw i32 %a, 1
 153 ; CHECK-NEXT:    --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)
 154 ; CHECK-NEXT:    %mul1 = shl nsw i32 %b, 2
 155 ; CHECK-NEXT:    --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)
 156 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
 157 ; CHECK-NEXT:    --> ((2 * %a)<nsw> smin (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483645)
 158 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 159 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
 160 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
 161 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a)<nsw> smin (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
 162 ; CHECK-NEXT:  Determining loop execution counts for: @smin
 163 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
 164 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
 165 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
 166 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>))
 167 ; CHECK-NEXT:   Predicates:
 168 ; CHECK:       Loop %for.body: Trip multiple is 1
 169 ;
 170 ; void smin(signed a, signed b) {
 171 ;   a *= 2;
 172 ;   b *= 4;
 173 ;   int N = a < b ? a : b;
 174 ;   for (int i = 0; i < N; ++i) {
 175 ;     foo();
 176 ;   }
 177 ; }
 178
 179 entry:
 180   %mul = shl nsw i32 %a, 1
 181   %mul1 = shl nsw i32 %b, 2
 182   %cmp = icmp slt i32 %mul, %mul1
 183   %cond = select i1 %cmp, i32 %mul, i32 %mul1
 184   %cmp210 = icmp sgt i32 %cond, 0
 185   br i1 %cmp210, label %for.body, label %for.cond.cleanup
 186
 187 for.cond.cleanup:                                 ; preds = %for.body, %entry
 188   ret void
 189
 190 for.body:                                         ; preds = %entry, %for.body
 191   %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 192   tail call void (...) @foo() #2
 193   %inc = add nuw nsw i32 %i.011, 1
 194   %exitcond.not = icmp eq i32 %inc, %cond
 195   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 196 }
 197
 198 define void @smax(i32 noundef %a, i32 noundef %b) {
 199 ; CHECK-LABEL: 'smax'
 200 ; CHECK-NEXT:  Classifying expressions for: @smax
 201 ; CHECK-NEXT:    %mul = shl nsw i32 %a, 1
 202 ; CHECK-NEXT:    --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)
 203 ; CHECK-NEXT:    %mul1 = shl nsw i32 %b, 2
 204 ; CHECK-NEXT:    --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)
 205 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
 206 ; CHECK-NEXT:    --> ((2 * %a)<nsw> smax (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483647)
 207 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 208 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable }
 209 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
 210 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a)<nsw> smax (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable }
 211 ; CHECK-NEXT:  Determining loop execution counts for: @smax
 212 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
 213 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -3
 214 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
 215 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>))
 216 ; CHECK-NEXT:   Predicates:
 217 ; CHECK:       Loop %for.body: Trip multiple is 2
 218 ;
 219 ; void smax(signed a, signed b) {
 220 ;   a *= 2;
 221 ;   b *= 4;
 222 ;   int N = a > b ? a : b;
 223 ;   for (int i = 0; i < N; ++i) {
 224 ;     foo();
 225 ;   }
 226 ; }
 227
 228 entry:
 229   %mul = shl nsw i32 %a, 1
 230   %mul1 = shl nsw i32 %b, 2
 231   %cmp = icmp sgt i32 %mul, %mul1
 232   %cond = select i1 %cmp, i32 %mul, i32 %mul1
 233   %cmp210 = icmp sgt i32 %cond, 0
 234   br i1 %cmp210, label %for.body, label %for.cond.cleanup
 235
 236 for.cond.cleanup:                                 ; preds = %for.body, %entry
 237   ret void
 238
 239 for.body:                                         ; preds = %entry, %for.body
 240   %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 241   tail call void (...) @foo() #2
 242   %inc = add nuw nsw i32 %i.011, 1
 243   %exitcond.not = icmp eq i32 %inc, %cond
 244   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 245 }
 246
 247 define void @umin_seq2(i32 %n, i32 %m) {
 248 ; CHECK-LABEL: 'umin_seq2'
 249 ; CHECK-NEXT:  Classifying expressions for: @umin_seq2
 250 ; CHECK-NEXT:    %n.2 = shl nsw i32 %n, 1
 251 ; CHECK-NEXT:    --> (2 * %n) U: [0,-1) S: [-2147483648,2147483647)
 252 ; CHECK-NEXT:    %m.2 = shl nsw i32 %m, 4
 253 ; CHECK-NEXT:    --> (16 * %m) U: [0,-15) S: [-2147483648,2147483633)
 254 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 255 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))) LoopDispositions: { %loop: Computable }
 256 ; CHECK-NEXT:    %i.next = add nuw nsw i32 %i, 1
 257 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-15) S: [1,-15) Exits: (1 + ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))))<nuw> LoopDispositions: { %loop: Computable }
 258 ; CHECK-NEXT:    %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
 259 ; CHECK-NEXT:    --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 260 ; CHECK-NEXT:  Determining loop execution counts for: @umin_seq2
 261 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m))))
 262 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -17
 263 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m))))
 264 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m))))
 265 ; CHECK-NEXT:   Predicates:
 266 ; CHECK:       Loop %loop: Trip multiple is 1
 267 ;
 268 ; Can't find that trip multiple is 2 for this case of umin_seq
 269 entry:
 270   %n.2 = shl nsw i32 %n, 1
 271   %m.2 = shl nsw i32 %m, 4
 272   br label %loop
 273 loop:
 274   %i = phi i32 [0, %entry], [%i.next, %loop]
 275   tail call void (...) @foo() #2
 276   %i.next = add nuw nsw i32 %i, 1
 277   %cond_p0 = icmp ult i32 %i.next, %n.2
 278   %cond_p1 = icmp ult i32 %i.next, %m.2
 279   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
 280   br i1 %cond, label %loop, label %exit
 281 exit:
 282   ret void
 283 }
 284
 285 define void @umin-3and6(i32 noundef %a, i32 noundef %b) {
 286 ; CHECK-LABEL: 'umin-3and6'
 287 ; CHECK-NEXT:  Classifying expressions for: @umin-3and6
 288 ; CHECK-NEXT:    %mul = mul i32 %a, 3
 289 ; CHECK-NEXT:    --> (3 * %a) U: full-set S: full-set
 290 ; CHECK-NEXT:    %mul1 = mul i32 %b, 6
 291 ; CHECK-NEXT:    --> (6 * %b) U: [0,-1) S: [-2147483648,2147483647)
 292 ; CHECK-NEXT:    %cond = select i1 %cmp, i32 %mul, i32 %mul1
 293 ; CHECK-NEXT:    --> ((3 * %a) umin (6 * %b)) U: [0,-1) S: full-set
 294 ; CHECK-NEXT:    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 295 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((3 * %a) umin (6 * %b))) LoopDispositions: { %for.body: Computable }
 296 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.011, 1
 297 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((3 * %a) umin (6 * %b)) LoopDispositions: { %for.body: Computable }
 298 ; CHECK-NEXT:  Determining loop execution counts for: @umin-3and6
 299 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
 300 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
 301 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
 302 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + ((3 * %a) umin (6 * %b)))
 303 ; CHECK-NEXT:   Predicates:
 304 ; CHECK:       Loop %for.body: Trip multiple is 1
 305 ;
 306 ; Trip multiple is 1 because we use GetMinTrailingZeros() to compute trip multiples.
 307 ; SCEV cannot compute that the trip multiple is 3.
 308 ; void umin(unsigned a, unsigned b) {
 309 ;   a *= 3;
 310 ;   b *= 6;
 311 ;   int N = a < b ? a : b;
 312 ;   for (int i = 0; i < N; ++i) {
 313 ;     foo();
 314 ;   }
 315 ;  }
 316
 317 entry:
 318   %mul = mul i32 %a, 3
 319   %mul1 = mul i32 %b, 6
 320   %cmp = icmp ult i32 %mul, %mul1
 321   %cond = select i1 %cmp, i32 %mul, i32 %mul1
 322   %cmp210 = icmp sgt i32 %cond, 0
 323   br i1 %cmp210, label %for.body, label %for.cond.cleanup
 324
 325 for.cond.cleanup:                                 ; preds = %for.body, %entry
 326   ret void
 327
 328 for.body:                                         ; preds = %entry, %for.body
 329   %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 330   tail call void (...) @foo() #2
 331   %inc = add nuw nsw i32 %i.011, 1
 332   %exitcond.not = icmp eq i32 %inc, %cond
 333   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 334 }
 335
 336 declare void @foo(...) local_unnamed_addr #1