[LoopInterchange][PR56275] Fix legality in dependence vectors

[congzhe]

Summary

This is the 2nd patch of the two-patch series that fix PR56275 (https://github.com/llvm/llvm-project/issues/56275): D130188 D130189.

Following up on the dependence analysis (DA) patch D130188, in this patch we query DA with NeedsNormalize=true in loop interchange, such that the DA results queried by loop interchange are normalized. With a minor fix w.r.t. how loop interchange interpret dependence distances, all tests in PR56275 can get interchanged.

I've added the tests in PR56275 in lit test pr56275.ll for more details.

[kawashima-fj]

Thanks @congzhe . LGTM.

[Meinersbur]

As mentioned in https://github.com/llvm/llvm-project/issues/56275#issuecomment-1183363002, I think both directions need to be considered. < or > of the Dependence object mingels relation between the Src/Dst argument. Here, it is interpreted as the direction of the loop.

However, with normalizing this could be correct, but only when we bail out with any bidirectional dependencies. See my inline comment. Such subtly should be worth a source comment somewhere.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

140–141

[serious] A SCEV can be neither isPositive(), isZero(), nor isNegative(). This is for instance that case when it depend on a variable which can be either one of them at runtime. This code implicitly assumes that such a distance is "negative". It should be '*'.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

140–141

Thanks for the comment. Thinking about this piece of code more carefully, I think the entire if (SCEVConst) block can be deleted. This code block is merely a subset of the the else block where we could just leverage Dir = D->getDirection(II) to construct Dep. Another benefit is that the else block explicitly addresses your concern - if the direction is bidirectional, it would be a "*".

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

132

Before I can accept the patch, I would like to see D130188 to treat a Dependence object as immutable (modifying global state is incompatible with pass manager analysis caching)

140–141

I think you are correct. If the distance is positive/negative, the direction be </> anyway.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

132

Thanks for the comment, I've updated D130188 such that Dependence::normalize() does not change this object but just returns a new Depenence object.

[congzhe]

Updated the patch according to the most recent update in D130188

[Meinersbur]

LGTM, thank you

[congzhe]

Updated to take the bool return value of normalize() into account, will land soon.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

for (auto &Row : DepMatrix) {
     for (auto D : Row)
       LLVM_DEBUG(dbgs() << D << " ");
     LLVM_DEBUG(dbgs() << "\n");
   }
 }
 #endif
 
 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
