llvm/test/Analysis/ScalarEvolution/trip-multiple.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt -passes='print<scalar-evolution>,verify<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
   3
   4 ; Test trip multiples with functions that look like:
   5
   6 ; void foo();
   7 ; void square(unsigned num) {
   8 ;     if (num % 5 == 0)
   9 ;     for (unsigned i = 0; i < num; ++i)
  10 ;         foo();
  11 ; }
  12
  13 declare void @foo(...)
  14
  15 define void @trip_multiple_3(i32 noundef %num) {
  16 ; CHECK-LABEL: 'trip_multiple_3'
  17 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_3
  18 ; CHECK-NEXT:    %rem = urem i32 %num, 3
  19 ; CHECK-NEXT:    --> ((-3 * (%num /u 3)) + %num) U: full-set S: full-set
  20 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
  21 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
  22 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  23 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-1) S: [0,-1) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
  24 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
  25 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,0) S: [1,0) Exits: %num LoopDispositions: { %for.body: Computable }
  26 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_3
  27 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
  28 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
  29 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
  30 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
  31 ; CHECK-NEXT:   Predicates:
  32 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 3
  33 ;
  34 entry:
  35   %rem = urem i32 %num, 3
  36   %cmp = icmp eq i32 %rem, 0
  37   %cmp14 = icmp ne i32 %num, 0
  38   %or.cond = and i1 %cmp, %cmp14
  39   br i1 %or.cond, label %for.body, label %if.end
  40
  41 for.body:                                         ; preds = %entry, %for.body
  42   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  43   tail call void (...) @foo() #2
  44   %inc = add nuw i32 %i.05, 1
  45   %exitcond.not = icmp eq i32 %inc, %num
  46   br i1 %exitcond.not, label %if.end, label %for.body
  47
  48 if.end:                                           ; preds = %for.body, %entry
  49   ret void
  50 }
  51 define void @trip_multiple_4(i32 noundef %num) {
  52 ; CHECK-LABEL: 'trip_multiple_4'
  53 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_4
  54 ; CHECK-NEXT:    %rem = urem i32 %num, 4
  55 ; CHECK-NEXT:    --> (zext i2 (trunc i32 %num to i2) to i32) U: [0,4) S: [0,4)
  56 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
  57 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
  58 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  59 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-4) S: [0,-4) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
  60 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
  61 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
  62 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_4
  63 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
  64 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
  65 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
  66 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
  67 ; CHECK-NEXT:   Predicates:
  68 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 4
  69 ;
  70 entry:
  71   %rem = urem i32 %num, 4
  72   %cmp = icmp eq i32 %rem, 0
  73   %cmp14 = icmp ne i32 %num, 0
  74   %or.cond = and i1 %cmp, %cmp14
  75   br i1 %or.cond, label %for.body, label %if.end
  76
  77 for.body:                                         ; preds = %entry, %for.body
  78   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  79   tail call void (...) @foo() #2
  80   %inc = add nuw i32 %i.05, 1
  81   %exitcond.not = icmp eq i32 %inc, %num
  82   br i1 %exitcond.not, label %if.end, label %for.body
  83
  84 if.end:                                           ; preds = %for.body, %entry
  85   ret void
  86 }
  87
  88 define void @trip_multiple_5(i32 noundef %num) {
  89 ; CHECK-LABEL: 'trip_multiple_5'
  90 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_5
  91 ; CHECK-NEXT:    %rem = urem i32 %num, 5
  92 ; CHECK-NEXT:    --> ((-5 * (%num /u 5)) + %num) U: full-set S: full-set
  93 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
  94 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
  95 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  96 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-1) S: [0,-1) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
  97 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
  98 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,0) S: [1,0) Exits: %num LoopDispositions: { %for.body: Computable }
  99 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_5
 100 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 101 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
 102 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 103 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 104 ; CHECK-NEXT:   Predicates:
 105 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 5
 106 ;
 107 entry:
 108   %rem = urem i32 %num, 5
 109   %cmp = icmp eq i32 %rem, 0
 110   %cmp14 = icmp ne i32 %num, 0
 111   %or.cond = and i1 %cmp, %cmp14
 112   br i1 %or.cond, label %for.body, label %if.end
 113
 114 for.body:                                         ; preds = %entry, %for.body
 115   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 116   tail call void (...) @foo() #2
 117   %inc = add nuw i32 %i.05, 1
 118   %exitcond.not = icmp eq i32 %inc, %num
 119   br i1 %exitcond.not, label %if.end, label %for.body
 120
 121 if.end:                                           ; preds = %for.body, %entry
 122   ret void
 123 }
 124
 125 define void @trip_multiple_6(i32 noundef %num) {
 126 ; CHECK-LABEL: 'trip_multiple_6'
 127 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_6
 128 ; CHECK-NEXT:    %rem = urem i32 %num, 6
 129 ; CHECK-NEXT:    --> ((-6 * (%num /u 6)) + %num) U: full-set S: full-set
 130 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
 131 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
 132 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 133 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-4) S: [0,-4) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
 134 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 135 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 136 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_6
 137 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 138 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 139 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 140 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 141 ; CHECK-NEXT:   Predicates:
 142 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 6
 143 ;
 144 entry:
 145   %rem = urem i32 %num, 6
 146   %cmp = icmp eq i32 %rem, 0
 147   %cmp14 = icmp ne i32 %num, 0
 148   %or.cond = and i1 %cmp, %cmp14
 149   br i1 %or.cond, label %for.body, label %if.end
 150
 151 for.body:                                         ; preds = %entry, %for.body
 152   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 153   tail call void (...) @foo() #2
 154   %inc = add nuw i32 %i.05, 1
 155   %exitcond.not = icmp eq i32 %inc, %num
 156   br i1 %exitcond.not, label %if.end, label %for.body
 157
 158 if.end:                                           ; preds = %for.body, %entry
 159   ret void
 160 }
 161
 162 define void @trip_multiple_7(i32 noundef %num) {
 163 ; CHECK-LABEL: 'trip_multiple_7'
 164 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_7
 165 ; CHECK-NEXT:    %rem = urem i32 %num, 7
 166 ; CHECK-NEXT:    --> ((-7 * (%num /u 7)) + %num) U: full-set S: full-set
 167 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
 168 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
 169 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 170 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-4) S: [0,-4) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
 171 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 172 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 173 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_7
 174 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 175 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 176 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 177 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 178 ; CHECK-NEXT:   Predicates:
 179 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 7
 180 ;
 181 entry:
 182   %rem = urem i32 %num, 7
 183   %cmp = icmp eq i32 %rem, 0
 184   %cmp14 = icmp ne i32 %num, 0
 185   %or.cond = and i1 %cmp, %cmp14
 186   br i1 %or.cond, label %for.body, label %if.end
 187
 188 for.body:                                         ; preds = %entry, %for.body
 189   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 190   tail call void (...) @foo() #2
 191   %inc = add nuw i32 %i.05, 1
 192   %exitcond.not = icmp eq i32 %inc, %num
 193   br i1 %exitcond.not, label %if.end, label %for.body
 194
 195 if.end:                                           ; preds = %for.body, %entry
 196   ret void
 197 }
 198
 199 define void @trip_multiple_8(i32 noundef %num) {
 200 ; CHECK-LABEL: 'trip_multiple_8'
 201 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_8
 202 ; CHECK-NEXT:    %rem = urem i32 %num, 8
 203 ; CHECK-NEXT:    --> (zext i3 (trunc i32 %num to i3) to i32) U: [0,8) S: [0,8)
 204 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
 205 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
 206 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 207 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-8) S: [0,-8) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
 208 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 209 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-7) S: [1,-7) Exits: %num LoopDispositions: { %for.body: Computable }
 210 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_8
 211 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 212 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -9
 213 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 214 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 215 ; CHECK-NEXT:   Predicates:
 216 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 8
 217 ;
 218 entry:
 219   %rem = urem i32 %num, 8
 220   %cmp = icmp eq i32 %rem, 0
 221   %cmp14 = icmp ne i32 %num, 0
 222   %or.cond = and i1 %cmp, %cmp14
 223   br i1 %or.cond, label %for.body, label %if.end
 224
 225 for.body:                                         ; preds = %entry, %for.body
 226   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 227   tail call void (...) @foo() #2
 228   %inc = add nuw i32 %i.05, 1
 229   %exitcond.not = icmp eq i32 %inc, %num
 230   br i1 %exitcond.not, label %if.end, label %for.body
 231
 232 if.end:                                           ; preds = %for.body, %entry
 233   ret void
 234 }
 235 define void @trip_multiple_9(i32 noundef %num) {
 236 ; CHECK-LABEL: 'trip_multiple_9'
 237 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_9
 238 ; CHECK-NEXT:    %rem = urem i32 %num, 9
 239 ; CHECK-NEXT:    --> ((-9 * (%num /u 9)) + %num) U: full-set S: full-set
 240 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
 241 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
 242 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 243 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-4) S: [0,-4) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
 244 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 245 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 246 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_9
 247 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 248 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 249 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 250 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 251 ; CHECK-NEXT:   Predicates:
 252 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 9
 253 ;
 254 entry:
 255   %rem = urem i32 %num, 9
 256   %cmp = icmp eq i32 %rem, 0
 257   %cmp14 = icmp ne i32 %num, 0
 258   %or.cond = and i1 %cmp, %cmp14
 259   br i1 %or.cond, label %for.body, label %if.end
 260
 261 for.body:                                         ; preds = %entry, %for.body
 262   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 263   tail call void (...) @foo() #2
 264   %inc = add nuw i32 %i.05, 1
 265   %exitcond.not = icmp eq i32 %inc, %num
 266   br i1 %exitcond.not, label %if.end, label %for.body
 267
 268 if.end:                                           ; preds = %for.body, %entry
 269   ret void
 270 }
 271 define void @trip_multiple_10(i32 noundef %num) {
 272 ; CHECK-LABEL: 'trip_multiple_10'
 273 ; CHECK-NEXT:  Classifying expressions for: @trip_multiple_10
 274 ; CHECK-NEXT:    %rem = urem i32 %num, 10
 275 ; CHECK-NEXT:    --> ((-10 * (%num /u 10)) + %num) U: full-set S: full-set
 276 ; CHECK-NEXT:    %or.cond = and i1 %cmp, %cmp14
 277 ; CHECK-NEXT:    --> (%cmp14 umin %cmp) U: full-set S: full-set
 278 ; CHECK-NEXT:    %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 279 ; CHECK-NEXT:    --> {0,+,1}<nuw><%for.body> U: [0,-6) S: [0,-6) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
 280 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 281 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-5) S: [1,-5) Exits: %num LoopDispositions: { %for.body: Computable }
 282 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_10
 283 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 284 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -7
 285 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 286 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 287 ; CHECK-NEXT:   Predicates:
 288 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 10
 289 ;
 290 entry:
 291   %rem = urem i32 %num, 10
 292   %cmp = icmp eq i32 %rem, 0
 293   %cmp14 = icmp ne i32 %num, 0
 294   %or.cond = and i1 %cmp, %cmp14
 295   br i1 %or.cond, label %for.body, label %if.end
 296
 297 for.body:                                         ; preds = %entry, %for.body
 298   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 299   tail call void (...) @foo() #2
 300   %inc = add nuw i32 %i.05, 1
 301   %exitcond.not = icmp eq i32 %inc, %num
 302   br i1 %exitcond.not, label %if.end, label %for.body
 303
 304 if.end:                                           ; preds = %for.body, %entry
 305   ret void
 306 }