test/Transforms/LoopIdiom/basic.ll

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