-                                     Loop *L, DependenceInfo *DI) {
+                                     Loop *L, DependenceInfo *DI,
+                                     ScalarEvolution *SE) {
   using ValueVector = SmallVector<Value *, 16>;
 
   ValueVector MemInstr;
 
   // For each block.
   for (BasicBlock *BB : L->blocks()) {
     // Scan the BB and collect legal loads and stores.
     for (Instruction &I : *BB) {
for (J = I, JE = MemInstr.end(); J != JE; ++J) {
       Instruction *Src = cast<Instruction>(*I);
       Instruction *Dst = cast<Instruction>(*J);
       // Ignore Input dependencies.
       if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
         continue;
       // Track Output, Flow, and Anti dependencies.
       if (auto D = DI->depends(Src, Dst, true)) {
         assert(D->isOrdered() && "Expected an output, flow or anti dep.");
+        // If the direction vector is negative, normalize it to
+        // make it non-negative.
+        if (D->normalize(SE))
+          LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
         LLVM_DEBUG(StringRef DepType =
                        D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
                    dbgs() << "Found " << DepType
                           << " dependency between Src and Dst\n"
                           << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
         unsigned Levels = D->getLevels();
         char Direction;
         for (unsigned II = 1; II <= Levels; ++II) {
-          const SCEV *Distance = D->getDistance(II);
-          const SCEVConstant *SCEVConst =
-              dyn_cast_or_null<SCEVConstant>(Distance);
-          if (SCEVConst) {
-            const ConstantInt *CI = SCEVConst->getValue();
-            if (CI->isNegative())
-              Direction = '<';
-            else if (CI->isZero())
-              Direction = '=';
-            else
-              Direction = '>';
-            Dep.push_back(Direction);
-          } else if (D->isScalar(II)) {
+          if (D->isScalar(II)) {
             Direction = 'S';
             Dep.push_back(Direction);
           } else {
             unsigned Dir = D->getDirection(II);
             if (Dir == Dependence::DVEntry::LT ||
                 Dir == Dependence::DVEntry::LE)
               Direction = '<';
             else if (Dir == Dependence::DVEntry::GT ||
bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
     }
 
     LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
                       << "\n");
 
     CharMatrix DependencyMatrix;
     Loop *OuterMostLoop = *(LoopList.begin());
     if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
-                                  OuterMostLoop, DI)) {
+                                  OuterMostLoop, DI, SE)) {
       LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
       return false;
     }
 #ifdef DUMP_DEP_MATRICIES
     LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
     printDepMatrix(DependencyMatrix);
 #endif
 

llvm/test/Transforms/LoopInterchange/pr56275.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -aa-pipeline=basic-aa -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+;; Test to make sure DA outputs the correction direction
+;; vector [< =] hence the loopnest is interchanged.
+;;
+;; void test1(unsigned a[restrict N1][N2],
+;;          unsigned b[restrict N1][N2],
+;;          unsigned c[restrict N1][N2]) {
+;;  for (unsigned long i2 = 1; i2 < N2-1; i2++) {
+;;    for (unsigned long i1 = 1; i1 < N1-1; i1++) {
+;;      a[i1][i2+1] = b[i1][i2];
+;;      c[i1][i2] = a[i1][i2];
+;;    }
+;;  }
+;; }
+
+define void @test1(ptr noalias noundef %a, ptr noalias noundef %b, ptr noalias noundef %c) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP2_HEADER_PREHEADER:%.*]]
+; CHECK:       loop1.header.preheader:
+; CHECK-NEXT:    br label [[LOOP1_HEADER:%.*]]
+; CHECK:       loop1.header:
+; CHECK-NEXT:    [[I2:%.*]] = phi i64 [ [[I2_INC:%.*]], [[LOOP1_LATCH:%.*]] ], [ 1, [[LOOP1_HEADER_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[I2_ST:%.*]] = add i64 [[I2]], 1
+; CHECK-NEXT:    [[I2_LD:%.*]] = add i64 [[I2]], 0
+; CHECK-NEXT:    br label [[LOOP2_HEADER_SPLIT1:%.*]]
+; CHECK:       loop2.header.preheader:
+; CHECK-NEXT:    br label [[LOOP2_HEADER:%.*]]
+; CHECK:       loop2.header:
+; CHECK-NEXT:    [[I1:%.*]] = phi i64 [ [[TMP0:%.*]], [[LOOP2_HEADER_SPLIT:%.*]] ], [ 1, [[LOOP2_HEADER_PREHEADER]] ]
+; CHECK-NEXT:    br label [[LOOP1_HEADER_PREHEADER]]
+; CHECK:       loop2.header.split1:
+; CHECK-NEXT:    [[I1_ST:%.*]] = add i64 [[I1]], 0
+; CHECK-NEXT:    [[I1_LD:%.*]] = add i64 [[I1]], 0
+; CHECK-NEXT:    [[A_ST:%.*]] = getelementptr inbounds [64 x i32], ptr [[A:%.*]], i64 [[I1_ST]], i64 [[I2_ST]]
+; CHECK-NEXT:    [[A_LD:%.*]] = getelementptr inbounds [64 x i32], ptr [[A]], i64 [[I1_LD]], i64 [[I2_LD]]
+; CHECK-NEXT:    [[B_LD:%.*]] = getelementptr inbounds [64 x i32], ptr [[B:%.*]], i64 [[I1]], i64 [[I2]]
+; CHECK-NEXT:    [[C_ST:%.*]] = getelementptr inbounds [64 x i32], ptr [[C:%.*]], i64 [[I1]], i64 [[I2]]
+; CHECK-NEXT:    [[B_VAL:%.*]] = load i32, ptr [[B_LD]], align 4
+; CHECK-NEXT:    store i32 [[B_VAL]], ptr [[A_ST]], align 4
+; CHECK-NEXT:    [[A_VAL:%.*]] = load i32, ptr [[A_LD]], align 4
+; CHECK-NEXT:    store i32 [[A_VAL]], ptr [[C_ST]], align 4
+; CHECK-NEXT:    [[I1_INC:%.*]] = add nuw nsw i64 [[I1]], 1
+; CHECK-NEXT:    [[LOOP2_EXITCOND_NOT:%.*]] = icmp eq i64 [[I1_INC]], 63
+; CHECK-NEXT:    br label [[LOOP1_LATCH]]
+; CHECK:       loop2.header.split:
+; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[I1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 63
+; CHECK-NEXT:    br i1 [[TMP1]], label [[EXIT:%.*]], label [[LOOP2_HEADER]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    [[I2_INC]] = add nuw nsw i64 [[I2]], 1
+; CHECK-NEXT:    [[LOOP1_EXITCOND_NOT:%.*]] = icmp eq i64 [[I2_INC]], 63
+; CHECK-NEXT:    br i1 [[LOOP1_EXITCOND_NOT]], label [[LOOP2_HEADER_SPLIT]], label [[LOOP1_HEADER]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop1.header
+
+loop1.header:
+  %i2 = phi i64 [ 1, %entry ], [ %i2.inc, %loop1.latch ]
+  %i2.st = add i64 %i2, 1
+  %i2.ld = add i64 %i2, 0
+  br label %loop2.header
+
+loop2.header:
+  %i1 = phi i64 [ 1, %loop1.header ], [ %i1.inc, %loop2.header ]
+  %i1.st = add i64 %i1, 0
+  %i1.ld = add i64 %i1, 0
+  %a.st = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.st, i64 %i2.st
+  %a.ld = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.ld, i64 %i2.ld
+  %b.ld = getelementptr inbounds [64 x i32], ptr %b, i64 %i1, i64 %i2
+  %c.st = getelementptr inbounds [64 x i32], ptr %c, i64 %i1, i64 %i2
+  %b.val = load i32, ptr %b.ld, align 4
+  store i32 %b.val, ptr %a.st, align 4  ; (X) store to a[i1][i2+1]
+  %a.val = load i32, ptr %a.ld, align 4 ; (Y) load from a[i1][i2]
+  store i32 %a.val, ptr %c.st, align 4
+  %i1.inc = add nuw nsw i64 %i1, 1
+  %loop2.exitcond.not = icmp eq i64 %i1.inc, 63
+  br i1 %loop2.exitcond.not, label %loop1.latch, label %loop2.header
+
+loop1.latch:
+  %i2.inc = add nuw nsw i64 %i2, 1
+  %loop1.exitcond.not = icmp eq i64 %i2.inc, 63
+  br i1 %loop1.exitcond.not, label %exit, label %loop1.header
+
+exit:
+  ret void
+}
+
+;; Semantically equivalent to test1() with only the difference
+;; of the order of a load and a store at (X) and (Y).
+;;
+;; Test to make sure DA outputs the correction direction
+;; vector [< =] hence the loopnest is interchanged.
+
+define void @test2(ptr noalias noundef %a, ptr noalias noundef %b, ptr noalias noundef %c) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP2_HEADER_PREHEADER:%.*]]
+; CHECK:       loop1.header.preheader:
+; CHECK-NEXT:    br label [[LOOP1_HEADER:%.*]]
+; CHECK:       loop1.header:
+; CHECK-NEXT:    [[I2:%.*]] = phi i64 [ [[I2_INC:%.*]], [[LOOP1_LATCH:%.*]] ], [ 1, [[LOOP1_HEADER_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[I2_ST:%.*]] = add i64 [[I2]], 1
+; CHECK-NEXT:    [[I2_LD:%.*]] = add i64 [[I2]], 0
+; CHECK-NEXT:    br label [[LOOP2_HEADER_SPLIT1:%.*]]
+; CHECK:       loop2.header.preheader:
+; CHECK-NEXT:    br label [[LOOP2_HEADER:%.*]]
+; CHECK:       loop2.header:
+; CHECK-NEXT:    [[I1:%.*]] = phi i64 [ [[TMP0:%.*]], [[LOOP2_HEADER_SPLIT:%.*]] ], [ 1, [[LOOP2_HEADER_PREHEADER]] ]
+; CHECK-NEXT:    br label [[LOOP1_HEADER_PREHEADER]]
+; CHECK:       loop2.header.split1:
+; CHECK-NEXT:    [[I1_ST:%.*]] = add i64 [[I1]], 0
+; CHECK-NEXT:    [[I1_LD:%.*]] = add i64 [[I1]], 0
+; CHECK-NEXT:    [[A_ST:%.*]] = getelementptr inbounds [64 x i32], ptr [[A:%.*]], i64 [[I1_ST]], i64 [[I2_ST]]
+; CHECK-NEXT:    [[A_LD:%.*]] = getelementptr inbounds [64 x i32], ptr [[A]], i64 [[I1_LD]], i64 [[I2_LD]]
+; CHECK-NEXT:    [[B_LD:%.*]] = getelementptr inbounds [64 x i32], ptr [[B:%.*]], i64 [[I1]], i64 [[I2]]
+; CHECK-NEXT:    [[C_ST:%.*]] = getelementptr inbounds [64 x i32], ptr [[C:%.*]], i64 [[I1]], i64 [[I2]]
+; CHECK-NEXT:    [[B_VAL:%.*]] = load i32, ptr [[B_LD]], align 4
+; CHECK-NEXT:    [[A_VAL:%.*]] = load i32, ptr [[A_LD]], align 4
+; CHECK-NEXT:    store i32 [[B_VAL]], ptr [[A_ST]], align 4
+; CHECK-NEXT:    store i32 [[A_VAL]], ptr [[C_ST]], align 4
+; CHECK-NEXT:    [[I1_INC:%.*]] = add nuw nsw i64 [[I1]], 1
+; CHECK-NEXT:    [[LOOP2_EXITCOND_NOT:%.*]] = icmp eq i64 [[I1_INC]], 63
+; CHECK-NEXT:    br label [[LOOP1_LATCH]]
+; CHECK:       loop2.header.split:
+; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[I1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 63
+; CHECK-NEXT:    br i1 [[TMP1]], label [[EXIT:%.*]], label [[LOOP2_HEADER]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    [[I2_INC]] = add nuw nsw i64 [[I2]], 1
+; CHECK-NEXT:    [[LOOP1_EXITCOND_NOT:%.*]] = icmp eq i64 [[I2_INC]], 63
+; CHECK-NEXT:    br i1 [[LOOP1_EXITCOND_NOT]], label [[LOOP2_HEADER_SPLIT]], label [[LOOP1_HEADER]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop1.header
+
+loop1.header:
+  %i2 = phi i64 [ 1, %entry ], [ %i2.inc, %loop1.latch ]
+  %i2.st = add i64 %i2, 1
+  %i2.ld = add i64 %i2, 0
+  br label %loop2.header
+
+loop2.header:
+  %i1 = phi i64 [ 1, %loop1.header ], [ %i1.inc, %loop2.header ]
+  %i1.st = add i64 %i1, 0
+  %i1.ld = add i64 %i1, 0
+  %a.st = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.st, i64 %i2.st
+  %a.ld = getelementptr inbounds [64 x i32], ptr %a, i64 %i1.ld, i64 %i2.ld
+  %b.ld = getelementptr inbounds [64 x i32], ptr %b, i64 %i1, i64 %i2
+  %c.st = getelementptr inbounds [64 x i32], ptr %c, i64 %i1, i64 %i2
+  %b.val = load i32, ptr %b.ld, align 4
+  %a.val = load i32, ptr %a.ld, align 4 ; (Y) load from a[i1][i2]
+  store i32 %b.val, ptr %a.st, align 4  ; (X) store to a[i1][i2+1]
+  store i32 %a.val, ptr %c.st, align 4
+  %i1.inc = add nuw nsw i64 %i1, 1
+  %loop2.exitcond.not = icmp eq i64 %i1.inc, 63
+  br i1 %loop2.exitcond.not, label %loop1.latch, label %loop2.header
+
+loop1.latch:
+  %i2.inc = add nuw nsw i64 %i2, 1
+  %loop1.exitcond.not = icmp eq i64 %i2.inc, 63
+  br i1 %loop1.exitcond.not, label %exit, label %loop1.header
+
+exit:
+  ret void
+}