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