llvm/test/Transforms/LoopIdiom/basic.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes=loop-idiom < %s -S | FileCheck %s
   3 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"
   4
   5 ; For @test11_pattern
   6 ; CHECK: @.memset_pattern = private unnamed_addr constant [4 x i32] [i32 1, i32 1, i32 1, i32 1]
   7
   8 ; For @test13_pattern
   9 ; CHECK: @.memset_pattern.1 = private unnamed_addr constant [2 x ptr] [ptr @G, ptr @G]
  10
  11 target triple = "x86_64-apple-darwin10.0.0"
  12
  13 define void @test1(ptr %Base, i64 %Size) nounwind ssp {
  14 ; CHECK-LABEL: @test1(
  15 ; CHECK-NEXT:  bb.nph:
  16 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[BASE:%.*]], i8 0, i64 [[SIZE:%.*]], i1 false)
  17 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
  18 ; CHECK:       for.body:
  19 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
  20 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
  21 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
  22 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
  23 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
  24 ; CHECK:       for.end:
  25 ; CHECK-NEXT:    ret void
  26 ;
  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 ]
  32   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
  33   store i8 0, ptr %I.0.014, align 1
  34   %indvar.next = add i64 %indvar, 1
  35   %exitcond = icmp eq i64 %indvar.next, %Size
  36   br i1 %exitcond, label %for.end, label %for.body
  37
  38 for.end:                                          ; preds = %for.body, %entry
  39   ret void
  40 }
  41
  42 ; Make sure memset is formed for larger than 1 byte stores, and that the
  43 ; alignment of the store is preserved
  44 define void @test1_i16(ptr align 2 %Base, i64 %Size) nounwind ssp {
  45 ; CHECK-LABEL: @test1_i16(
  46 ; CHECK-NEXT:  bb.nph:
  47 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[SIZE:%.*]], 1
  48 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 2 [[BASE:%.*]], i8 0, i64 [[TMP0]], i1 false)
  49 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
  50 ; CHECK:       for.body:
  51 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
  52 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i16, ptr [[BASE]], i64 [[INDVAR]]
  53 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
  54 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
  55 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
  56 ; CHECK:       for.end:
  57 ; CHECK-NEXT:    ret void
  58 ;
  59 bb.nph:                                           ; preds = %entry
  60   br label %for.body
  61
  62 for.body:                                         ; preds = %bb.nph, %for.body
  63   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
  64   %I.0.014 = getelementptr i16, ptr %Base, i64 %indvar
  65   store i16 0, ptr %I.0.014, align 2
  66   %indvar.next = add i64 %indvar, 1
  67   %exitcond = icmp eq i64 %indvar.next, %Size
  68   br i1 %exitcond, label %for.end, label %for.body
  69
  70 for.end:                                          ; preds = %for.body, %entry
  71   ret void
  72 }
  73
  74 ; This is a loop that was rotated but where the blocks weren't merged.  This
  75 ; shouldn't perturb us.
  76 define void @test1a(ptr %Base, i64 %Size) nounwind ssp {
  77 ; CHECK-LABEL: @test1a(
  78 ; CHECK-NEXT:  bb.nph:
  79 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[BASE:%.*]], i8 0, i64 [[SIZE:%.*]], i1 false)
  80 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
  81 ; CHECK:       for.body:
  82 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY_CONT:%.*]] ]
  83 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
  84 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
  85 ; CHECK-NEXT:    br label [[FOR_BODY_CONT]]
  86 ; CHECK:       for.body.cont:
  87 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
  88 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
  89 ; CHECK:       for.end:
  90 ; CHECK-NEXT:    ret void
  91 ;
  92 bb.nph:                                           ; preds = %entry
  93   br label %for.body
  94
  95 for.body:                                         ; preds = %bb.nph, %for.body
  96   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body.cont ]
  97   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
  98   store i8 0, ptr %I.0.014, align 1
  99   %indvar.next = add i64 %indvar, 1
 100   br label %for.body.cont
 101 for.body.cont:
 102   %exitcond = icmp eq i64 %indvar.next, %Size
 103   br i1 %exitcond, label %for.end, label %for.body
 104
 105 for.end:                                          ; preds = %for.body, %entry
 106   ret void
 107 }
 108
 109
 110 define void @test2(ptr %Base, i64 %Size) nounwind ssp {
 111 ; CHECK-LABEL: @test2(
 112 ; CHECK-NEXT:  entry:
 113 ; CHECK-NEXT:    [[CMP10:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
 114 ; CHECK-NEXT:    br i1 [[CMP10]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
 115 ; CHECK:       for.body.preheader:
 116 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[SIZE]], 2
 117 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 4 [[BASE:%.*]], i8 1, i64 [[TMP0]], i1 false)
 118 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 119 ; CHECK:       for.body:
 120 ; CHECK-NEXT:    [[I_011:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 121 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr i32, ptr [[BASE]], i64 [[I_011]]
 122 ; CHECK-NEXT:    [[INC]] = add nsw i64 [[I_011]], 1
 123 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[SIZE]]
 124 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
 125 ; CHECK:       for.end.loopexit:
 126 ; CHECK-NEXT:    br label [[FOR_END]]
 127 ; CHECK:       for.end:
 128 ; CHECK-NEXT:    ret void
 129 ;
 130 entry:
 131   %cmp10 = icmp eq i64 %Size, 0
 132   br i1 %cmp10, label %for.end, label %for.body
 133
 134 for.body:                                         ; preds = %entry, %for.body
 135   %i.011 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
 136   %add.ptr.i = getelementptr i32, ptr %Base, i64 %i.011
 137   store i32 16843009, ptr %add.ptr.i, align 4
 138   %inc = add nsw i64 %i.011, 1
 139   %exitcond = icmp eq i64 %inc, %Size
 140   br i1 %exitcond, label %for.end, label %for.body
 141
 142 for.end:                                          ; preds = %for.body, %entry
 143   ret void
 144 }
 145
 146 ; This is a case where there is an extra may-aliased store in the loop, we can't
 147 ; promote the memset.
 148 define void @test3(ptr %Base, i64 %Size, ptr %MayAlias) nounwind ssp {
 149 ; CHECK-LABEL: @test3(
 150 ; CHECK-NEXT:  entry:
 151 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 152 ; CHECK:       for.body:
 153 ; CHECK-NEXT:    [[I_011:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
 154 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr i32, ptr [[BASE:%.*]], i64 [[I_011]]
 155 ; CHECK-NEXT:    store i32 16843009, ptr [[ADD_PTR_I]], align 4
 156 ; CHECK-NEXT:    store i8 42, ptr [[MAYALIAS:%.*]], align 1
 157 ; CHECK-NEXT:    [[INC]] = add nsw i64 [[I_011]], 1
 158 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[SIZE:%.*]]
 159 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 160 ; CHECK:       for.end:
 161 ; CHECK-NEXT:    ret void
 162 ;
 163 entry:
 164   br label %for.body
 165
 166 for.body:                                         ; preds = %entry, %for.body
 167   %i.011 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
 168   %add.ptr.i = getelementptr i32, ptr %Base, i64 %i.011
 169   store i32 16843009, ptr %add.ptr.i, align 4
 170
 171   store i8 42, ptr %MayAlias
 172   %inc = add nsw i64 %i.011, 1
 173   %exitcond = icmp eq i64 %inc, %Size
 174   br i1 %exitcond, label %for.end, label %for.body
 175
 176 for.end:                                          ; preds = %entry
 177   ret void
 178 }
 179
 180 ; Make sure the first store in the loop is turned into a memset.
 181 define void @test4(ptr %Base) nounwind ssp {
 182 ; CHECK-LABEL: @test4(
 183 ; CHECK-NEXT:  bb.nph:
 184 ; CHECK-NEXT:    [[BASE100:%.*]] = getelementptr i8, ptr [[BASE:%.*]], i64 1000
 185 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[BASE]], i8 0, i64 100, i1 false)
 186 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 187 ; CHECK:       for.body:
 188 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 189 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
 190 ; CHECK-NEXT:    store i8 42, ptr [[BASE100]], align 1
 191 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 192 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 100
 193 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 194 ; CHECK:       for.end:
 195 ; CHECK-NEXT:    ret void
 196 ;
 197 bb.nph:                                           ; preds = %entry
 198   %Base100 = getelementptr i8, ptr %Base, i64 1000
 199   br label %for.body
 200
 201 for.body:                                         ; preds = %bb.nph, %for.body
 202   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 203   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
 204   store i8 0, ptr %I.0.014, align 1
 205
 206   ;; Store beyond the range memset, should be safe to promote.
 207   store i8 42, ptr %Base100
 208
 209   %indvar.next = add i64 %indvar, 1
 210   %exitcond = icmp eq i64 %indvar.next, 100
 211   br i1 %exitcond, label %for.end, label %for.body
 212
 213 for.end:                                          ; preds = %for.body, %entry
 214   ret void
 215 }
 216
 217 ; This can't be promoted: the memset is a store of a loop variant value.
 218 define void @test5(ptr %Base, i64 %Size) nounwind ssp {
 219 ; CHECK-LABEL: @test5(
 220 ; CHECK-NEXT:  bb.nph:
 221 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 222 ; CHECK:       for.body:
 223 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 224 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE:%.*]], i64 [[INDVAR]]
 225 ; CHECK-NEXT:    [[V:%.*]] = trunc i64 [[INDVAR]] to i8
 226 ; CHECK-NEXT:    store i8 [[V]], ptr [[I_0_014]], align 1
 227 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 228 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
 229 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 230 ; CHECK:       for.end:
 231 ; CHECK-NEXT:    ret void
 232 ;
 233 bb.nph:                                           ; preds = %entry
 234   br label %for.body
 235
 236 for.body:                                         ; preds = %bb.nph, %for.body
 237   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 238   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
 239
 240   %V = trunc i64 %indvar to i8
 241   store i8 %V, ptr %I.0.014, align 1
 242   %indvar.next = add i64 %indvar, 1
 243   %exitcond = icmp eq i64 %indvar.next, %Size
 244   br i1 %exitcond, label %for.end, label %for.body
 245
 246 for.end:                                          ; preds = %for.body, %entry
 247   ret void
 248 }
 249
 250
 251 ;; memcpy formation
 252 define void @test6(i64 %Size) nounwind ssp {
 253 ; CHECK-LABEL: @test6(
 254 ; CHECK-NEXT:  bb.nph:
 255 ; CHECK-NEXT:    [[BASE:%.*]] = alloca i8, i32 10000, align 1
 256 ; CHECK-NEXT:    [[DEST:%.*]] = alloca i8, i32 10000, align 1
 257 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DEST]], ptr align 1 [[BASE]], i64 [[SIZE:%.*]], i1 false)
 258 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 259 ; CHECK:       for.body:
 260 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 261 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
 262 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[DEST]], i64 [[INDVAR]]
 263 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[I_0_014]], align 1
 264 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 265 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
 266 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 267 ; CHECK:       for.end:
 268 ; CHECK-NEXT:    ret void
 269 ;
 270 bb.nph:
 271   %Base = alloca i8, i32 10000
 272   %Dest = alloca i8, i32 10000
 273   br label %for.body
 274
 275 for.body:                                         ; preds = %bb.nph, %for.body
 276   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 277   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
 278   %DestI = getelementptr i8, ptr %Dest, i64 %indvar
 279   %V = load i8, ptr %I.0.014, align 1
 280   store i8 %V, ptr %DestI, align 1
 281   %indvar.next = add i64 %indvar, 1
 282   %exitcond = icmp eq i64 %indvar.next, %Size
 283   br i1 %exitcond, label %for.end, label %for.body
 284
 285 for.end:                                          ; preds = %for.body, %entry
 286   ret void
 287 }
 288
 289 ;; memcpy formation, check alignment
 290 define void @test6_dest_align(ptr noalias align 1 %Base, ptr noalias align 4 %Dest, i64 %Size) nounwind ssp {
 291 ; CHECK-LABEL: @test6_dest_align(
 292 ; CHECK-NEXT:  bb.nph:
 293 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[SIZE:%.*]], 2
 294 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST:%.*]], ptr align 1 [[BASE:%.*]], i64 [[TMP0]], i1 false)
 295 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 296 ; CHECK:       for.body:
 297 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 298 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i32, ptr [[BASE]], i64 [[INDVAR]]
 299 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i32, ptr [[DEST]], i64 [[INDVAR]]
 300 ; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[I_0_014]], align 1
 301 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 302 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
 303 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 304 ; CHECK:       for.end:
 305 ; CHECK-NEXT:    ret void
 306 ;
 307 bb.nph:
 308   br label %for.body
 309
 310 for.body:                                         ; preds = %bb.nph, %for.body
 311   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 312   %I.0.014 = getelementptr i32, ptr %Base, i64 %indvar
 313   %DestI = getelementptr i32, ptr %Dest, i64 %indvar
 314   %V = load i32, ptr %I.0.014, align 1
 315   store i32 %V, ptr %DestI, align 4
 316   %indvar.next = add i64 %indvar, 1
 317   %exitcond = icmp eq i64 %indvar.next, %Size
 318   br i1 %exitcond, label %for.end, label %for.body
 319
 320 for.end:                                          ; preds = %for.body, %entry
 321   ret void
 322 }
 323
 324 ;; memcpy formation, check alignment
 325 define void @test6_src_align(ptr noalias align 4 %Base, ptr noalias align 1 %Dest, i64 %Size) nounwind ssp {
 326 ; CHECK-LABEL: @test6_src_align(
 327 ; CHECK-NEXT:  bb.nph:
 328 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[SIZE:%.*]], 2
 329 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DEST:%.*]], ptr align 4 [[BASE:%.*]], i64 [[TMP0]], i1 false)
 330 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 331 ; CHECK:       for.body:
 332 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 333 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i32, ptr [[BASE]], i64 [[INDVAR]]
 334 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i32, ptr [[DEST]], i64 [[INDVAR]]
 335 ; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[I_0_014]], align 4
 336 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 337 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
 338 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 339 ; CHECK:       for.end:
 340 ; CHECK-NEXT:    ret void
 341 ;
 342 bb.nph:
 343   br label %for.body
 344
 345 for.body:                                         ; preds = %bb.nph, %for.body
 346   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 347   %I.0.014 = getelementptr i32, ptr %Base, i64 %indvar
 348   %DestI = getelementptr i32, ptr %Dest, i64 %indvar
 349   %V = load i32, ptr %I.0.014, align 4
 350   store i32 %V, ptr %DestI, align 1
 351   %indvar.next = add i64 %indvar, 1
 352   %exitcond = icmp eq i64 %indvar.next, %Size
 353   br i1 %exitcond, label %for.end, label %for.body
 354
 355 for.end:                                          ; preds = %for.body, %entry
 356   ret void
 357 }
 358
 359
 360 ; This is a loop that was rotated but where the blocks weren't merged.  This
 361 ; shouldn't perturb us.
 362 define void @test7(ptr %Base, i64 %Size) nounwind ssp {
 363 ; CHECK-LABEL: @test7(
 364 ; CHECK-NEXT:  bb.nph:
 365 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[BASE:%.*]], i8 0, i64 [[SIZE:%.*]], i1 false)
 366 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 367 ; CHECK:       for.body:
 368 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY_CONT:%.*]] ]
 369 ; CHECK-NEXT:    br label [[FOR_BODY_CONT]]
 370 ; CHECK:       for.body.cont:
 371 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
 372 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 373 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
 374 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 375 ; CHECK:       for.end:
 376 ; CHECK-NEXT:    ret void
 377 ;
 378 bb.nph:                                           ; preds = %entry
 379   br label %for.body
 380
 381 for.body:                                         ; preds = %bb.nph, %for.body
 382   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body.cont ]
 383   br label %for.body.cont
 384 for.body.cont:
 385   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
 386   store i8 0, ptr %I.0.014, align 1
 387   %indvar.next = add i64 %indvar, 1
 388   %exitcond = icmp eq i64 %indvar.next, %Size
 389   br i1 %exitcond, label %for.end, label %for.body
 390
 391 for.end:                                          ; preds = %for.body, %entry
 392   ret void
 393 }
 394
 395 ; This is a loop should not be transformed, it only executes one iteration.
 396 define void @test8(ptr %Ptr, i64 %Size) nounwind ssp {
 397 ; CHECK-LABEL: @test8(
 398 ; CHECK-NEXT:  bb.nph:
 399 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 400 ; CHECK:       for.body:
 401 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 402 ; CHECK-NEXT:    [[PI:%.*]] = getelementptr i64, ptr [[PTR:%.*]], i64 [[INDVAR]]
 403 ; CHECK-NEXT:    store i64 0, ptr [[PI]], align 8
 404 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 405 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 1
 406 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 407 ; CHECK:       for.end:
 408 ; CHECK-NEXT:    ret void
 409 ;
 410 bb.nph:                                           ; preds = %entry
 411   br label %for.body
 412
 413 for.body:                                         ; preds = %bb.nph, %for.body
 414   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 415   %PI = getelementptr i64, ptr %Ptr, i64 %indvar
 416   store i64 0, ptr %PI
 417   %indvar.next = add i64 %indvar, 1
 418   %exitcond = icmp eq i64 %indvar.next, 1
 419   br i1 %exitcond, label %for.end, label %for.body
 420
 421 for.end:                                          ; preds = %for.body, %entry
 422   ret void
 423 }
 424
 425 declare ptr @external(ptr)
 426
 427 ;; This cannot be transformed into a memcpy, because the read-from location is
 428 ;; mutated by the loop.
 429 define void @test9(i64 %Size) nounwind ssp {
 430 ; CHECK-LABEL: @test9(
 431 ; CHECK-NEXT:  bb.nph:
 432 ; CHECK-NEXT:    [[BASE:%.*]] = alloca i8, i32 10000, align 1
 433 ; CHECK-NEXT:    [[DEST:%.*]] = alloca i8, i32 10000, align 1
 434 ; CHECK-NEXT:    [[BASEALIAS:%.*]] = call ptr @external(ptr [[BASE]])
 435 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 436 ; CHECK:       for.body:
 437 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 438 ; CHECK-NEXT:    [[I_0_014:%.*]] = getelementptr i8, ptr [[BASE]], i64 [[INDVAR]]
 439 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[DEST]], i64 [[INDVAR]]
 440 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[I_0_014]], align 1
 441 ; CHECK-NEXT:    store i8 [[V]], ptr [[DESTI]], align 1
 442 ; CHECK-NEXT:    store i8 4, ptr [[BASEALIAS]], align 1
 443 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 444 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
 445 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 446 ; CHECK:       for.end:
 447 ; CHECK-NEXT:    ret void
 448 ;
 449 bb.nph:
 450   %Base = alloca i8, i32 10000
 451   %Dest = alloca i8, i32 10000
 452
 453   %BaseAlias = call ptr @external(ptr %Base)
 454   br label %for.body
 455
 456 for.body:                                         ; preds = %bb.nph, %for.body
 457   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
 458   %I.0.014 = getelementptr i8, ptr %Base, i64 %indvar
 459   %DestI = getelementptr i8, ptr %Dest, i64 %indvar
 460   %V = load i8, ptr %I.0.014, align 1
 461   store i8 %V, ptr %DestI, align 1
 462
 463   ;; This store can clobber the input.
 464   store i8 4, ptr %BaseAlias
 465
 466   %indvar.next = add i64 %indvar, 1
 467   %exitcond = icmp eq i64 %indvar.next, %Size
 468   br i1 %exitcond, label %for.end, label %for.body
 469
 470 for.end:                                          ; preds = %for.body, %entry
 471   ret void
 472 }
 473
 474 ; Two dimensional nested loop should be promoted to one big memset.
 475 define void @test10(ptr %X) nounwind ssp {
 476 ; CHECK-LABEL: @test10(
 477 ; CHECK-NEXT:  entry:
 478 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[X:%.*]], i8 0, i64 10000, i1 false)
 479 ; CHECK-NEXT:    br label [[BB_NPH:%.*]]
 480 ; CHECK:       bb.nph:
 481 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[FOR_INC10:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 482 ; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC12:%.*]], [[FOR_INC10]] ]
 483 ; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw nsw i64 [[INDVAR]], 100
 484 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[X]], i64 [[TMP0]]
 485 ; CHECK-NEXT:    br label [[FOR_BODY5:%.*]]
 486 ; CHECK:       for.body5:
 487 ; CHECK-NEXT:    [[J_02:%.*]] = phi i32 [ 0, [[BB_NPH]] ], [ [[INC:%.*]], [[FOR_BODY5]] ]
 488 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I_04]], 100
 489 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[J_02]], [[MUL]]
 490 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[ADD]] to i64
 491 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 [[IDXPROM]]
 492 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[J_02]], 1
 493 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i32 [[INC]], 100
 494 ; CHECK-NEXT:    br i1 [[CMP4]], label [[FOR_INC10]], label [[FOR_BODY5]]
 495 ; CHECK:       for.inc10:
 496 ; CHECK-NEXT:    [[INC12]] = add nsw i32 [[I_04]], 1
 497 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[INC12]], 100
 498 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 499 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_END13:%.*]], label [[BB_NPH]]
 500 ; CHECK:       for.end13:
 501 ; CHECK-NEXT:    ret void
 502 ;
 503 entry:
 504   br label %bb.nph
 505
 506 bb.nph:                                           ; preds = %entry, %for.inc10
 507   %i.04 = phi i32 [ 0, %entry ], [ %inc12, %for.inc10 ]
 508   br label %for.body5
 509
 510 for.body5:                                        ; preds = %for.body5, %bb.nph
 511   %j.02 = phi i32 [ 0, %bb.nph ], [ %inc, %for.body5 ]
 512   %mul = mul nsw i32 %i.04, 100
 513   %add = add nsw i32 %j.02, %mul
 514   %idxprom = sext i32 %add to i64
 515   %arrayidx = getelementptr inbounds i8, ptr %X, i64 %idxprom
 516   store i8 0, ptr %arrayidx, align 1
 517   %inc = add nsw i32 %j.02, 1
 518   %cmp4 = icmp eq i32 %inc, 100
 519   br i1 %cmp4, label %for.inc10, label %for.body5
 520
 521 for.inc10:                                        ; preds = %for.body5
 522   %inc12 = add nsw i32 %i.04, 1
 523   %cmp = icmp eq i32 %inc12, 100
 524   br i1 %cmp, label %for.end13, label %bb.nph
 525
 526 for.end13:                                        ; preds = %for.inc10
 527   ret void
 528 }
 529
 530 ; On darwin10 (which is the triple in this .ll file) this loop can be turned
 531 ; into a memset_pattern call.
 532 ; rdar://9009151
 533 define void @test11_pattern(ptr nocapture %P) nounwind ssp {
 534 ; CHECK-LABEL: @test11_pattern(
 535 ; CHECK-NEXT:  entry:
 536 ; CHECK-NEXT:    call void @memset_pattern16(ptr [[P:%.*]], ptr @.memset_pattern, i64 40000)
 537 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 538 ; CHECK:       for.body:
 539 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 540 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr i32, ptr [[P]], i64 [[INDVAR]]
 541 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 542 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 10000
 543 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 544 ; CHECK:       for.end:
 545 ; CHECK-NEXT:    ret void
 546 ;
 547 entry:
 548   br label %for.body
 549
 550 for.body:                                         ; preds = %entry, %for.body
 551   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ]
 552   %arrayidx = getelementptr i32, ptr %P, i64 %indvar
 553   store i32 1, ptr %arrayidx, align 4
 554   %indvar.next = add i64 %indvar, 1
 555   %exitcond = icmp eq i64 %indvar.next, 10000
 556   br i1 %exitcond, label %for.end, label %for.body
 557
 558 for.end:                                          ; preds = %for.body
 559   ret void
 560 }
 561
 562 ; Store of null should turn into memset of zero.
 563 define void @test12(ptr nocapture %P) nounwind ssp {
 564 ; CHECK-LABEL: @test12(
 565 ; CHECK-NEXT:  entry:
 566 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 4 [[P:%.*]], i8 0, i64 80000, i1 false)
 567 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 568 ; CHECK:       for.body:
 569 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 570 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr ptr, ptr [[P]], i64 [[INDVAR]]
 571 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 572 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 10000
 573 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 574 ; CHECK:       for.end:
 575 ; CHECK-NEXT:    ret void
 576 ;
 577 entry:
 578   br label %for.body
 579
 580 for.body:                                         ; preds = %entry, %for.body
 581   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ]
 582   %arrayidx = getelementptr ptr, ptr %P, i64 %indvar
 583   store ptr null, ptr %arrayidx, align 4
 584   %indvar.next = add i64 %indvar, 1
 585   %exitcond = icmp eq i64 %indvar.next, 10000
 586   br i1 %exitcond, label %for.end, label %for.body
 587
 588 for.end:                                          ; preds = %for.body
 589   ret void
 590 }
 591
 592 @G = global i32 5
 593
 594 ; This store-of-address loop can be turned into a memset_pattern call.
 595 ; rdar://9009151
 596 define void @test13_pattern(ptr nocapture %P) nounwind ssp {
 597 ; CHECK-LABEL: @test13_pattern(
 598 ; CHECK-NEXT:  entry:
 599 ; CHECK-NEXT:    call void @memset_pattern16(ptr [[P:%.*]], ptr @.memset_pattern.1, i64 80000)
 600 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 601 ; CHECK:       for.body:
 602 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 603 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr ptr, ptr [[P]], i64 [[INDVAR]]
 604 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 605 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 10000
 606 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 607 ; CHECK:       for.end:
 608 ; CHECK-NEXT:    ret void
 609 ;
 610 entry:
 611   br label %for.body
 612
 613 for.body:                                         ; preds = %entry, %for.body
 614   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.body ]
 615   %arrayidx = getelementptr ptr, ptr %P, i64 %indvar
 616   store ptr @G, ptr %arrayidx, align 4
 617   %indvar.next = add i64 %indvar, 1
 618   %exitcond = icmp eq i64 %indvar.next, 10000
 619   br i1 %exitcond, label %for.end, label %for.body
 620
 621 for.end:                                          ; preds = %for.body
 622   ret void
 623 }
 624
 625
 626
 627 ; PR9815 - This is a partial overlap case that cannot be safely transformed
 628 ; into a memcpy.
 629 @g_50 = global [7 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0], align 16
 630
 631 define i32 @test14() nounwind {
 632 ; CHECK-LABEL: @test14(
 633 ; CHECK-NEXT:  entry:
 634 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 635 ; CHECK:       for.body:
 636 ; CHECK-NEXT:    [[T5:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
 637 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[T5]], 4
 638 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[ADD]] to i64
 639 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [7 x i32], ptr @g_50, i32 0, i64 [[IDXPROM]]
 640 ; CHECK-NEXT:    [[T2:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 641 ; CHECK-NEXT:    [[ADD4:%.*]] = add nsw i32 [[T5]], 5
 642 ; CHECK-NEXT:    [[IDXPROM5:%.*]] = sext i32 [[ADD4]] to i64
 643 ; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [7 x i32], ptr @g_50, i32 0, i64 [[IDXPROM5]]
 644 ; CHECK-NEXT:    store i32 [[T2]], ptr [[ARRAYIDX6]], align 4
 645 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[T5]], 1
 646 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], 2
 647 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 648 ; CHECK:       for.end:
 649 ; CHECK-NEXT:    [[T8:%.*]] = load i32, ptr getelementptr inbounds ([7 x i32], ptr @g_50, i32 0, i64 6), align 4
 650 ; CHECK-NEXT:    ret i32 [[T8]]
 651 ;
 652 entry:
 653   br label %for.body
 654
 655 for.body:                                         ; preds = %for.inc, %for.body.lr.ph
 656   %t5 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 657   %add = add nsw i32 %t5, 4
 658   %idxprom = sext i32 %add to i64
 659   %arrayidx = getelementptr inbounds [7 x i32], ptr @g_50, i32 0, i64 %idxprom
 660   %t2 = load i32, ptr %arrayidx, align 4
 661   %add4 = add nsw i32 %t5, 5
 662   %idxprom5 = sext i32 %add4 to i64
 663   %arrayidx6 = getelementptr inbounds [7 x i32], ptr @g_50, i32 0, i64 %idxprom5
 664   store i32 %t2, ptr %arrayidx6, align 4
 665   %inc = add nsw i32 %t5, 1
 666   %cmp = icmp slt i32 %inc, 2
 667   br i1 %cmp, label %for.body, label %for.end
 668
 669 for.end:                                          ; preds = %for.inc
 670   %t8 = load i32, ptr getelementptr inbounds ([7 x i32], ptr @g_50, i32 0, i64 6), align 4
 671   ret i32 %t8
 672
 673 }
 674
 675 define void @PR14241(ptr %s, i64 %size) {
 676 ; Ensure that we don't form a memcpy for strided loops. Briefly, when we taught
 677 ; LoopIdiom about memmove and strided loops, this got miscompiled into a memcpy
 678 ; instead of a memmove. If we get the memmove transform back, this will catch
 679 ; regressions.
 680 ;
 681 ; CHECK-LABEL: @PR14241(
 682 ; CHECK-NEXT:  entry:
 683 ; CHECK-NEXT:    [[END_IDX:%.*]] = add i64 [[SIZE:%.*]], -1
 684 ; CHECK-NEXT:    [[END_PTR:%.*]] = getelementptr inbounds i32, ptr [[S:%.*]], i64 [[END_IDX]]
 685 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[S]], i64 4
 686 ; CHECK-NEXT:    [[TMP0:%.*]] = shl i64 [[SIZE]], 2
 687 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[TMP0]], -8
 688 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i64 [[TMP1]], 2
 689 ; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i64 [[TMP2]], 2
 690 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[TMP3]], 4
 691 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 4 [[S]], ptr align 4 [[SCEVGEP]], i64 [[TMP4]], i1 false)
 692 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
 693 ; CHECK:       while.body:
 694 ; CHECK-NEXT:    [[PHI_PTR:%.*]] = phi ptr [ [[S]], [[ENTRY:%.*]] ], [ [[NEXT_PTR:%.*]], [[WHILE_BODY]] ]
 695 ; CHECK-NEXT:    [[SRC_PTR:%.*]] = getelementptr inbounds i32, ptr [[PHI_PTR]], i64 1
 696 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[SRC_PTR]], align 4
 697 ; CHECK-NEXT:    [[NEXT_PTR]] = getelementptr inbounds i32, ptr [[PHI_PTR]], i64 1
 698 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[NEXT_PTR]], [[END_PTR]]
 699 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[WHILE_BODY]]
 700 ; CHECK:       exit:
 701 ; CHECK-NEXT:    ret void
 702 ;
 703
 704 entry:
 705   %end.idx = add i64 %size, -1
 706   %end.ptr = getelementptr inbounds i32, ptr %s, i64 %end.idx
 707   br label %while.body
 708
 709 while.body:
 710   %phi.ptr = phi ptr [ %s, %entry ], [ %next.ptr, %while.body ]
 711   %src.ptr = getelementptr inbounds i32, ptr %phi.ptr, i64 1
 712   %val = load i32, ptr %src.ptr, align 4
 713   store i32 %val, ptr %phi.ptr, align 4
 714   %next.ptr = getelementptr inbounds i32, ptr %phi.ptr, i64 1
 715   %cmp = icmp eq ptr %next.ptr, %end.ptr
 716   br i1 %cmp, label %exit, label %while.body
 717
 718 exit:
 719   ret void
 720 }
 721
 722 ; Recognize loops with a negative stride.
 723 define void @test15(ptr nocapture %f) {
 724 ; CHECK-LABEL: @test15(
 725 ; CHECK-NEXT:  entry:
 726 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 4 [[F:%.*]], i8 0, i64 262148, i1 false)
 727 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 728 ; CHECK:       for.body:
 729 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 65536, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 730 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[F]], i64 [[INDVARS_IV]]
 731 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 732 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0
 733 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
 734 ; CHECK:       for.cond.cleanup:
 735 ; CHECK-NEXT:    ret void
 736 ;
 737 entry:
 738   br label %for.body
 739
 740 for.body:
 741   %indvars.iv = phi i64 [ 65536, %entry ], [ %indvars.iv.next, %for.body ]
 742   %arrayidx = getelementptr inbounds i32, ptr %f, i64 %indvars.iv
 743   store i32 0, ptr %arrayidx, align 4
 744   %indvars.iv.next = add nsw i64 %indvars.iv, -1
 745   %cmp = icmp sgt i64 %indvars.iv, 0
 746   br i1 %cmp, label %for.body, label %for.cond.cleanup
 747
 748 for.cond.cleanup:
 749   ret void
 750 }
 751
 752 ; Loop with a negative stride.  Verify an aliasing write to f[65536] prevents
 753 ; the creation of a memset.
 754 define void @test16(ptr nocapture %f) {
 755 ; CHECK-LABEL: @test16(
 756 ; CHECK-NEXT:  entry:
 757 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, ptr [[F:%.*]], i64 65536
 758 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 759 ; CHECK:       for.body:
 760 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 65536, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 761 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[F]], i64 [[INDVARS_IV]]
 762 ; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX]], align 4
 763 ; CHECK-NEXT:    store i32 1, ptr [[ARRAYIDX1]], align 4
 764 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 765 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0
 766 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
 767 ; CHECK:       for.cond.cleanup:
 768 ; CHECK-NEXT:    ret void
 769 ;
 770 entry:
 771   %arrayidx1 = getelementptr inbounds i32, ptr %f, i64 65536
 772   br label %for.body
 773
 774 for.body:                                         ; preds = %entry, %for.body
 775   %indvars.iv = phi i64 [ 65536, %entry ], [ %indvars.iv.next, %for.body ]
 776   %arrayidx = getelementptr inbounds i32, ptr %f, i64 %indvars.iv
 777   store i32 0, ptr %arrayidx, align 4
 778   store i32 1, ptr %arrayidx1, align 4
 779   %indvars.iv.next = add nsw i64 %indvars.iv, -1
 780   %cmp = icmp sgt i64 %indvars.iv, 0
 781   br i1 %cmp, label %for.body, label %for.cond.cleanup
 782
 783 for.cond.cleanup:                                 ; preds = %for.body
 784   ret void
 785 }
 786
 787 ; Handle memcpy-able loops with negative stride.
 788 define noalias ptr @test17(ptr nocapture readonly %a, i32 %c) {
 789 ; CHECK-LABEL: @test17(
 790 ; CHECK-NEXT:  entry:
 791 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[C:%.*]] to i64
 792 ; CHECK-NEXT:    [[MUL:%.*]] = shl nsw i64 [[CONV]], 2
 793 ; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias ptr @malloc(i64 [[MUL]])
 794 ; CHECK-NEXT:    [[TOBOOL_9:%.*]] = icmp eq i32 [[C]], 0
 795 ; CHECK-NEXT:    br i1 [[TOBOOL_9]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
 796 ; CHECK:       while.body.preheader:
 797 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[C]], -1
 798 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[TMP0]] to i64
 799 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nsw i64 [[TMP1]], 2
 800 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP0]] to i64
 801 ; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i64 [[TMP3]], 2
 802 ; CHECK-NEXT:    [[TMP5:%.*]] = sub i64 [[TMP2]], [[TMP4]]
 803 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[CALL]], i64 [[TMP5]]
 804 ; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[A:%.*]], i64 [[TMP5]]
 805 ; CHECK-NEXT:    [[TMP6:%.*]] = zext i32 [[C]] to i64
 806 ; CHECK-NEXT:    [[TMP7:%.*]] = shl nuw nsw i64 [[TMP6]], 2
 807 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[SCEVGEP]], ptr align 4 [[SCEVGEP1]], i64 [[TMP7]], i1 false)
 808 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
 809 ; CHECK:       while.body:
 810 ; CHECK-NEXT:    [[DEC10_IN:%.*]] = phi i32 [ [[DEC10:%.*]], [[WHILE_BODY]] ], [ [[C]], [[WHILE_BODY_PREHEADER]] ]
 811 ; CHECK-NEXT:    [[DEC10]] = add nsw i32 [[DEC10_IN]], -1
 812 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[DEC10]] to i64
 813 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]
 814 ; CHECK-NEXT:    [[TMP8:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 815 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[CALL]], i64 [[IDXPROM]]
 816 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[DEC10]], 0
 817 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
 818 ; CHECK:       while.end.loopexit:
 819 ; CHECK-NEXT:    br label [[WHILE_END]]
 820 ; CHECK:       while.end:
 821 ; CHECK-NEXT:    ret ptr [[CALL]]
 822 ;
 823 entry:
 824   %conv = sext i32 %c to i64
 825   %mul = shl nsw i64 %conv, 2
 826   %call = tail call noalias ptr @malloc(i64 %mul)
 827   %tobool.9 = icmp eq i32 %c, 0
 828   br i1 %tobool.9, label %while.end, label %while.body.preheader
 829
 830 while.body.preheader:                             ; preds = %entry
 831   br label %while.body
 832
 833 while.body:                                       ; preds = %while.body.preheader, %while.body
 834   %dec10.in = phi i32 [ %dec10, %while.body ], [ %c, %while.body.preheader ]
 835   %dec10 = add nsw i32 %dec10.in, -1
 836   %idxprom = sext i32 %dec10 to i64
 837   %arrayidx = getelementptr inbounds i32, ptr %a, i64 %idxprom
 838   %0 = load i32, ptr %arrayidx, align 4
 839   %arrayidx2 = getelementptr inbounds i32, ptr %call, i64 %idxprom
 840   store i32 %0, ptr %arrayidx2, align 4
 841   %tobool = icmp eq i32 %dec10, 0
 842   br i1 %tobool, label %while.end.loopexit, label %while.body
 843
 844 while.end.loopexit:                               ; preds = %while.body
 845   br label %while.end
 846
 847 while.end:                                        ; preds = %while.end.loopexit, %entry
 848   ret ptr %call
 849 }
 850
 851 declare noalias ptr @malloc(i64)
 852
 853 ; Handle memcpy-able loops with negative stride.
 854 ; void test18(unsigned *__restrict__ a, unsigned *__restrict__ b) {
 855 ;   for (int i = 2047; i >= 0; --i) {
 856 ;     a[i] = b[i];
 857 ;   }
 858 ; }
 859 define void @test18(ptr noalias nocapture %a, ptr noalias nocapture readonly %b) #0 {
 860 ; CHECK-LABEL: @test18(
 861 ; CHECK-NEXT:  entry:
 862 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[A:%.*]], ptr align 4 [[B:%.*]], i64 8192, i1 false)
 863 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 864 ; CHECK:       for.body:
 865 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 2047, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 866 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[INDVARS_IV]]
 867 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 868 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[INDVARS_IV]]
 869 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 870 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0
 871 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
 872 ; CHECK:       for.cond.cleanup:
 873 ; CHECK-NEXT:    ret void
 874 ;
 875 entry:
 876   br label %for.body
 877
 878 for.body:                                         ; preds = %entry, %for.body
 879   %indvars.iv = phi i64 [ 2047, %entry ], [ %indvars.iv.next, %for.body ]
 880   %arrayidx = getelementptr inbounds i32, ptr %b, i64 %indvars.iv
 881   %0 = load i32, ptr %arrayidx, align 4
 882   %arrayidx2 = getelementptr inbounds i32, ptr %a, i64 %indvars.iv
 883   store i32 %0, ptr %arrayidx2, align 4
 884   %indvars.iv.next = add nsw i64 %indvars.iv, -1
 885   %cmp = icmp sgt i64 %indvars.iv, 0
 886   br i1 %cmp, label %for.body, label %for.cond.cleanup
 887
 888 for.cond.cleanup:                                 ; preds = %for.body
 889   ret void
 890 }
 891
 892 ; Two dimensional nested loop with negative stride should be promoted to one big memset.
 893 define void @test19(ptr nocapture %X) {
 894 ; CHECK-LABEL: @test19(
 895 ; CHECK-NEXT:  entry:
 896 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 1 [[X:%.*]], i8 0, i64 10000, i1 false)
 897 ; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
 898 ; CHECK:       for.cond1.preheader:
 899 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[FOR_INC4:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 900 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 99, [[ENTRY]] ], [ [[DEC5:%.*]], [[FOR_INC4]] ]
 901 ; CHECK-NEXT:    [[TMP0:%.*]] = mul nsw i64 [[INDVAR]], -100
 902 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[TMP0]], 9900
 903 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[X]], i64 [[TMP1]]
 904 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I_06]], 100
 905 ; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
 906 ; CHECK:       for.body3:
 907 ; CHECK-NEXT:    [[J_05:%.*]] = phi i32 [ 99, [[FOR_COND1_PREHEADER]] ], [ [[DEC:%.*]], [[FOR_BODY3]] ]
 908 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[J_05]], [[MUL]]
 909 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[ADD]] to i64
 910 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 [[IDXPROM]]
 911 ; CHECK-NEXT:    [[DEC]] = add nsw i32 [[J_05]], -1
 912 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[J_05]], 0
 913 ; CHECK-NEXT:    br i1 [[CMP2]], label [[FOR_BODY3]], label [[FOR_INC4]]
 914 ; CHECK:       for.inc4:
 915 ; CHECK-NEXT:    [[DEC5]] = add nsw i32 [[I_06]], -1
 916 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[I_06]], 0
 917 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
 918 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_COND1_PREHEADER]], label [[FOR_END6:%.*]]
 919 ; CHECK:       for.end6:
 920 ; CHECK-NEXT:    ret void
 921 ;
 922 entry:
 923   br label %for.cond1.preheader
 924
 925 for.cond1.preheader:                              ; preds = %entry, %for.inc4
 926   %i.06 = phi i32 [ 99, %entry ], [ %dec5, %for.inc4 ]
 927   %mul = mul nsw i32 %i.06, 100
 928   br label %for.body3
 929
 930 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 931   %j.05 = phi i32 [ 99, %for.cond1.preheader ], [ %dec, %for.body3 ]
 932   %add = add nsw i32 %j.05, %mul
 933   %idxprom = sext i32 %add to i64
 934   %arrayidx = getelementptr inbounds i8, ptr %X, i64 %idxprom
 935   store i8 0, ptr %arrayidx, align 1
 936   %dec = add nsw i32 %j.05, -1
 937   %cmp2 = icmp sgt i32 %j.05, 0
 938   br i1 %cmp2, label %for.body3, label %for.inc4
 939
 940 for.inc4:                                         ; preds = %for.body3
 941   %dec5 = add nsw i32 %i.06, -1
 942   %cmp = icmp sgt i32 %i.06, 0
 943   br i1 %cmp, label %for.cond1.preheader, label %for.end6
 944
 945 for.end6:                                         ; preds = %for.inc4
 946   ret void
 947 }
 948
 949 ; Handle loops where the trip count is a narrow integer that needs to be
 950 ; extended.
 951 define void @form_memset_narrow_size(ptr %ptr, i32 %size) {
 952 ; CHECK-LABEL: @form_memset_narrow_size(
 953 ; CHECK-NEXT:  entry:
 954 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[SIZE:%.*]], 0
 955 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LOOP_PH:%.*]], label [[EXIT:%.*]]
 956 ; CHECK:       loop.ph:
 957 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[SIZE]] to i64
 958 ; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 3
 959 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 8 [[PTR:%.*]], i8 0, i64 [[TMP1]], i1 false)
 960 ; CHECK-NEXT:    br label [[LOOP_BODY:%.*]]
 961 ; CHECK:       loop.body:
 962 ; CHECK-NEXT:    [[STOREMERGE4:%.*]] = phi i32 [ 0, [[LOOP_PH]] ], [ [[INC:%.*]], [[LOOP_BODY]] ]
 963 ; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[STOREMERGE4]] to i64
 964 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i64, ptr [[PTR]], i64 [[IDXPROM]]
 965 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[STOREMERGE4]], 1
 966 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[INC]], [[SIZE]]
 967 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_BODY]], label [[LOOP_EXIT:%.*]]
 968 ; CHECK:       loop.exit:
 969 ; CHECK-NEXT:    br label [[EXIT]]
 970 ; CHECK:       exit:
 971 ; CHECK-NEXT:    ret void
 972 ;
 973 entry:
 974   %cmp1 = icmp sgt i32 %size, 0
 975   br i1 %cmp1, label %loop.ph, label %exit
 976
 977 loop.ph:
 978   br label %loop.body
 979
 980 loop.body:
 981   %storemerge4 = phi i32 [ 0, %loop.ph ], [ %inc, %loop.body ]
 982   %idxprom = sext i32 %storemerge4 to i64
 983   %arrayidx = getelementptr inbounds i64, ptr %ptr, i64 %idxprom
 984   store i64 0, ptr %arrayidx, align 8
 985   %inc = add nsw i32 %storemerge4, 1
 986   %cmp2 = icmp slt i32 %inc, %size
 987   br i1 %cmp2, label %loop.body, label %loop.exit
 988
 989 loop.exit:
 990   br label %exit
 991
 992 exit:
 993   ret void
 994 }
 995
 996 define void @form_memcpy_narrow_size(ptr noalias %dst, ptr noalias %src, i32 %size) {
 997 ; CHECK-LABEL: @form_memcpy_narrow_size(
 998 ; CHECK-NEXT:  entry:
 999 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[SIZE:%.*]], 0
1000 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LOOP_PH:%.*]], label [[EXIT:%.*]]
1001 ; CHECK:       loop.ph:
1002 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[SIZE]] to i64
1003 ; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 3
1004 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 8 [[DST:%.*]], ptr align 8 [[SRC:%.*]], i64 [[TMP1]], i1 false)
1005 ; CHECK-NEXT:    br label [[LOOP_BODY:%.*]]
1006 ; CHECK:       loop.body:
1007 ; CHECK-NEXT:    [[STOREMERGE4:%.*]] = phi i32 [ 0, [[LOOP_PH]] ], [ [[INC:%.*]], [[LOOP_BODY]] ]
1008 ; CHECK-NEXT:    [[IDXPROM1:%.*]] = sext i32 [[STOREMERGE4]] to i64
1009 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[IDXPROM1]]
1010 ; CHECK-NEXT:    [[V:%.*]] = load i64, ptr [[ARRAYIDX1]], align 8
1011 ; CHECK-NEXT:    [[IDXPROM2:%.*]] = sext i32 [[STOREMERGE4]] to i64
1012 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i64, ptr [[DST]], i64 [[IDXPROM2]]
1013 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[STOREMERGE4]], 1
1014 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[INC]], [[SIZE]]
1015 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_BODY]], label [[LOOP_EXIT:%.*]]
1016 ; CHECK:       loop.exit:
1017 ; CHECK-NEXT:    br label [[EXIT]]
1018 ; CHECK:       exit:
1019 ; CHECK-NEXT:    ret void
1020 ;
1021 entry:
1022   %cmp1 = icmp sgt i32 %size, 0
1023   br i1 %cmp1, label %loop.ph, label %exit
1024
1025 loop.ph:
1026   br label %loop.body
1027
1028 loop.body:
1029   %storemerge4 = phi i32 [ 0, %loop.ph ], [ %inc, %loop.body ]
1030   %idxprom1 = sext i32 %storemerge4 to i64
1031   %arrayidx1 = getelementptr inbounds i64, ptr %src, i64 %idxprom1
1032   %v = load i64, ptr %arrayidx1, align 8
1033   %idxprom2 = sext i32 %storemerge4 to i64
1034   %arrayidx2 = getelementptr inbounds i64, ptr %dst, i64 %idxprom2
1035   store i64 %v, ptr %arrayidx2, align 8
1036   %inc = add nsw i32 %storemerge4, 1
1037   %cmp2 = icmp slt i32 %inc, %size
1038   br i1 %cmp2, label %loop.body, label %loop.exit
1039
1040 loop.exit:
1041   br label %exit
1042
1043 exit:
1044   ret void
1045 }
1046
1047 ;; Memmove formation.
1048 define void @PR46179_positive_stride(ptr %Src, i64 %Size) {
1049 ; CHECK-LABEL: @PR46179_positive_stride(
1050 ; CHECK-NEXT:  bb.nph:
1051 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 1
1052 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 1 [[SRC]], ptr align 1 [[SCEVGEP]], i64 [[SIZE:%.*]], i1 false)
1053 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1054 ; CHECK:       for.body:
1055 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1056 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
1057 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[STEP]]
1058 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[INDVAR]]
1059 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[SRCI]], align 1
1060 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1061 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
1062 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1063 ; CHECK:       for.end:
1064 ; CHECK-NEXT:    ret void
1065 ;
1066 bb.nph:
1067   br label %for.body
1068
1069 for.body:                                         ; preds = %bb.nph, %for.body
1070   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
1071   %Step = add nuw nsw i64 %indvar, 1
1072   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1073   %DestI = getelementptr i8, ptr %Src, i64 %indvar
1074   %V = load i8, ptr %SrcI, align 1
1075   store i8 %V, ptr %DestI, align 1
1076   %indvar.next = add i64 %indvar, 1
1077   %exitcond = icmp eq i64 %indvar.next, %Size
1078   br i1 %exitcond, label %for.end, label %for.body
1079
1080 for.end:                                          ; preds = %for.body, %entry
1081   ret void
1082 }
1083
1084 declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg)
1085
1086 ;; Memmove formation. We expect exactly same memmove result like in PR46179_positive_stride output.
1087 define void @loop_with_memcpy_PR46179_positive_stride(ptr %Src, i64 %Size) {
1088 ; CHECK-LABEL: @loop_with_memcpy_PR46179_positive_stride(
1089 ; CHECK-NEXT:  bb.nph:
1090 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 1
1091 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 1 [[SRC]], ptr align 1 [[SCEVGEP]], i64 [[SIZE:%.*]], i1 false)
1092 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1093 ; CHECK:       for.body:
1094 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1095 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
1096 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[STEP]]
1097 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[INDVAR]]
1098 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1099 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
1100 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1101 ; CHECK:       for.end:
1102 ; CHECK-NEXT:    ret void
1103 ;
1104 bb.nph:
1105   br label %for.body
1106
1107 for.body:                                         ; preds = %bb.nph, %for.body
1108   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
1109   %Step = add nuw nsw i64 %indvar, 1
1110   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1111   %DestI = getelementptr i8, ptr %Src, i64 %indvar
1112   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 1, i1 false)
1113   %indvar.next = add i64 %indvar, 1
1114   %exitcond = icmp eq i64 %indvar.next, %Size
1115   br i1 %exitcond, label %for.end, label %for.body
1116
1117 for.end:                                          ; preds = %for.body, %entry
1118   ret void
1119 }
1120
1121 ;; Memmove formation.
1122 define void @PR46179_negative_stride(ptr %Src, i64 %Size) {
1123 ; CHECK-LABEL: @PR46179_negative_stride(
1124 ; CHECK-NEXT:  bb.nph:
1125 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i64 [[SIZE:%.*]], 0
1126 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
1127 ; CHECK:       for.body.preheader:
1128 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 1
1129 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 1 [[SCEVGEP]], ptr align 1 [[SRC]], i64 [[SIZE]], i1 false)
1130 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1131 ; CHECK:       for.body:
1132 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[STEP:%.*]], [[FOR_BODY]] ], [ [[SIZE]], [[FOR_BODY_PREHEADER]] ]
1133 ; CHECK-NEXT:    [[STEP]] = add nsw i64 [[INDVAR]], -1
1134 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[STEP]]
1135 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[SRCI]], align 1
1136 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[INDVAR]]
1137 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp sgt i64 [[INDVAR]], 1
1138 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
1139 ; CHECK:       for.end.loopexit:
1140 ; CHECK-NEXT:    br label [[FOR_END]]
1141 ; CHECK:       for.end:
1142 ; CHECK-NEXT:    ret void
1143 ;
1144 bb.nph:
1145   %cmp1 = icmp sgt i64 %Size, 0
1146   br i1 %cmp1, label %for.body, label %for.end
1147
1148 for.body:                                           ; preds = %bb.nph, %.for.body
1149   %indvar = phi i64 [ %Step, %for.body ], [ %Size, %bb.nph ]
1150   %Step = add nsw i64 %indvar, -1
1151   %SrcI = getelementptr inbounds i8, ptr %Src, i64 %Step
1152   %V = load i8, ptr %SrcI, align 1
1153   %DestI = getelementptr inbounds i8, ptr %Src, i64 %indvar
1154   store i8 %V, ptr %DestI, align 1
1155   %exitcond = icmp sgt i64 %indvar, 1
1156   br i1 %exitcond, label %for.body, label %for.end
1157
1158 for.end:                                      ; preds = %.for.body, %bb.nph
1159   ret void
1160 }
1161
1162 ;; Memmove formation. We expect exactly same memmove result like in PR46179_negative_stride output.
1163 define void @loop_with_memcpy_PR46179_negative_stride(ptr %Src, i64 %Size) {
1164 ; CHECK-LABEL: @loop_with_memcpy_PR46179_negative_stride(
1165 ; CHECK-NEXT:  bb.nph:
1166 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i64 [[SIZE:%.*]], 0
1167 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
1168 ; CHECK:       for.body.preheader:
1169 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 1
1170 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 1 [[SCEVGEP]], ptr align 1 [[SRC]], i64 [[SIZE]], i1 false)
1171 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1172 ; CHECK:       for.body:
1173 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[STEP:%.*]], [[FOR_BODY]] ], [ [[SIZE]], [[FOR_BODY_PREHEADER]] ]
1174 ; CHECK-NEXT:    [[STEP]] = add nsw i64 [[INDVAR]], -1
1175 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[STEP]]
1176 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[INDVAR]]
1177 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp sgt i64 [[INDVAR]], 1
1178 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
1179 ; CHECK:       for.end.loopexit:
1180 ; CHECK-NEXT:    br label [[FOR_END]]
1181 ; CHECK:       for.end:
1182 ; CHECK-NEXT:    ret void
1183 ;
1184 bb.nph:
1185   %cmp1 = icmp sgt i64 %Size, 0
1186   br i1 %cmp1, label %for.body, label %for.end
1187
1188 for.body:                                           ; preds = %bb.nph, %.for.body
1189   %indvar = phi i64 [ %Step, %for.body ], [ %Size, %bb.nph ]
1190   %Step = add nsw i64 %indvar, -1
1191   %SrcI = getelementptr inbounds i8, ptr %Src, i64 %Step
1192   %DestI = getelementptr inbounds i8, ptr %Src, i64 %indvar
1193   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 1, i1 false)
1194   %exitcond = icmp sgt i64 %indvar, 1
1195   br i1 %exitcond, label %for.body, label %for.end
1196
1197 for.end:                                      ; preds = %.for.body, %bb.nph
1198   ret void
1199 }
1200
1201 ;; Memmove formation.
1202 define void @loop_with_memcpy_stride16(ptr %Src, i64 %Size) {
1203 ; CHECK-LABEL: @loop_with_memcpy_stride16(
1204 ; CHECK-NEXT:  bb.nph:
1205 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 16
1206 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[SIZE:%.*]], i64 16)
1207 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[SMAX]], -1
1208 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[TMP0]], 4
1209 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 4
1210 ; CHECK-NEXT:    [[TMP3:%.*]] = add nuw i64 [[TMP2]], 16
1211 ; CHECK-NEXT:    call void @llvm.memmove.p0.p0.i64(ptr align 1 [[SRC]], ptr align 1 [[SCEVGEP]], i64 [[TMP3]], i1 false)
1212 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1213 ; CHECK:       for.body:
1214 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[STEP:%.*]], [[FOR_BODY]] ], [ 0, [[BB_NPH:%.*]] ]
1215 ; CHECK-NEXT:    [[STEP]] = add nuw nsw i64 [[INDVAR]], 16
1216 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[STEP]]
1217 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[INDVAR]]
1218 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp slt i64 [[STEP]], [[SIZE]]
1219 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
1220 ; CHECK:       for.end:
1221 ; CHECK-NEXT:    ret void
1222 ;
1223 bb.nph:
1224   br label %for.body
1225
1226 for.body:                                                ; preds = %for.body, %bb.nph
1227   %indvar = phi i64 [ %Step, %for.body ], [ 0, %bb.nph ]
1228   %Step = add nuw nsw i64 %indvar, 16
1229   %SrcI = getelementptr inbounds i8, ptr %Src, i64 %Step
1230   %DestI = getelementptr inbounds i8, ptr %Src, i64 %indvar
1231   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 16, i1 false)
1232   %exitcond = icmp slt i64 %Step, %Size
1233   br i1 %exitcond, label %for.body, label %for.end
1234
1235 for.end:                                                ; preds = %for.body
1236   ret void
1237 }
1238
1239 ;; Do not form memmove from previous load when stride is positive.
1240 define void @do_not_form_memmove1(ptr %Src, i64 %Size) {
1241 ; CHECK-LABEL: @do_not_form_memmove1(
1242 ; CHECK-NEXT:  bb.nph:
1243 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1244 ; CHECK:       for.body:
1245 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 1, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1246 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], -1
1247 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 [[STEP]]
1248 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[INDVAR]]
1249 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[SRCI]], align 1
1250 ; CHECK-NEXT:    store i8 [[V]], ptr [[DESTI]], align 1
1251 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1252 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
1253 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1254 ; CHECK:       for.end:
1255 ; CHECK-NEXT:    ret void
1256 ;
1257 bb.nph:
1258   br label %for.body
1259
1260 for.body:                                         ; preds = %bb.nph, %for.body
1261   %indvar = phi i64 [ 1, %bb.nph ], [ %indvar.next, %for.body ]
1262   %Step = add nuw nsw i64 %indvar, -1
1263   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1264   %DestI = getelementptr i8, ptr %Src, i64 %indvar
1265   %V = load i8, ptr %SrcI, align 1
1266   store i8 %V, ptr %DestI, align 1
1267   %indvar.next = add i64 %indvar, 1
1268   %exitcond = icmp eq i64 %indvar.next, %Size
1269   br i1 %exitcond, label %for.end, label %for.body
1270
1271 for.end:                                          ; preds = %for.body, %entry
1272   ret void
1273 }
1274
1275 ;; Do not form memmove from previous load in memcpy when stride is positive.
1276 define void @do_not_form_memmove2(ptr %Src, i64 %Size) {
1277 ; CHECK-LABEL: @do_not_form_memmove2(
1278 ; CHECK-NEXT:  bb.nph:
1279 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1280 ; CHECK:       for.body:
1281 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 1, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1282 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], -1
1283 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 [[STEP]]
1284 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[INDVAR]]
1285 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DESTI]], ptr align 1 [[SRCI]], i64 1, i1 false)
1286 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1287 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
1288 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1289 ; CHECK:       for.end:
1290 ; CHECK-NEXT:    ret void
1291 ;
1292 bb.nph:
1293   br label %for.body
1294
1295 for.body:                                         ; preds = %bb.nph, %for.body
1296   %indvar = phi i64 [ 1, %bb.nph ], [ %indvar.next, %for.body ]
1297   %Step = add nuw nsw i64 %indvar, -1
1298   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1299   %DestI = getelementptr i8, ptr %Src, i64 %indvar
1300   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 1, i1 false)
1301   %indvar.next = add i64 %indvar, 1
1302   %exitcond = icmp eq i64 %indvar.next, %Size
1303   br i1 %exitcond, label %for.end, label %for.body
1304
1305 for.end:                                          ; preds = %for.body, %entry
1306   ret void
1307 }
1308
1309 ;; Do not form memmove from next load when stride is negative.
1310 define void @do_not_form_memmove3(ptr %Src, i64 %Size) {
1311 ; CHECK-LABEL: @do_not_form_memmove3(
1312 ; CHECK-NEXT:  bb.nph:
1313 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i64 [[SIZE:%.*]], 0
1314 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
1315 ; CHECK:       for.body.preheader:
1316 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1317 ; CHECK:       for.body:
1318 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ], [ [[SIZE]], [[FOR_BODY_PREHEADER]] ]
1319 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
1320 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr inbounds i8, ptr [[SRC:%.*]], i64 [[STEP]]
1321 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[SRCI]], align 1
1322 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[INDVAR]]
1323 ; CHECK-NEXT:    store i8 [[V]], ptr [[DESTI]], align 1
1324 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add nsw i64 [[INDVAR]], -1
1325 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp sgt i64 [[INDVAR]], 1
1326 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
1327 ; CHECK:       for.end.loopexit:
1328 ; CHECK-NEXT:    br label [[FOR_END]]
1329 ; CHECK:       for.end:
1330 ; CHECK-NEXT:    ret void
1331 ;
1332 bb.nph:
1333   %cmp1 = icmp sgt i64 %Size, 0
1334   br i1 %cmp1, label %for.body, label %for.end
1335
1336 for.body:                                           ; preds = %bb.nph, %.for.body
1337   %indvar = phi i64 [ %indvar.next, %for.body ], [ %Size, %bb.nph ]
1338   %Step = add nuw nsw i64 %indvar, 1
1339   %SrcI = getelementptr inbounds i8, ptr %Src, i64 %Step
1340   %V = load i8, ptr %SrcI, align 1
1341   %DestI = getelementptr inbounds i8, ptr %Src, i64 %indvar
1342   store i8 %V, ptr %DestI, align 1
1343   %indvar.next = add nsw i64 %indvar, -1
1344   %exitcond = icmp sgt i64 %indvar, 1
1345   br i1 %exitcond, label %for.body, label %for.end
1346
1347 for.end:                                      ; preds = %.for.body, %bb.nph
1348   ret void
1349 }
1350
1351 ;; Do not form memmove from next load in memcpy when stride is negative.
1352 define void @do_not_form_memmove4(ptr %Src, i64 %Size) {
1353 ; CHECK-LABEL: @do_not_form_memmove4(
1354 ; CHECK-NEXT:  bb.nph:
1355 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i64 [[SIZE:%.*]], 0
1356 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
1357 ; CHECK:       for.body.preheader:
1358 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1359 ; CHECK:       for.body:
1360 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ], [ [[SIZE]], [[FOR_BODY_PREHEADER]] ]
1361 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
1362 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr inbounds i8, ptr [[SRC:%.*]], i64 [[STEP]]
1363 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i64 [[INDVAR]]
1364 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DESTI]], ptr align 1 [[SRCI]], i64 1, i1 false)
1365 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add nsw i64 [[INDVAR]], -1
1366 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp sgt i64 [[INDVAR]], 1
1367 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
1368 ; CHECK:       for.end.loopexit:
1369 ; CHECK-NEXT:    br label [[FOR_END]]
1370 ; CHECK:       for.end:
1371 ; CHECK-NEXT:    ret void
1372 ;
1373 bb.nph:
1374   %cmp1 = icmp sgt i64 %Size, 0
1375   br i1 %cmp1, label %for.body, label %for.end
1376
1377 for.body:                                           ; preds = %bb.nph, %.for.body
1378   %indvar = phi i64 [ %indvar.next, %for.body ], [ %Size, %bb.nph ]
1379   %Step = add nuw nsw i64 %indvar, 1
1380   %SrcI = getelementptr inbounds i8, ptr %Src, i64 %Step
1381   %DestI = getelementptr inbounds i8, ptr %Src, i64 %indvar
1382   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 1, i1 false)
1383   %indvar.next = add nsw i64 %indvar, -1
1384   %exitcond = icmp sgt i64 %indvar, 1
1385   br i1 %exitcond, label %for.body, label %for.end
1386
1387 for.end:                                      ; preds = %.for.body, %bb.nph
1388   ret void
1389 }
1390
1391 ;; Do not form memmove when underaligned load is overlapped with store.
1392 define void @do_not_form_memmove5(ptr %s, i64 %size) {
1393 ; CHECK-LABEL: @do_not_form_memmove5(
1394 ; CHECK-NEXT:  entry:
1395 ; CHECK-NEXT:    [[END_IDX:%.*]] = add i64 [[SIZE:%.*]], -1
1396 ; CHECK-NEXT:    [[END_PTR:%.*]] = getelementptr inbounds i32, ptr [[S:%.*]], i64 [[END_IDX]]
1397 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
1398 ; CHECK:       while.body:
1399 ; CHECK-NEXT:    [[PHI_PTR:%.*]] = phi ptr [ [[S]], [[ENTRY:%.*]] ], [ [[NEXT_PTR:%.*]], [[WHILE_BODY]] ]
1400 ; CHECK-NEXT:    [[SRC_PTR:%.*]] = getelementptr i16, ptr [[PHI_PTR]], i64 1
1401 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[SRC_PTR]], align 2
1402 ; CHECK-NEXT:    store i32 [[VAL]], ptr [[PHI_PTR]], align 4
1403 ; CHECK-NEXT:    [[NEXT_PTR]] = getelementptr i32, ptr [[PHI_PTR]], i64 1
1404 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[NEXT_PTR]], [[END_PTR]]
1405 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[WHILE_BODY]]
1406 ; CHECK:       exit:
1407 ; CHECK-NEXT:    ret void
1408 ;
1409 entry:
1410   %end.idx = add i64 %size, -1
1411   %end.ptr = getelementptr inbounds i32, ptr %s, i64 %end.idx
1412   br label %while.body
1413
1414 while.body:
1415   %phi.ptr = phi ptr [ %s, %entry ], [ %next.ptr, %while.body ]
1416   %src.ptr = getelementptr i16, ptr %phi.ptr, i64 1
1417   ; below underaligned load is overlapped with store.
1418   %val = load i32, ptr %src.ptr, align 2
1419   store i32 %val, ptr %phi.ptr, align 4
1420   %next.ptr = getelementptr i32, ptr %phi.ptr, i64 1
1421   %cmp = icmp eq ptr %next.ptr, %end.ptr
1422   br i1 %cmp, label %exit, label %while.body
1423
1424 exit:
1425   ret void
1426 }
1427
1428 ;; Do not form memmove for memcpy with aliasing store.
1429 define void @do_not_form_memmove6(ptr %Src, i64 %Size) {
1430 ; CHECK-LABEL: @do_not_form_memmove6(
1431 ; CHECK-NEXT:  bb.nph:
1432 ; CHECK-NEXT:    [[BASEALIAS:%.*]] = call ptr @external(ptr [[SRC:%.*]])
1433 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1434 ; CHECK:       for.body:
1435 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1436 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
1437 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[STEP]]
1438 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[INDVAR]]
1439 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DESTI]], ptr align 1 [[SRCI]], i64 1, i1 false)
1440 ; CHECK-NEXT:    store i8 4, ptr [[BASEALIAS]], align 1
1441 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1442 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
1443 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1444 ; CHECK:       for.end:
1445 ; CHECK-NEXT:    ret void
1446 ;
1447 bb.nph:
1448   %BaseAlias = call ptr @external(ptr %Src)
1449   br label %for.body
1450
1451 for.body:                                         ; preds = %bb.nph, %for.body
1452   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
1453   %Step = add nuw nsw i64 %indvar, 1
1454   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1455   %DestI = getelementptr i8, ptr %Src, i64 %indvar
1456   call void @llvm.memcpy.p0.p0.i64(ptr align 1 %DestI, ptr align 1 %SrcI, i64 1, i1 false)
1457   store i8 4, ptr %BaseAlias
1458   %indvar.next = add i64 %indvar, 1
1459   %exitcond = icmp eq i64 %indvar.next, %Size
1460   br i1 %exitcond, label %for.end, label %for.body
1461
1462 for.end:                                          ; preds = %for.body, %entry
1463   ret void
1464 }
1465
1466 ;; Do not form memmove when load has more than one use.
1467 define i32 @do_not_form_memmove7(ptr %p) {
1468 ; CHECK-LABEL: @do_not_form_memmove7(
1469 ; CHECK-NEXT:  entry:
1470 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1471 ; CHECK:       for.cond.cleanup:
1472 ; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ]
1473 ; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
1474 ; CHECK:       for.body:
1475 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 15, [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[FOR_BODY]] ]
1476 ; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD]], [[FOR_BODY]] ]
1477 ; CHECK-NEXT:    [[SUB]] = add nsw i32 [[INDEX]], -1
1478 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[SUB]] to i64
1479 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[TMP0]]
1480 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
1481 ; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[INDEX]] to i64
1482 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[P]], i64 [[IDXPROM]]
1483 ; CHECK-NEXT:    store i32 [[TMP1]], ptr [[ARRAYIDX2]], align 4
1484 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[TMP1]], [[SUM]]
1485 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[INDEX]], 1
1486 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
1487 ;
1488 entry:
1489   br label %for.body
1490
1491 for.cond.cleanup:                                 ; preds = %for.body
1492   %add.lcssa = phi i32 [ %add, %for.body ]
1493   ret i32 %add.lcssa
1494
1495 for.body:                                      ; preds = %entry, %for.body
1496   %index = phi i32 [ 15, %entry ], [ %sub, %for.body ]
1497   %sum = phi i32 [ 0, %entry ], [ %add, %for.body ]
1498   %sub = add nsw i32 %index, -1
1499   %0 = zext i32 %sub to i64
1500   %arrayidx = getelementptr inbounds i32, ptr %p, i64 %0
1501   %1 = load i32, ptr %arrayidx, align 4
1502   %idxprom = zext i32 %index to i64
1503   %arrayidx2 = getelementptr inbounds i32, ptr %p, i64 %idxprom
1504   store i32 %1, ptr %arrayidx2, align 4
1505   %add = add nsw i32 %1, %sum
1506   %cmp = icmp sgt i32 %index, 1
1507   br i1 %cmp, label %for.body, label %for.cond.cleanup
1508 }
1509
1510 ; Do not form memmove when there's an aliasing operation, even
1511 ; if the memcpy source and destination are in the same object.
1512 define void @do_not_form_memmove8(ptr %p) {
1513 ; CHECK-LABEL: @do_not_form_memmove8(
1514 ; CHECK-NEXT:  entry:
1515 ; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i64, ptr [[P:%.*]], i64 1000
1516 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1517 ; CHECK:       exit:
1518 ; CHECK-NEXT:    ret void
1519 ; CHECK:       loop:
1520 ; CHECK-NEXT:    [[X4:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X13:%.*]], [[LOOP]] ]
1521 ; CHECK-NEXT:    [[X5:%.*]] = zext i32 [[X4]] to i64
1522 ; CHECK-NEXT:    [[X7:%.*]] = getelementptr inbounds i64, ptr [[P2]], i64 [[X5]]
1523 ; CHECK-NEXT:    store i64 1, ptr [[X7]], align 4
1524 ; CHECK-NEXT:    [[X11:%.*]] = getelementptr inbounds i64, ptr [[P]], i64 [[X5]]
1525 ; CHECK-NEXT:    tail call void @llvm.memcpy.p0.p0.i64(ptr [[X11]], ptr [[X7]], i64 8, i1 false)
1526 ; CHECK-NEXT:    [[X13]] = add i32 [[X4]], 1
1527 ; CHECK-NEXT:    [[X14:%.*]] = icmp eq i32 [[X13]], 44
1528 ; CHECK-NEXT:    br i1 [[X14]], label [[EXIT:%.*]], label [[LOOP]]
1529 ;
1530 entry:
1531   %p2 = getelementptr inbounds i64, ptr %p, i64 1000
1532   br label %loop
1533
1534 exit:
1535   ret void
1536
1537 loop:
1538   %x4 = phi i32 [ 0, %entry ], [ %x13, %loop ]
1539   %x5 = zext i32 %x4 to i64
1540   %x7 = getelementptr inbounds i64, ptr %p2, i64 %x5
1541   store i64 1, ptr %x7, align 4
1542   %x11 = getelementptr inbounds i64, ptr %p, i64 %x5
1543   tail call void @llvm.memcpy.p0.p0.i64(ptr %x11, ptr %x7, i64 8, i1 false)
1544   %x13 = add i32 %x4, 1
1545   %x14 = icmp eq i32 %x13, 44
1546   br i1 %x14, label %exit, label %loop
1547 }
1548
1549 ;; Memcpy formation is still preferred over memmove.
1550 define void @prefer_memcpy_over_memmove(ptr noalias %Src, ptr noalias %Dest, i64 %Size) {
1551 ; CHECK-LABEL: @prefer_memcpy_over_memmove(
1552 ; CHECK-NEXT:  bb.nph:
1553 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC:%.*]], i64 42
1554 ; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 1 [[DEST:%.*]], ptr align 1 [[SCEVGEP]], i64 [[SIZE:%.*]], i1 false)
1555 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
1556 ; CHECK:       for.body:
1557 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
1558 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 42
1559 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[STEP]]
1560 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, ptr [[DEST]], i64 [[INDVAR]]
1561 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr [[SRCI]], align 1
1562 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
1563 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
1564 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
1565 ; CHECK:       for.end:
1566 ; CHECK-NEXT:    ret void
1567 ;
1568 bb.nph:
1569   br label %for.body
1570
1571 for.body:                                         ; preds = %bb.nph, %for.body
1572   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
1573   %Step = add nuw nsw i64 %indvar, 42
1574   %SrcI = getelementptr i8, ptr %Src, i64 %Step
1575   %DestI = getelementptr i8, ptr %Dest, i64 %indvar
1576   %V = load i8, ptr %SrcI, align 1
1577   store i8 %V, ptr %DestI, align 1
1578   %indvar.next = add i64 %indvar, 1
1579   %exitcond = icmp eq i64 %indvar.next, %Size
1580   br i1 %exitcond, label %for.end, label %for.body
1581
1582 for.end:                                          ; preds = %for.body, %entry
1583   ret void
1584 }
1585
1586 %class.CMSPULog = type { %struct._opaque_pthread_mutex_t, ptr, i32, i32, i32, i8, i8, i8, [512 x i32] }
1587 %struct._opaque_pthread_mutex_t = type { i64, [56 x i8] }
1588
1589 define noalias ptr @_ZN8CMSPULog9beginImplEja(ptr nocapture writeonly %0) local_unnamed_addr #0 {
1590 ; CHECK-LABEL: @_ZN8CMSPULog9beginImplEja(
1591 ; CHECK-NEXT:    br label [[TMP2:%.*]]
1592 ; CHECK:       2:
1593 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ 0, [[TMP1:%.*]] ], [ [[TMP4:%.*]], [[TMP2]] ]
1594 ; CHECK-NEXT:    [[TMP4]] = add nuw nsw i32 [[TMP3]], 1
1595 ; CHECK-NEXT:    [[TMP5:%.*]] = zext i32 [[TMP3]] to i64
1596 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr [[CLASS_CMSPULOG:%.*]], ptr [[TMP0:%.*]], i64 0, i32 8, i64 [[TMP5]]
1597 ; CHECK-NEXT:    [[AND:%.*]] = and i64 ptrtoint (ptr @G to i64), 16777215
1598 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[AND]] to i32
1599 ; CHECK-NEXT:    store i32 [[TRUNC]], ptr [[TMP6]], align 4
1600 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp ult i32 [[TMP3]], 511
1601 ; CHECK-NEXT:    br i1 [[TMP7]], label [[TMP2]], label [[TMP8:%.*]]
1602 ; CHECK:       8:
1603 ; CHECK-NEXT:    ret ptr null
1604 ;
1605   br label %2
1606
1607 2:                                                ; preds = %1, %2
1608   %3 = phi i32 [ 0, %1 ], [ %4, %2 ]
1609   %4 = add nuw nsw i32 %3, 1
1610   %5 = zext i32 %3 to i64
1611   %6 = getelementptr %class.CMSPULog, ptr %0, i64 0, i32 8, i64 %5
1612   %and = and i64 ptrtoint (ptr @G to i64), 16777215
1613   %trunc = trunc i64 %and to i32
1614   store i32 %trunc, ptr %6, align 4
1615   %7 = icmp ult i32 %3, 511
1616   br i1 %7, label %2, label %8
1617
1618 8:                                                ; preds = %2
1619   ret ptr null
1620 }
1621
1622 ; Validate that "memset_pattern" has the proper attributes.