1 ; RUN: opt -basicaa -loop-idiom < %s -S | FileCheck %s 2 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" 3 target triple = "x86_64-apple-darwin10.0.0" 4 5 define void @test1(i8* %Base, i64 %Size) nounwind ssp { 6 bb.nph: ; preds = %entry 7 br label %for.body 8 9 for.body: ; preds = %bb.nph, %for.body 10 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 11 %I.0.014 = getelementptr i8* %Base, i64 %indvar 12 store i8 0, i8* %I.0.014, align 1 13 %indvar.next = add i64 %indvar, 1 14 %exitcond = icmp eq i64 %indvar.next, %Size 15 br i1 %exitcond, label %for.end, label %for.body 16 17 for.end: ; preds = %for.body, %entry 18 ret void 19 ; CHECK-LABEL: @test1( 20 ; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 %Size, i32 1, i1 false) 21 ; CHECK-NOT: store 22 } 23 24 ; This is a loop that was rotated but where the blocks weren't merged. This 25 ; shouldn't perturb us. 26 define void @test1a(i8* %Base, i64 %Size) nounwind ssp { 27 bb.nph: ; preds = %entry 28 br label %for.body 29 30 for.body: ; preds = %bb.nph, %for.body 31 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body.cont ] 32 %I.0.014 = getelementptr i8* %Base, i64 %indvar 33 store i8 0, i8* %I.0.014, align 1 34 %indvar.next = add i64 %indvar, 1 35 br label %for.body.cont 36 for.body.cont: 37 %exitcond = icmp eq i64 %indvar.next, %Size 38 br i1 %exitcond, label %for.end, label %for.body 39 40 for.end: ; preds = %for.body, %entry 41 ret void 42 ; CHECK-LABEL: @test1a( 43 ; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 %Size, i32 1, i1 false) 44 ; CHECK-NOT: store 45 } 46 47 48 define void @test2(i32* %Base, i64 %Size) nounwind ssp { 49 entry: 50 %cmp10 = icmp eq i64 %Size, 0 51 br i1 %cmp10, label %for.end, label %for.body 52 53 for.body: ; preds = %entry, %for.body 54 %i.011 = phi i64 [ %inc, %for.body ], [ 0, %entry ] 55 %add.ptr.i = getelementptr i32* %Base, i64 %i.011 56 store i32 16843009, i32* %add.ptr.i, align 4 57 %inc = add nsw i64 %i.011, 1 58 %exitcond = icmp eq i64 %inc, %Size 59 br i1 %exitcond, label %for.end, label %for.body 60 61 for.end: ; preds = %for.body, %entry 62 ret void 63 ; CHECK-LABEL: @test2( 64 ; CHECK: br i1 %cmp10, 65 ; CHECK: %0 = mul i64 %Size, 4 66 ; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base1, i8 1, i64 %0, i32 4, i1 false) 67 ; CHECK-NOT: store 68 } 69 70 ; This is a case where there is an extra may-aliased store in the loop, we can't 71 ; promote the memset. 72 define void @test3(i32* %Base, i64 %Size, i8 *%MayAlias) nounwind ssp { 73 entry: 74 br label %for.body 75 76 for.body: ; preds = %entry, %for.body 77 %i.011 = phi i64 [ %inc, %for.body ], [ 0, %entry ] 78 %add.ptr.i = getelementptr i32* %Base, i64 %i.011 79 store i32 16843009, i32* %add.ptr.i, align 4 80 81 store i8 42, i8* %MayAlias 82 %inc = add nsw i64 %i.011, 1 83 %exitcond = icmp eq i64 %inc, %Size 84 br i1 %exitcond, label %for.end, label %for.body 85 86 for.end: ; preds = %entry 87 ret void 88 ; CHECK-LABEL: @test3( 89 ; CHECK-NOT: memset 90 ; CHECK: ret void 91 } 92 93 94 ;; TODO: We should be able to promote this memset. Not yet though. 95 define void @test4(i8* %Base) nounwind ssp { 96 bb.nph: ; preds = %entry 97 %Base100 = getelementptr i8* %Base, i64 1000 98 br label %for.body 99 100 for.body: ; preds = %bb.nph, %for.body 101 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 102 %I.0.014 = getelementptr i8* %Base, i64 %indvar 103 store i8 0, i8* %I.0.014, align 1 104 105 ;; Store beyond the range memset, should be safe to promote. 106 store i8 42, i8* %Base100 107 108 %indvar.next = add i64 %indvar, 1 109 %exitcond = icmp eq i64 %indvar.next, 100 110 br i1 %exitcond, label %for.end, label %for.body 111 112 for.end: ; preds = %for.body, %entry 113 ret void 114 ; CHECK-TODO-LABEL: @test4( 115 ; CHECK-TODO: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 100, i32 1, i1 false) 116 ; CHECK-TODO-NOT: store 117 } 118 119 ; This can't be promoted: the memset is a store of a loop variant value. 120 define void @test5(i8* %Base, i64 %Size) nounwind ssp { 121 bb.nph: ; preds = %entry 122 br label %for.body 123 124 for.body: ; preds = %bb.nph, %for.body 125 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 126 %I.0.014 = getelementptr i8* %Base, i64 %indvar 127 128 %V = trunc i64 %indvar to i8 129 store i8 %V, i8* %I.0.014, align 1 130 %indvar.next = add i64 %indvar, 1 131 %exitcond = icmp eq i64 %indvar.next, %Size 132 br i1 %exitcond, label %for.end, label %for.body 133 134 for.end: ; preds = %for.body, %entry 135 ret void 136 ; CHECK-LABEL: @test5( 137 ; CHECK-NOT: memset 138 ; CHECK: ret void 139 } 140 141 142 ;; memcpy formation 143 define void @test6(i64 %Size) nounwind ssp { 144 bb.nph: 145 %Base = alloca i8, i32 10000 146 %Dest = alloca i8, i32 10000 147 br label %for.body 148 149 for.body: ; preds = %bb.nph, %for.body 150 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 151 %I.0.014 = getelementptr i8* %Base, i64 %indvar 152 %DestI = getelementptr i8* %Dest, i64 %indvar 153 %V = load i8* %I.0.014, align 1 154 store i8 %V, i8* %DestI, align 1 155 %indvar.next = add i64 %indvar, 1 156 %exitcond = icmp eq i64 %indvar.next, %Size 157 br i1 %exitcond, label %for.end, label %for.body 158 159 for.end: ; preds = %for.body, %entry 160 ret void 161 ; CHECK-LABEL: @test6( 162 ; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %Dest, i8* %Base, i64 %Size, i32 1, i1 false) 163 ; CHECK-NOT: store 164 ; CHECK: ret void 165 } 166 167 168 ; This is a loop that was rotated but where the blocks weren't merged. This 169 ; shouldn't perturb us. 170 define void @test7(i8* %Base, i64 %Size) nounwind ssp { 171 bb.nph: ; preds = %entry 172 br label %for.body 173 174 for.body: ; preds = %bb.nph, %for.body 175 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body.cont ] 176 br label %for.body.cont 177 for.body.cont: 178 %I.0.014 = getelementptr i8* %Base, i64 %indvar 179 store i8 0, i8* %I.0.014, align 1 180 %indvar.next = add i64 %indvar, 1 181 %exitcond = icmp eq i64 %indvar.next, %Size 182 br i1 %exitcond, label %for.end, label %for.body 183 184 for.end: ; preds = %for.body, %entry 185 ret void 186 ; CHECK-LABEL: @test7( 187 ; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 %Size, i32 1, i1 false) 188 ; CHECK-NOT: store 189 } 190 191 ; This is a loop should not be transformed, it only executes one iteration. 192 define void @test8(i64* %Ptr, i64 %Size) nounwind ssp { 193 bb.nph: ; preds = %entry 194 br label %for.body 195 196 for.body: ; preds = %bb.nph, %for.body 197 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 198 %PI = getelementptr i64* %Ptr, i64 %indvar 199 store i64 0, i64 *%PI 200 %indvar.next = add i64 %indvar, 1 201 %exitcond = icmp eq i64 %indvar.next, 1 202 br i1 %exitcond, label %for.end, label %for.body 203 204 for.end: ; preds = %for.body, %entry 205 ret void 206 ; CHECK-LABEL: @test8( 207 ; CHECK: store i64 0, i64* %PI 208 } 209 210 declare i8* @external(i8*) 211 212 ;; This cannot be transformed into a memcpy, because the read-from location is 213 ;; mutated by the loop. 214 define void @test9(i64 %Size) nounwind ssp { 215 bb.nph: 216 %Base = alloca i8, i32 10000 217 %Dest = alloca i8, i32 10000 218 219 %BaseAlias = call i8* @external(i8* %Base) 220 br label %for.body 221 222 for.body: ; preds = %bb.nph, %for.body 223 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ] 224 %I.0.014 = getelementptr i8* %Base, i64 %indvar 225 %DestI = getelementptr i8* %Dest, i64 %indvar 226 %V = load i8* %I.0.014, align 1 227 store i8 %V, i8* %DestI, align 1 228 229 ;; This store can clobber the input. 230 store i8 4, i8* %BaseAlias 231 232 %indvar.next = add i64 %indvar, 1 233 %exitcond = icmp eq i64 %indvar.next, %Size 234 br i1 %exitcond, label %for.end, label %for.body 235 236 for.end: ; preds = %for.body, %entry 237 ret void 238 ; CHECK-LABEL: @test9( 239 ; CHECK-NOT: llvm.memcpy 240 ; CHECK: ret void 241 } 242 243 ; Two dimensional nested loop should be promoted to one big memset. 244 define void @test10(i8* %X) nounwind ssp { 245 entry: 246 br label %bb.nph 247 248 bb.nph: ; preds = %entry, %for.inc10 249 %i.04 = phi i32 [ 0, %entry ], [ %inc12, %for.inc10 ] 250 br label %for.body5 251 252 for.body5: ; preds = %for.body5, %bb.nph 253 %j.02 = phi i32 [ 0, %bb.nph ], [ %inc, %for.body5 ] 254 %mul = mul nsw i32 %i.04, 100 255 %add = add nsw i32 %j.02, %mul 256 %idxprom = sext i32 %add to i64 257 %arrayidx = getelementptr inbounds i8* %X, i64 %idxprom 258 store i8 0, i8* %arrayidx, align 1 259 %inc = add nsw i32 %j.02, 1 260 %cmp4 = icmp eq i32 %inc, 100 261 br i1 %cmp4, label %for.inc10, label %for.body5 262 263 for.inc10: ; preds = %for.body5 264 %inc12 = add nsw i32 %i.04, 1 265 %cmp = icmp eq i32 %inc12, 100 266 br i1 %cmp, label %for.end13, label %bb.nph 267 268 for.end13: ; preds = %for.inc10 269 ret void 270 ; CHECK-LABEL: @test10( 271 ; CHECK: entry: 272 ; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* %X, i8 0, i64 10000, i32 1, i1 false) 273 ; CHECK-NOT: store 274 ; CHECK: ret void 275 } 276 277 ; On darwin10 (which is the triple in this .ll file) this loop can be turned 278 ; into a memset_pattern call. 279 ; rdar://9009151 280 define void @test11_pattern(i32* nocapture %P) nounwind ssp { 281 entry: 282 br label %for.body 283 284 for.body: ; preds = %entry, %for.body 285 %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ] 286 %arrayidx = getelementptr i32* %P, i64 %indvar 287 store i32 1, i32* %arrayidx, align 4 288 %indvar.next = add i64 %indvar, 1 289 %exitcond = icmp eq i64 %indvar.next, 10000 290 br i1 %exitcond, label %for.end, label %for.body 291 292 for.end: ; preds = %for.body 293 ret void 294 ; CHECK-LABEL: @test11_pattern( 295 ; CHECK-NEXT: entry: 296 ; CHECK-NEXT: bitcast 297 ; CHECK-NEXT: memset_pattern 298 ; CHECK-NOT: store 299 ; CHECK: ret void 300 } 301 302 ; Store of null should turn into memset of zero. 303 define void @test12(i32** nocapture %P) nounwind ssp { 304 entry: 305 br label %for.body 306 307 for.body: ; preds = %entry, %for.body 308 %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ] 309 %arrayidx = getelementptr i32** %P, i64 %indvar 310 store i32* null, i32** %arrayidx, align 4 311 %indvar.next = add i64 %indvar, 1 312 %exitcond = icmp eq i64 %indvar.next, 10000 313 br i1 %exitcond, label %for.end, label %for.body 314 315 for.end: ; preds = %for.body 316 ret void 317 ; CHECK-LABEL: @test12( 318 ; CHECK-NEXT: entry: 319 ; CHECK-NEXT: bitcast 320 ; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* %P1, i8 0, i64 80000, i32 4, i1 false) 321 ; CHECK-NOT: store 322 ; CHECK: ret void 323 } 324 325 @G = global i32 5 326 327 ; This store-of-address loop can be turned into a memset_pattern call. 328 ; rdar://9009151 329 define void @test13_pattern(i32** nocapture %P) nounwind ssp { 330 entry: 331 br label %for.body 332 333 for.body: ; preds = %entry, %for.body 334 %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ] 335 %arrayidx = getelementptr i32** %P, i64 %indvar 336 store i32* @G, i32** %arrayidx, align 4 337 %indvar.next = add i64 %indvar, 1 338 %exitcond = icmp eq i64 %indvar.next, 10000 339 br i1 %exitcond, label %for.end, label %for.body 340 341 for.end: ; preds = %for.body 342 ret void 343 ; CHECK-LABEL: @test13_pattern( 344 ; CHECK-NEXT: entry: 345 ; CHECK-NEXT: bitcast 346 ; CHECK-NEXT: memset_pattern 347 ; CHECK-NOT: store 348 ; CHECK: ret void 349 } 350 351 352 353 ; PR9815 - This is a partial overlap case that cannot be safely transformed 354 ; into a memcpy. 355 @g_50 = global [7 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0], align 16 356 357 define i32 @test14() nounwind { 358 entry: 359 br label %for.body 360 361 for.body: ; preds = %for.inc, %for.body.lr.ph 362 %tmp5 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 363 %add = add nsw i32 %tmp5, 4 364 %idxprom = sext i32 %add to i64 365 %arrayidx = getelementptr inbounds [7 x i32]* @g_50, i32 0, i64 %idxprom 366 %tmp2 = load i32* %arrayidx, align 4 367 %add4 = add nsw i32 %tmp5, 5 368 %idxprom5 = sext i32 %add4 to i64 369 %arrayidx6 = getelementptr inbounds [7 x i32]* @g_50, i32 0, i64 %idxprom5 370 store i32 %tmp2, i32* %arrayidx6, align 4 371 %inc = add nsw i32 %tmp5, 1 372 %cmp = icmp slt i32 %inc, 2 373 br i1 %cmp, label %for.body, label %for.end 374 375 for.end: ; preds = %for.inc 376 %tmp8 = load i32* getelementptr inbounds ([7 x i32]* @g_50, i32 0, i64 6), align 4 377 ret i32 %tmp8 378 ; CHECK-LABEL: @test14( 379 ; CHECK: for.body: 380 ; CHECK: load i32 381 ; CHECK: store i32 382 ; CHECK: br i1 %cmp 383 384 } 385 386 define void @PR14241(i32* %s, i64 %size) { 387 ; Ensure that we don't form a memcpy for strided loops. Briefly, when we taught 388 ; LoopIdiom about memmove and strided loops, this got miscompiled into a memcpy 389 ; instead of a memmove. If we get the memmove transform back, this will catch 390 ; regressions. 391 ; 392 ; CHECK-LABEL: @PR14241( 393 394 entry: 395 %end.idx = add i64 %size, -1 396 %end.ptr = getelementptr inbounds i32* %s, i64 %end.idx 397 br label %while.body 398 ; CHECK-NOT: memcpy 399 ; 400 ; FIXME: When we regain the ability to form a memmove here, this test should be 401 ; reversed and turned into a positive assertion. 402 ; CHECK-NOT: memmove 403 404 while.body: 405 %phi.ptr = phi i32* [ %s, %entry ], [ %next.ptr, %while.body ] 406 %src.ptr = getelementptr inbounds i32* %phi.ptr, i64 1 407 %val = load i32* %src.ptr, align 4 408 ; CHECK: load 409 %dst.ptr = getelementptr inbounds i32* %phi.ptr, i64 0 410 store i32 %val, i32* %dst.ptr, align 4 411 ; CHECK: store 412 %next.ptr = getelementptr inbounds i32* %phi.ptr, i64 1 413 %cmp = icmp eq i32* %next.ptr, %end.ptr 414 br i1 %cmp, label %exit, label %while.body 415 416 exit: 417 ret void 418 ; CHECK: ret void 419 } 420
