1 ; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s 2 3 ; Every combination of 4 ; - starting at 0, 1, or %x 5 ; - steping by 1 or 2 6 ; - stopping at %n or %n*2 7 ; - using nsw, or not 8 9 ; Some of these represent missed opportunities. 10 11 ; CHECK: Determining loop execution counts for: @foo 12 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n) 13 ; CHECK: Loop %loop: max backedge-taken count is 6 14 define void @foo(i4 %n) { 15 entry: 16 %s = icmp sgt i4 %n, 0 17 br i1 %s, label %loop, label %exit 18 loop: 19 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 20 %i.next = add i4 %i, 1 21 %t = icmp slt i4 %i.next, %n 22 br i1 %t, label %loop, label %exit 23 exit: 24 ret void 25 } 26 27 ; CHECK: Determining loop execution counts for: @step2 28 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 29 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 30 define void @step2(i4 %n) { 31 entry: 32 %s = icmp sgt i4 %n, 0 33 br i1 %s, label %loop, label %exit 34 loop: 35 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 36 %i.next = add i4 %i, 2 37 %t = icmp slt i4 %i.next, %n 38 br i1 %t, label %loop, label %exit 39 exit: 40 ret void 41 } 42 43 ; CHECK: Determining loop execution counts for: @start1 44 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) 45 ; CHECK: Loop %loop: max backedge-taken count is 5 46 define void @start1(i4 %n) { 47 entry: 48 %s = icmp sgt i4 %n, 0 49 br i1 %s, label %loop, label %exit 50 loop: 51 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 52 %i.next = add i4 %i, 1 53 %t = icmp slt i4 %i.next, %n 54 br i1 %t, label %loop, label %exit 55 exit: 56 ret void 57 } 58 59 ; CHECK: Determining loop execution counts for: @start1_step2 60 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 61 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 62 define void @start1_step2(i4 %n) { 63 entry: 64 %s = icmp sgt i4 %n, 0 65 br i1 %s, label %loop, label %exit 66 loop: 67 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 68 %i.next = add i4 %i, 2 69 %t = icmp slt i4 %i.next, %n 70 br i1 %t, label %loop, label %exit 71 exit: 72 ret void 73 } 74 75 ; CHECK: Determining loop execution counts for: @startx 76 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 77 ; CHECK: Loop %loop: max backedge-taken count is -1 78 define void @startx(i4 %n, i4 %x) { 79 entry: 80 %s = icmp sgt i4 %n, 0 81 br i1 %s, label %loop, label %exit 82 loop: 83 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 84 %i.next = add i4 %i, 1 85 %t = icmp slt i4 %i.next, %n 86 br i1 %t, label %loop, label %exit 87 exit: 88 ret void 89 } 90 91 ; CHECK: Determining loop execution counts for: @startx_step2 92 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 93 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 94 define void @startx_step2(i4 %n, i4 %x) { 95 entry: 96 %s = icmp sgt i4 %n, 0 97 br i1 %s, label %loop, label %exit 98 loop: 99 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 100 %i.next = add i4 %i, 2 101 %t = icmp slt i4 %i.next, %n 102 br i1 %t, label %loop, label %exit 103 exit: 104 ret void 105 } 106 107 ; CHECK: Determining loop execution counts for: @nsw 108 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n) 109 ; CHECK: Loop %loop: max backedge-taken count is 6 110 define void @nsw(i4 %n) { 111 entry: 112 %s = icmp sgt i4 %n, 0 113 br i1 %s, label %loop, label %exit 114 loop: 115 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 116 %i.next = add nsw i4 %i, 1 117 %t = icmp slt i4 %i.next, %n 118 br i1 %t, label %loop, label %exit 119 exit: 120 ret void 121 } 122 123 ; Be careful with this one. If %n is INT4_MAX, %i.next will wrap. The nsw bit 124 ; says that the result is undefined, but ScalarEvolution must respect that 125 ; subsequent passes may result the undefined behavior in predictable ways. 126 ; CHECK: Determining loop execution counts for: @nsw_step2 127 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 128 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 129 define void @nsw_step2(i4 %n) { 130 entry: 131 %s = icmp sgt i4 %n, 0 132 br i1 %s, label %loop, label %exit 133 loop: 134 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 135 %i.next = add nsw i4 %i, 2 136 %t = icmp slt i4 %i.next, %n 137 br i1 %t, label %loop, label %exit 138 exit: 139 ret void 140 } 141 142 ; CHECK: Determining loop execution counts for: @nsw_start1 143 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) 144 ; CHECK: Loop %loop: max backedge-taken count is 5 145 define void @nsw_start1(i4 %n) { 146 entry: 147 %s = icmp sgt i4 %n, 0 148 br i1 %s, label %loop, label %exit 149 loop: 150 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 151 %i.next = add nsw i4 %i, 1 152 %t = icmp slt i4 %i.next, %n 153 br i1 %t, label %loop, label %exit 154 exit: 155 ret void 156 } 157 158 ; CHECK: Determining loop execution counts for: @nsw_start1_step2 159 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 160 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 161 define void @nsw_start1_step2(i4 %n) { 162 entry: 163 %s = icmp sgt i4 %n, 0 164 br i1 %s, label %loop, label %exit 165 loop: 166 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 167 %i.next = add nsw i4 %i, 2 168 %t = icmp slt i4 %i.next, %n 169 br i1 %t, label %loop, label %exit 170 exit: 171 ret void 172 } 173 174 ; CHECK: Determining loop execution counts for: @nsw_startx 175 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 176 ; CHECK: Loop %loop: max backedge-taken count is -1 177 define void @nsw_startx(i4 %n, i4 %x) { 178 entry: 179 %s = icmp sgt i4 %n, 0 180 br i1 %s, label %loop, label %exit 181 loop: 182 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 183 %i.next = add nsw i4 %i, 1 184 %t = icmp slt i4 %i.next, %n 185 br i1 %t, label %loop, label %exit 186 exit: 187 ret void 188 } 189 190 ; CHECK: Determining loop execution counts for: @nsw_startx_step2 191 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 192 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 193 define void @nsw_startx_step2(i4 %n, i4 %x) { 194 entry: 195 %s = icmp sgt i4 %n, 0 196 br i1 %s, label %loop, label %exit 197 loop: 198 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 199 %i.next = add nsw i4 %i, 2 200 %t = icmp slt i4 %i.next, %n 201 br i1 %t, label %loop, label %exit 202 exit: 203 ret void 204 } 205 206 ; CHECK: Determining loop execution counts for: @even 207 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 208 ; CHECK: Loop %loop: max backedge-taken count is 5 209 define void @even(i4 %n) { 210 entry: 211 %m = shl i4 %n, 1 212 %s = icmp sgt i4 %m, 0 213 br i1 %s, label %loop, label %exit 214 loop: 215 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 216 %i.next = add i4 %i, 1 217 %t = icmp slt i4 %i.next, %m 218 br i1 %t, label %loop, label %exit 219 exit: 220 ret void 221 } 222 223 ; CHECK: Determining loop execution counts for: @even_step2 224 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 225 ; CHECK: Loop %loop: max backedge-taken count is 2 226 define void @even_step2(i4 %n) { 227 entry: 228 %m = shl i4 %n, 1 229 %s = icmp sgt i4 %m, 0 230 br i1 %s, label %loop, label %exit 231 loop: 232 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 233 %i.next = add i4 %i, 2 234 %t = icmp slt i4 %i.next, %m 235 br i1 %t, label %loop, label %exit 236 exit: 237 ret void 238 } 239 240 ; CHECK: Determining loop execution counts for: @even_start1 241 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) 242 ; CHECK: Loop %loop: max backedge-taken count is 4 243 define void @even_start1(i4 %n) { 244 entry: 245 %m = shl i4 %n, 1 246 %s = icmp sgt i4 %m, 0 247 br i1 %s, label %loop, label %exit 248 loop: 249 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 250 %i.next = add i4 %i, 1 251 %t = icmp slt i4 %i.next, %m 252 br i1 %t, label %loop, label %exit 253 exit: 254 ret void 255 } 256 257 ; CHECK: Determining loop execution counts for: @even_start1_step2 258 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 259 ; CHECK: Loop %loop: max backedge-taken count is 2 260 define void @even_start1_step2(i4 %n) { 261 entry: 262 %m = shl i4 %n, 1 263 %s = icmp sgt i4 %m, 0 264 br i1 %s, label %loop, label %exit 265 loop: 266 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 267 %i.next = add i4 %i, 2 268 %t = icmp slt i4 %i.next, %m 269 br i1 %t, label %loop, label %exit 270 exit: 271 ret void 272 } 273 274 ; CHECK: Determining loop execution counts for: @even_startx 275 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 276 ; CHECK: Loop %loop: max backedge-taken count is -1 277 define void @even_startx(i4 %n, i4 %x) { 278 entry: 279 %m = shl i4 %n, 1 280 %s = icmp sgt i4 %m, 0 281 br i1 %s, label %loop, label %exit 282 loop: 283 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 284 %i.next = add i4 %i, 1 285 %t = icmp slt i4 %i.next, %m 286 br i1 %t, label %loop, label %exit 287 exit: 288 ret void 289 } 290 291 ; CHECK: Determining loop execution counts for: @even_startx_step2 292 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 293 ; CHECK: Loop %loop: max backedge-taken count is 7 294 define void @even_startx_step2(i4 %n, i4 %x) { 295 entry: 296 %m = shl i4 %n, 1 297 %s = icmp sgt i4 %m, 0 298 br i1 %s, label %loop, label %exit 299 loop: 300 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 301 %i.next = add i4 %i, 2 302 %t = icmp slt i4 %i.next, %m 303 br i1 %t, label %loop, label %exit 304 exit: 305 ret void 306 } 307 308 ; CHECK: Determining loop execution counts for: @even_nsw 309 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 310 ; CHECK: Loop %loop: max backedge-taken count is 5 311 define void @even_nsw(i4 %n) { 312 entry: 313 %m = shl i4 %n, 1 314 %s = icmp sgt i4 %m, 0 315 br i1 %s, label %loop, label %exit 316 loop: 317 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 318 %i.next = add nsw i4 %i, 1 319 %t = icmp slt i4 %i.next, %m 320 br i1 %t, label %loop, label %exit 321 exit: 322 ret void 323 } 324 325 ; CHECK: Determining loop execution counts for: @even_nsw_step2 326 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) 327 ; CHECK: Loop %loop: max backedge-taken count is 2 328 define void @even_nsw_step2(i4 %n) { 329 entry: 330 %m = shl i4 %n, 1 331 %s = icmp sgt i4 %m, 0 332 br i1 %s, label %loop, label %exit 333 loop: 334 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 335 %i.next = add nsw i4 %i, 2 336 %t = icmp slt i4 %i.next, %m 337 br i1 %t, label %loop, label %exit 338 exit: 339 ret void 340 } 341 342 ; CHECK: Determining loop execution counts for: @even_nsw_start1 343 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) 344 ; CHECK: Loop %loop: max backedge-taken count is 4 345 define void @even_nsw_start1(i4 %n) { 346 entry: 347 %m = shl i4 %n, 1 348 %s = icmp sgt i4 %m, 0 349 br i1 %s, label %loop, label %exit 350 loop: 351 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 352 %i.next = add nsw i4 %i, 1 353 %t = icmp slt i4 %i.next, %m 354 br i1 %t, label %loop, label %exit 355 exit: 356 ret void 357 } 358 359 ; CHECK: Determining loop execution counts for: @even_nsw_start1_step2 360 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2) 361 ; CHECK: Loop %loop: max backedge-taken count is 2 362 define void @even_nsw_start1_step2(i4 %n) { 363 entry: 364 %m = shl i4 %n, 1 365 %s = icmp sgt i4 %m, 0 366 br i1 %s, label %loop, label %exit 367 loop: 368 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 369 %i.next = add nsw i4 %i, 2 370 %t = icmp slt i4 %i.next, %m 371 br i1 %t, label %loop, label %exit 372 exit: 373 ret void 374 } 375 376 ; CHECK: Determining loop execution counts for: @even_nsw_startx 377 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 378 ; CHECK: Loop %loop: max backedge-taken count is -1 379 define void @even_nsw_startx(i4 %n, i4 %x) { 380 entry: 381 %m = shl i4 %n, 1 382 %s = icmp sgt i4 %m, 0 383 br i1 %s, label %loop, label %exit 384 loop: 385 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 386 %i.next = add nsw i4 %i, 1 387 %t = icmp slt i4 %i.next, %m 388 br i1 %t, label %loop, label %exit 389 exit: 390 ret void 391 } 392 393 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2 394 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 395 ; CHECK: Loop %loop: max backedge-taken count is 7 396 define void @even_nsw_startx_step2(i4 %n, i4 %x) { 397 entry: 398 %m = shl i4 %n, 1 399 %s = icmp sgt i4 %m, 0 400 br i1 %s, label %loop, label %exit 401 loop: 402 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 403 %i.next = add nsw i4 %i, 2 404 %t = icmp slt i4 %i.next, %m 405 br i1 %t, label %loop, label %exit 406 exit: 407 ret void 408 } 409
