From 4de3184f07fd8c548125d315dd306d4afa7c9698 Mon Sep 17 00:00:00 2001
From: Nikita Popov <npopov@redhat.com>
Date: Mon, 14 Nov 2022 16:13:51 +0100
Subject: [PATCH] [LAA] Use cross-iteration alias analysis

LAA analyzes cross-iteration memory dependencies, as such AA should
not make assumptions about equality of values inside the loop, as
they may come from different iterations.

Fix this by exposing the MayBeCrossIteration AA flag and enabling
it for LAA.

Differential Revision: https://reviews.llvm.org/D137958
---
 llvm/include/llvm/Analysis/AliasAnalysis.h         |  5 ++++
 llvm/lib/Analysis/LoopAccessAnalysis.cpp           |  5 +++-
 .../LoopAccessAnalysis/select-dependence.ll        | 30 ++++++++++++++++++++++
 3 files changed, 39 insertions(+), 1 deletion(-)
 create mode 100644 llvm/test/Analysis/LoopAccessAnalysis/select-dependence.ll

diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h
index c50cb2d..99d10cb 100644
--- a/llvm/include/llvm/Analysis/AliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/AliasAnalysis.h
@@ -651,6 +651,11 @@ public:
                                 DominatorTree *DT) {
     return AA.callCapturesBefore(I, MemLoc, DT, AAQI);
   }
+
+  /// Assume that values may come from different cycle iterations.
+  void enableCrossIterationMode() {
+    AAQI.MayBeCrossIteration = true;
+  }
 };
 
 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 1bc2f6b..4e68856 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -622,7 +622,10 @@ public:
   AccessAnalysis(Loop *TheLoop, AAResults *AA, LoopInfo *LI,
                  MemoryDepChecker::DepCandidates &DA,
                  PredicatedScalarEvolution &PSE)
-      : TheLoop(TheLoop), BAA(*AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE) {}
+      : TheLoop(TheLoop), BAA(*AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE) {
+    // We're analyzing dependences across loop iterations.
+    BAA.enableCrossIterationMode();
+  }
 
   /// Register a load  and whether it is only read from.
   void addLoad(MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly) {
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/select-dependence.ll b/llvm/test/Analysis/LoopAccessAnalysis/select-dependence.ll
new file mode 100644
index 0000000..07e32f4
--- /dev/null
+++ b/llvm/test/Analysis/LoopAccessAnalysis/select-dependence.ll
@@ -0,0 +1,30 @@
+; RUN: opt -passes='print<access-info>' -disable-output 2>&1 < %s | FileCheck %s
+
+; CHECK: Dependences:
+; CHECK-NEXT: Unknown:
+; CHECK-NEXT: %t63 = load double, ptr %t62, align 8 ->
+; CHECK-NEXT: store double %t63, ptr %t64, align 8
+
+define i32 @test() {
+   %a1 = alloca [128 x double], align 8
+   %a2 = alloca [128 x double], align 8
+   %a3 = alloca [128 x double], align 8
+   %t30 = getelementptr double, ptr %a2, i64 -32
+   br label %loop
+
+loop:
+   %t58 = phi i64 [ %t65, %loop ], [ 0, %0 ]
+   %t59 = icmp ule i64 %t58, 32
+   %t60 = select i1 %t59, ptr %a1, ptr %t30
+   %t62 = getelementptr inbounds double, ptr %t60, i64 %t58
+   %t63 = load double, ptr %t62, align 8
+   %t61 = select i1 %t59, ptr %a2, ptr %a3
+   %t64 = getelementptr inbounds double, ptr %t61, i64 %t58
+   store double %t63, ptr %t64, align 8
+   %t65 = add nuw nsw i64 %t58, 1
+   %t66 = icmp eq i64 %t65, 94
+   br i1 %t66, label %exit, label %loop
+
+exit:
+   ret i32 0
+}
-- 
2.7.4