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