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 14define void @foo(i4 %n) { 15entry: 16 %s = icmp sgt i4 %n, 0 17 br i1 %s, label %loop, label %exit 18loop: 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 23exit: 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. 30define void @step2(i4 %n) { 31entry: 32 %s = icmp sgt i4 %n, 0 33 br i1 %s, label %loop, label %exit 34loop: 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 39exit: 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 46define void @start1(i4 %n) { 47entry: 48 %s = icmp sgt i4 %n, 0 49 br i1 %s, label %loop, label %exit 50loop: 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 55exit: 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. 62define void @start1_step2(i4 %n) { 63entry: 64 %s = icmp sgt i4 %n, 0 65 br i1 %s, label %loop, label %exit 66loop: 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 71exit: 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 78define void @startx(i4 %n, i4 %x) { 79entry: 80 %s = icmp sgt i4 %n, 0 81 br i1 %s, label %loop, label %exit 82loop: 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 87exit: 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. 94define void @startx_step2(i4 %n, i4 %x) { 95entry: 96 %s = icmp sgt i4 %n, 0 97 br i1 %s, label %loop, label %exit 98loop: 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 103exit: 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 110define void @nsw(i4 %n) { 111entry: 112 %s = icmp sgt i4 %n, 0 113 br i1 %s, label %loop, label %exit 114loop: 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 119exit: 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. 129define void @nsw_step2(i4 %n) { 130entry: 131 %s = icmp sgt i4 %n, 0 132 br i1 %s, label %loop, label %exit 133loop: 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 138exit: 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 145define void @nsw_start1(i4 %n) { 146entry: 147 %s = icmp sgt i4 %n, 0 148 br i1 %s, label %loop, label %exit 149loop: 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 154exit: 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. 161define void @nsw_start1_step2(i4 %n) { 162entry: 163 %s = icmp sgt i4 %n, 0 164 br i1 %s, label %loop, label %exit 165loop: 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 170exit: 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 177define void @nsw_startx(i4 %n, i4 %x) { 178entry: 179 %s = icmp sgt i4 %n, 0 180 br i1 %s, label %loop, label %exit 181loop: 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 186exit: 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. 193define void @nsw_startx_step2(i4 %n, i4 %x) { 194entry: 195 %s = icmp sgt i4 %n, 0 196 br i1 %s, label %loop, label %exit 197loop: 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 202exit: 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 209define void @even(i4 %n) { 210entry: 211 %m = shl i4 %n, 1 212 %s = icmp sgt i4 %m, 0 213 br i1 %s, label %loop, label %exit 214loop: 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 219exit: 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 226define void @even_step2(i4 %n) { 227entry: 228 %m = shl i4 %n, 1 229 %s = icmp sgt i4 %m, 0 230 br i1 %s, label %loop, label %exit 231loop: 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 236exit: 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 243define void @even_start1(i4 %n) { 244entry: 245 %m = shl i4 %n, 1 246 %s = icmp sgt i4 %m, 0 247 br i1 %s, label %loop, label %exit 248loop: 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 253exit: 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 260define void @even_start1_step2(i4 %n) { 261entry: 262 %m = shl i4 %n, 1 263 %s = icmp sgt i4 %m, 0 264 br i1 %s, label %loop, label %exit 265loop: 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 270exit: 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 277define void @even_startx(i4 %n, i4 %x) { 278entry: 279 %m = shl i4 %n, 1 280 %s = icmp sgt i4 %m, 0 281 br i1 %s, label %loop, label %exit 282loop: 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 287exit: 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 294define void @even_startx_step2(i4 %n, i4 %x) { 295entry: 296 %m = shl i4 %n, 1 297 %s = icmp sgt i4 %m, 0 298 br i1 %s, label %loop, label %exit 299loop: 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 304exit: 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 311define void @even_nsw(i4 %n) { 312entry: 313 %m = shl i4 %n, 1 314 %s = icmp sgt i4 %m, 0 315 br i1 %s, label %loop, label %exit 316loop: 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 321exit: 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 328define void @even_nsw_step2(i4 %n) { 329entry: 330 %m = shl i4 %n, 1 331 %s = icmp sgt i4 %m, 0 332 br i1 %s, label %loop, label %exit 333loop: 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 338exit: 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 345define void @even_nsw_start1(i4 %n) { 346entry: 347 %m = shl i4 %n, 1 348 %s = icmp sgt i4 %m, 0 349 br i1 %s, label %loop, label %exit 350loop: 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 355exit: 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 362define void @even_nsw_start1_step2(i4 %n) { 363entry: 364 %m = shl i4 %n, 1 365 %s = icmp sgt i4 %m, 0 366 br i1 %s, label %loop, label %exit 367loop: 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 372exit: 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 379define void @even_nsw_startx(i4 %n, i4 %x) { 380entry: 381 %m = shl i4 %n, 1 382 %s = icmp sgt i4 %m, 0 383 br i1 %s, label %loop, label %exit 384loop: 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 389exit: 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 396define void @even_nsw_startx_step2(i4 %n, i4 %x) { 397entry: 398 %m = shl i4 %n, 1 399 %s = icmp sgt i4 %m, 0 400 br i1 %s, label %loop, label %exit 401loop: 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 406exit: 407 ret void 408} 409