llvm/test/Analysis/LoopAccessAnalysis/zero-distance-mixed-width.ll

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 6
; RUN: opt -passes='print<access-info>' -disable-output < %s 2>&1 | FileCheck %s

; Mixed-width accesses at zero distance with a common byte stride
; are Forward when different iterations are disjoint.

; Same address, load 4 bytes / store 8 bytes, byte stride 8.
; Different iterations are disjoint --> Forward.
define void @load32_store64_stride8(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 8
  %done = icmp eq i64 %next, 128
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Load 1 byte / store 2 bytes, byte stride 2.
; Smaller access types remain disjoint across iterations --> Forward.
define void @load8_store16_stride2(ptr %base, i8 %before, i16 %after) {
; CHECK-LABEL: 'load8_store16_stride2'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i8, ptr %p, align 1 ->
; CHECK-NEXT:            store i16 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i8, ptr %p, align 1
  %match = icmp eq i8 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i16 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 2
  %done = icmp eq i64 %next, 32
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Load 1 byte / store 8 bytes, byte stride 8.
; Access sizes need not differ by a factor of two --> Forward.
define void @load8_store64_stride8(ptr %base, i8 %before, i64 %after) {
; CHECK-LABEL: 'load8_store64_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i8, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i8, ptr %p, align 1
  %match = icmp eq i8 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 8
  %done = icmp eq i64 %next, 128
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Load i24 (store size 3, allocation size 4) / store i64, byte stride 8.
; Different store and allocation sizes still fit within the stride --> Forward.
define void @load24_store64_stride8(ptr %base, i24 %before, i64 %after) {
; CHECK-LABEL: 'load24_store64_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i24, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i24, ptr %p, align 1
  %match = icmp eq i24 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 8
  %done = icmp eq i64 %next, 128
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Increase the common byte stride from 8 to 16.
; Gaps between iterations do not prevent classification --> Forward.
define void @load32_store64_stride16(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_stride16'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 16
  %done = icmp eq i64 %next, 256
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Reverse the common byte stride from +8 to -8.
; Different iterations remain disjoint --> Forward.
define void @load32_store64_reverse(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_reverse'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 120, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, -8
  %done = icmp eq i64 %next, -8
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Swap the access widths: load 8 bytes / store 4 bytes, byte stride 8.
; The load may be wider than the store --> Forward.
define void @load64_store32_stride8(ptr %base, i64 %before, i32 %after) {
; CHECK-LABEL: 'load64_store32_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i64, ptr %p, align 1 ->
; CHECK-NEXT:            store i32 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i64, ptr %p, align 1
  %match = icmp eq i64 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i32 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 8
  %done = icmp eq i64 %next, 128
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Reverse the access order: store 8 bytes before loading 4 bytes.
; The dependence stays within each iteration --> Forward.
define void @store64_load32_stride8(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'store64_load32_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            store i64 %after, ptr %p, align 1 ->
; CHECK-NEXT:            %value = load i32, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  store i64 %after, ptr %p, align 1
  %value = load i32, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 8
  %done = icmp eq i64 %next, 128
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Store 4 bytes then 8 bytes at equal addresses, with byte stride 8.
; Two writes are also safe across iterations --> Forward.
; Distinct pointer values with equal address expressions ensure that the
; writes reach dependence analysis instead of sharing one access key.
define void @store32_store64_stride8(ptr %base, i32 %first, i64 %second) {
; CHECK-LABEL: 'store32_store64_stride8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            store i32 %first, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %second, ptr %q, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %next, %loop ]
  %p = getelementptr inbounds i64, ptr %base, i64 %index
  %offset = shl nuw nsw i64 %index, 3
  %q = getelementptr inbounds i8, ptr %base, i64 %offset
  store i32 %first, ptr %p, align 1
  store i64 %second, ptr %q, align 1
  %next = add nuw nsw i64 %index, 1
  %done = icmp eq i64 %next, 16
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Let the trip count be a runtime value; keep the common byte stride at 8.
; Independence does not require a constant trip count --> Forward.
define void @load32_store64_dynamic_trip_count(ptr %base, i64 %n, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_dynamic_trip_count'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Memory dependences are safe
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Forward:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  %empty = icmp eq i64 %n, 0
  br i1 %empty, label %exit, label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i64, ptr %base, i64 %index
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nuw i64 %index, 1
  %done = icmp eq i64 %next, %n
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Reduce the byte stride to 4 while retaining the 8-byte store.
; The store overlaps the next iteration's load --> IndirectUnsafe.
; Stride analysis rejects the access before the zero-distance check.
define void @load32_store64_overlap(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_overlap'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
; CHECK-NEXT:  Unsafe indirect dependence.
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        IndirectUnsafe:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 4
  %done = icmp eq i64 %next, 64
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Load 8 bytes / store 4 bytes with byte stride 4.
; The load overlaps the next iteration's store --> IndirectUnsafe.
; Stride analysis rejects the access before the zero-distance check.
define void @load64_store32_overlap(ptr %base, i64 %before, i32 %after) {
; CHECK-LABEL: 'load64_store32_overlap'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
; CHECK-NEXT:  Unsafe indirect dependence.
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        IndirectUnsafe:
; CHECK-NEXT:            %value = load i64, ptr %p, align 1 ->
; CHECK-NEXT:            store i32 %after, ptr %p, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %offset = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i8, ptr %base, i64 %offset
  %value = load i64, ptr %p, align 1
  %match = icmp eq i64 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i32 %after, ptr %p, align 1
  br label %latch

latch:
  %next = add nsw i64 %offset, 4
  %done = icmp eq i64 %next, 64
  br i1 %done, label %exit, label %loop

exit:
  ret void
}

; Keep the common byte stride at 8, but move the store 8 bytes ahead.
; The store overlaps the next iteration's load --> Unknown.
; A common stride alone must not bypass the positive-distance checks.
define void @load32_store64_distance8(ptr %base, i32 %before, i64 %after) {
; CHECK-LABEL: 'load32_store64_distance8'
; CHECK-NEXT:    loop:
; CHECK-NEXT:      Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
; CHECK-NEXT:  Unknown data dependence.
; CHECK-NEXT:      Dependences:
; CHECK-NEXT:        Unknown:
; CHECK-NEXT:            %value = load i32, ptr %p, align 1 ->
; CHECK-NEXT:            store i64 %after, ptr %q, align 1
; CHECK-EMPTY:
; CHECK-NEXT:      Run-time memory checks:
; CHECK-NEXT:      Grouped accesses:
; CHECK-EMPTY:
; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
; CHECK-NEXT:      SCEV assumptions:
; CHECK-EMPTY:
; CHECK-NEXT:      Expressions re-written:
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %next, %latch ]
  %p = getelementptr inbounds i64, ptr %base, i64 %index
  %q = getelementptr inbounds i8, ptr %p, i64 8
  %value = load i32, ptr %p, align 1
  %match = icmp eq i32 %value, %before
  br i1 %match, label %store, label %latch

store:
  store i64 %after, ptr %q, align 1
  br label %latch

latch:
  %next = add nuw nsw i64 %index, 1
  %done = icmp eq i64 %next, 16
  br i1 %done, label %exit, label %loop

exit:
  ret void
}