test/Transforms/LoopInterchange/dependency-matrix-padding.ll

; RUN: opt < %s -passes=loop-interchange -loop-interchange-profitabilities=ignore -debug-only=loop-interchange,da -disable-output 2>&1 | FileCheck %s
; REQUIRES: asserts
;
; This test focuses exclusively on validating the padding logic in the dependency
; matrix construction and ensuring that matrix slicing preserves proper alignment 
; with the corresponding loops.
;
; Corresponding C code:
;
;   for (int i = 0; i < 32; ++i) {
;     for (int j = 0; j < 32; ++j) {
;       int sum = 0;
;       for (int k = 0; k < 32; ++k)
;         sum += k;
;       S[j] = sum + S[j-1]; 
;     }
;     for (int x = 0; x < 32; ++x)
;       D[x] = 0;
;   }
;
; For the first dependency, DA reports the subscript only lives at loop depth 2 (loop.j); confirming
; that loop.i contributes '=' and loop.j contributes the non-trivial '>'.
;
; For the second dependency, Distance 0 at loop.j level gives '=' for both levels (loop.i, loop.j).
; 
; For both dependencies, Dep.size() = 2  after DA fill and before padding
;   L->getLoopDepth() = 2  (loop.j is the outermost loop of the subnest)
;   Level             = 2  (subnest [loop.j, loop.k] has 2 loops)
;   L->getLoopDepth() + Level - 1 = 2 + 2 - 1 = 3
;   2 < 3  =>  padding fires once, appending 'I'
;
;   Dep 1 after padding:  ['=', '>', 'I']  (size 3)
;   Dep 2 after padding:  ['=', '=', 'I']  (size 3)
;
;   The first column of this matrix should be dropped. And the Final Dependecy Matrix before Interchange should be:
;   Dep 1: ['>', 'I'] (Size 2)
;   Dep 2: ['=', 'I'] (Size 3)
;
; CHECK: Found 2 Loads and Stores to analyze
; CHECK: common nesting levels = 2
; CHECK: loops = {2}
; CHECK: Result = anti [S -1|<]!
; CHECK: common nesting levels = 2
; CHECK: loops = {2}
; CHECK: Result = output [S 0]!
; CHECK: Dependency matrix before interchange:
; CHECK-NEXT: > I
; CHECK-NEXT: = I
; CHECK: Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence
;
define void @test_padding_nontrivial_direction(ptr noalias %S, ptr noalias %D) {
entry:
  br label %loop.i.header

loop.i.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %loop.i.latch ]
  br label %loop.j.header

loop.j.header:
  %j     = phi i64 [ 0, %loop.i.header ], [ %j.next, %loop.j.latch ]
  %s.ptr = getelementptr i32, ptr %S, i64 %j
  br label %loop.k.header

loop.k.header:
  %k        = phi i64 [ 0, %loop.j.header ], [ %k.next, %loop.k.latch ]
  %sum      = phi i32 [ 0, %loop.j.header ], [ %sum.next, %loop.k.latch ]
  %k.trunc  = trunc i64 %k to i32
  %sum.next = add nsw i32 %sum, %k.trunc
  br label %loop.k.latch

loop.k.latch:
  %k.next = add nuw nsw i64 %k, 1
  %k.done = icmp eq i64 %k.next, 32
  br i1 %k.done, label %loop.j.latch, label %loop.k.header

loop.j.latch:
  %sum.lcssa = phi i32 [ %sum.next, %loop.k.latch ]
  ; Load S[j-1] — reads what the previous j iteration stored into S[j-1].
  ; This load appears before the store in the same BB, so MemInstr order is
  ; [load, store].  DA tests (load, store) and finds an anti-dependence with
  ; distance -1 at the loop.j level; normalize() flips it to direction '>'.
  ; After padding: ['>', 'I'].  The '>' makes interchange illegal.
  %jm1    = add i64 %j, -1
  %s.prev = getelementptr i32, ptr %S, i64 %jm1
  %s.load = load i32, ptr %s.prev, align 4
  ; Store S[j] = sum + S[j-1].
  %val    = add nsw i32 %sum.lcssa, %s.load
  store i32 %val, ptr %s.ptr, align 4
  %j.next = add nuw nsw i64 %j, 1
  %j.done = icmp eq i64 %j.next, 32
  br i1 %j.done, label %loop.x.header, label %loop.j.header

loop.x.header:
  %x = phi i64 [ 0, %loop.j.latch ], [ %x.next, %loop.x.latch ]
  %d.ptr = getelementptr i8, ptr %D, i64 %x
  store i8 0, ptr %d.ptr, align 1
  br label %loop.x.latch

loop.x.latch:
  %x.next = add nuw nsw i64 %x, 1
  %x.done = icmp eq i64 %x.next, 32
  br i1 %x.done, label %loop.i.latch, label %loop.x.header

loop.i.latch:
  %i.next = add nuw nsw i64 %i, 1
  %i.done = icmp eq i64 %i.next, 32
  br i1 %i.done, label %exit, label %loop.i.header

exit:
  ret void
}