[DA] Handle mismatching loop levels by updating the numbering scheme

[bmahjour]

Summary

To represent various loop levels within a nest, DA implements a special numbering scheme (see comment atop establishNestingLevels). The goal of this numbering scheme appears to be representing each unique loop distinctively by using as little memory as possible. This numbering scheme is simple when the source and destination of the dependence are in the same loop. In such cases the level is simply the depth of the loop in which src and dst reside. When the src and dst are not in the same loop, we could run into the following situation exposed by https://reviews.llvm.org/D71539.

Suppose we have the following loop structure and memory access:

1: L1
2:    L2
3:    A[s1] 
4:    L3
5:      A[s2]

Further assume that the subscript of the first access (ie s1) is an LCSSA phi with a single incoming value from L2. With the change in D71539, the SCEV expression for s1 (queried at the scope of L1 where the access on line 3 occurs) will be an AddRec whose loop is L2.

Since the access A[s1] occurs at a loop depth of 1, but its subscript references a loop at depth 2, the current numbering scheme gets confused and assigns the same level value to both s1 and s2, which further causes classifyPair to incorrectly classify the subscript pair. In an assert enabled build, this would trigger the following assertion:

bool llvm::DependenceInfo::testSIV(const llvm::SCEV *, const llvm::SCEV *, unsigned int &, llvm::FullDependence &, llvm::DependenceInfo::Constraint &, const llvm::SCEV *&) const: Assertion `CurLoop == DstAddRec->getLoop() && "both loops in SIV should be same"' failed.

This patch proposes a slight change to the numbering scheme using the subscript SCEVs to treat the memory access instructions in such cases, as if they appeared inside the AddRec loop of the inner-most subscript.

An alternative fix can be reviewed in D110973.

[Meinersbur]

The test fails for me when applying the patch. Is D71539 supposed to be a parent patch?

Is the loop nest in the example supposed to look like this?

for (L1) {
  for (L2) {
    s1 = ...;
  }
  A[s1]; // getScev(s1) = SCEVAddRecExp<L1,...>
  for (L3) {
    A[s2];
  }
}

The problem seems to be that DA assumes that s1 depends on the induction variable of L1, even though the access is located outside of it. getSCEVAtScope may resolve it to a computed value, but may not if it does not understand the exit condition. In checkSubscript this is handled by calling isLoopInvariant first. However, the loop-invariance is only checked if there is no SCEVAddRecExpr. Might the problem be that an SCEVAddRecExpr may actually be loop-invariant, if evaluated outside the loop's scope?

llvm/lib/Analysis/DependenceAnalysis.cpp

3590

Consider removing unrelated changes from this patch.

3615

Is there a reason this is moved?

llvm/test/Analysis/DependenceAnalysis/MismatchingNestLevels.ll

11

Could you add some pseudocode helping to understand the case?

24

It would be better to not rely on undef in test cases. Handling of undef can change, depending on what an analysis thinks runs faster.

[Meinersbur]

I was able to reproduce the problem without D71539:

$ cat da-lcssa.c
void foobar(long n, double *A) {
    long  i;
    for (i = 0; i*n <= n*n; ++i) {
        A[i] = i;
    }
    A[i] = i;
}

$ cat da-lcssa.ll
; ModuleID = 'da-lcssa.c'
source_filename = "da-lcssa.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: argmemonly nofree norecurse nosync nounwind writeonly uwtable
define dso_local void @foobar(i64 noundef %n, ptr nocapture noundef writeonly %A) local_unnamed_addr #0 {
entry:
  %mul1 = mul nsw i64 %n, %n
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %i.012 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
  %conv = sitofp i64 %i.012 to double
  %arrayidx = getelementptr inbounds double, ptr %A, i64 %i.012
  store double %conv, ptr %arrayidx, align 8, !tbaa !3
  %inc = add nuw nsw i64 %i.012, 1
  %mul = mul nsw i64 %inc, %n
  %cmp.not = icmp sgt i64 %mul, %mul1
  br i1 %cmp.not, label %for.end, label %for.body, !llvm.loop !7

for.end:                                          ; preds = %for.body
  %conv2 = sitofp i64 %inc to double
  %arrayidx3 = getelementptr inbounds double, ptr %A, i64 %inc
  store double %conv2, ptr %arrayidx3, align 8, !tbaa !3
  ret void
}

attributes #0 = { argmemonly nofree norecurse nosync nounwind writeonly uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 7, !"uwtable", i32 2}
!2 = !{!"clang version 15.0.0 (/home/meinersbur/src/llvm-project/clang 2d92ee97f1afb3657579a46a7dd4611b61e9cc16)"}
!3 = !{!4, !4, i64 0}
!4 = !{!"double", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = distinct !{!7, !8, !9}
!8 = !{!"llvm.loop.mustprogress"}
!9 = !{!"llvm.loop.unroll.disable"}


$ opt da-lcssa.ll -disable-output "-passes=print<da>" -aa-pipeline=basic-aa
'Dependence Analysis' for function 'foobar':
Src:  store double %conv, ptr %arrayidx, align 8, !tbaa !3 --> Dst:  store double %conv, ptr %arrayidx, align 8, !tbaa !3
  da analyze - none!
Src:  store double %conv, ptr %arrayidx, align 8, !tbaa !3 --> Dst:  store double %conv2, ptr %arrayidx3, align 8, !tbaa !3
  da analyze - opt: /home/meinersbur/src/llvm-project/llvm/lib/Analysis/DependenceAnalysis.cpp:1160: bool llvm::DependenceInfo::strongSIVtest(const llvm::SCEV*, const llvm::SCEV*, const llvm::SCEV*, const llvm::Loop*, unsigned int, llvm::FullDependence&, llvm::DependenceInfo::Constraint&) const: Assertion `0 < Level && Level <= CommonLevels && "level out of range"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /home/meinersbur/build/llvm-project/release/bin/opt da-lcssa.ll -disable-output -passes=print<da> -aa-pipeline=basic-aa
 #0 0x00007fa14c381f14 PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x00007fa14c37f6b4 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007fa1492303c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x143c0)
 #3 0x00007fa148c9303b raise /build/glibc-sMfBJT/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #4 0x00007fa148c72859 abort /build/glibc-sMfBJT/glibc-2.31/stdlib/abort.c:81:7
 #5 0x00007fa148c72729 get_sysdep_segment_value /build/glibc-sMfBJT/glibc-2.31/intl/loadmsgcat.c:509:8
 #6 0x00007fa148c72729 _nl_load_domain /build/glibc-sMfBJT/glibc-2.31/intl/loadmsgcat.c:970:34
 #7 0x00007fa148c84006 (/lib/x86_64-linux-gnu/libc.so.6+0x34006)
 #8 0x00007fa14af1201c llvm::DependenceInfo::strongSIVtest(llvm::SCEV const*, llvm::SCEV const*, llvm::SCEV const*, llvm::Loop const*, unsigned int, llvm::FullDependence&, llvm::DependenceInfo::Constraint&) const (/home/meinersbur/build/llvm-project/release/bin/opt+0x1c8201c)
 #9 0x00007fa14af1eb6a llvm::DependenceInfo::testSIV(llvm::SCEV const*, llvm::SCEV const*, unsigned int&, llvm::FullDependence&, llvm::DependenceInfo::Constraint&, llvm::SCEV const*&) const (.constprop.0) DependenceAnalysis.cpp:0:0
#10 0x00007fa14af23eb8 llvm::DependenceInfo::depends(llvm::Instruction*, llvm::Instruction*, bool) (/home/meinersbur/build/llvm-project/release/bin/opt+0x1c93eb8)
#11 0x00007fa14af255bd dumpExampleDependence(llvm::raw_ostream&, llvm::DependenceInfo*) DependenceAnalysis.cpp:0:0
#12 0x00007fa14af25a76 llvm::DependenceAnalysisPrinterPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/meinersbur/build/llvm-project/release/bin/opt+0x1c95a76)
#13 0x00007fa14c6adad6 llvm::detail::PassModel<llvm::Function, llvm::DependenceAnalysisPrinterPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#14 0x00007fa14b99f766 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/meinersbur/build/llvm-project/release/bin/opt+0x270f766)
#15 0x00007fa14ad5f936 llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) NVPTXTargetMachine.cpp:0:0
#16 0x00007fa14b99e179 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/meinersbur/build/llvm-project/release/bin/opt+0x270e179)
#17 0x00007fa14ad5fdc6 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) NVPTXTargetMachine.cpp:0:0
#18 0x00007fa14b99bc6f llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/meinersbur/build/llvm-project/release/bin/opt+0x270bc6f)
#19 0x00007fa14a9a7787 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool) (/home/meinersbur/build/llvm-project/release/bin/opt+0x1717787)
#20 0x00007fa14a9baa2c main (/home/meinersbur/build/llvm-project/release/bin/opt+0x172aa2c)
#21 0x00007fa148c740b3 __libc_start_main /build/glibc-sMfBJT/glibc-2.31/csu/../csu/libc-start.c:342:3
#22 0x00007fa14a99948e _start (/home/meinersbur/build/llvm-project/release/bin/opt+0x170948e)
Aborted (core dumped)

[congzhe]

llvm/lib/Analysis/DependenceAnalysis.cpp

752

Would it be better to pass Pairs by reference?

And rename Pairs to Pair (since Pairs is used as an integer elsewhere)?

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

752

Even better: Pass ArrayRef<Subscript>

[Meinersbur]

I think the correct fix is to handle AddRecExpr from a loop outside LoopNest like other non-AddRec expressions. At the moment this means "non-linear" (like D110973) unless it is completely loop-invariant. This is a limitation of the current checkSubscript that does not look into other kinds of SCEV expressions. In @test1/@test2 this is all we can do because %c.1.lcssa (which has the value of %add27 when the loop exists) has an undefined value because with the backedge branch on undef, %c.1.lcssa is undefined which usually is not considered "linear".

DependenceInfo::depends should actually call getSCEVAtScope instead of just getScev (like tryDelinearize already does), because if ScalarEvolution can understand the backedge taken count, the SCEVAddRecExpr will be simplified to that result.

[congzhe]

In D110972#3463438, @Meinersbur wrote:

I think the correct fix is to handle AddRecExpr from a loop outside LoopNest like other non-AddRec expressions. At the moment this means "non-linear" (like D110973) unless it is completely loop-invariant. This is a limitation of the current checkSubscript that does not look into other kinds of SCEV expressions. In @test1/@test2 this is all we can do because %c.1.lcssa (which has the value of %add27 when the loop exists) has an undefined value because with the backedge branch on undef, %c.1.lcssa is undefined which usually is not considered "linear".

DependenceInfo::depends should actually call getSCEVAtScope instead of just getScev (like tryDelinearize already does), because if ScalarEvolution can understand the backedge taken count, the SCEVAddRecExpr will be simplified to that result.

Are you essentially suggesting that we follow the approach in D110973, and improve it by using getSCEVAtScope() such that we may be able to infer some of those AddRec (like in the lcssa case) to be loop invariant with respect to LoopNest? If that is the case then we may want to add another test that is a mirror of @test1 but not using undef as the loop exit condition?

[Meinersbur]

In D110972#3463979, @congzhe wrote:

Are you essentially suggesting that we follow the approach in D110973, and improve it by using getSCEVAtScope() such that we may be able to infer some of those AddRec (like in the lcssa case) to be loop invariant with respect to LoopNest?

yes. ScalarEvolution::computeLoopDisposition() == LoopInvariant might be the designated API for this.

If that is the case then we may want to add another test that is a mirror of @test1 but not using undef as the loop exit condition?

We preferably do not want undef at all in test cases, it makes them fragile.

[bmahjour]

@Meinersbur Thanks for the test case that fails without D71539. The test case I reported was bugpoint reduced and that's why the undefs are there. I'll update D110973 with a test that doesn't use undef and that passes today but would fail with D71539. I'll also add your test to it.

As for treating the case as non-linear, I'd be fine with that. I'll update D110973 to use SCEV LoopDisposition.

llvm/include/llvm/Analysis/DependenceAnalysis.h

private:
     /// A map from loop names to level indices would look like
     ///     a - 1
     ///     b - 2 = CommonLevels
     ///     c - 3
     ///     d - 4 = SrcLevels
     ///     e - 5
     ///     f - 6
     ///     g - 7 = MaxLevels
-    void establishNestingLevels(const Instruction *Src,
-                                const Instruction *Dst);
+    void establishNestingLevels(const Instruction *Src, const Instruction *Dst,
+                                const SmallVector<Subscript> Pairs);
 
     unsigned CommonLevels, SrcLevels, MaxLevels;
 
     /// mapSrcLoop - Given one of the loops containing the source, return
     /// its level index in our numbering scheme.
     unsigned mapSrcLoop(const Loop *SrcLoop) const;
 
     /// mapDstLoop - Given one of the loops containing the destination,

llvm/lib/Analysis/DependenceAnalysis.cpp

 // A map from loop names to loop numbers would look like
 //     a - 1
 //     b - 2 = CommonLevels
 //     c - 3
 //     d - 4 = SrcLevels
 //     e - 5
 //     f - 6
 //     g - 7 = MaxLevels
-void DependenceInfo::establishNestingLevels(const Instruction *Src,
-                                            const Instruction *Dst) {
+void DependenceInfo::establishNestingLevels(
+    const Instruction *Src, const Instruction *Dst,
+    const SmallVector<Subscript> Pairs) {
   const BasicBlock *SrcBlock = Src->getParent();
   const BasicBlock *DstBlock = Dst->getParent();
   unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
   unsigned DstLevel = LI->getLoopDepth(DstBlock);
   const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
   const Loop *DstLoop = LI->getLoopFor(DstBlock);
   SrcLevels = SrcLevel;
+  // If any of the subscripts for an instruction have a recurrence with a loop
+  // level that does not contain that instruction, we need to update the
+  // corresponding level number, to ensure a distinct loop is assigned. This
+  // effectively treats the instruction as if it was present inside the
+  // recurrence's loop. This is conservatively correct, since it may only cause
+  // more constraints to be propaged to the common levels.
+  if (SrcLoop != DstLoop) {
+    const SCEV *InnerMostSrcExpr = Pairs[Pairs.size() - 1].Src;
+    const SCEV *InnerMostDstExpr = Pairs[Pairs.size() - 1].Dst;
+    const SCEVAddRecExpr *SrcAddRec =
+        dyn_cast_or_null<SCEVAddRecExpr>(InnerMostSrcExpr);
+    const SCEVAddRecExpr *DstAddRec =
+        dyn_cast_or_null<SCEVAddRecExpr>(InnerMostDstExpr);
+    if (SrcAddRec && mapSrcLoop(SrcAddRec->getLoop()) > SrcLevel) {
+      SrcLoop = SrcAddRec->getLoop();
+      SrcLevels = LI->getLoopDepth(SrcLoop->getHeader());
+      SrcLevel = SrcLevels;
+    }
+    if (DstAddRec && mapDstLoop(DstAddRec->getLoop()) > DstLevel) {
+      DstLoop = DstAddRec->getLoop();
+      DstLevel = LI->getLoopDepth(DstLoop->getHeader());
+    }
+  }
+
   MaxLevels = SrcLevel + DstLevel;
   while (SrcLevel > DstLevel) {
     SrcLoop = SrcLoop->getParentLoop();
     SrcLevel--;
   }
   while (DstLevel > SrcLevel) {
     DstLoop = DstLoop->getParentLoop();
     DstLevel--;
   }
   while (SrcLoop != DstLoop) {
     SrcLoop = SrcLoop->getParentLoop();
     DstLoop = DstLoop->getParentLoop();
     SrcLevel--;
   }
   CommonLevels = SrcLevel;
   MaxLevels -= CommonLevels;
 }
 
-
 // Given one of the loops containing the source, return
 // its level index in our numbering scheme.
 unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
   return SrcLoop->getLoopDepth();
 }
 
 
 // Given one of the loops containing the destination,
 // return its level index in our numbering scheme.
 unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
   unsigned D = DstLoop->getLoopDepth();
   if (D > CommonLevels)
+    // This tries to make sure that we assign unique numbers to src and dst when
+    // the memory accesses reside in different loops that have the same depth.
     return D - CommonLevels + SrcLevels;
   else
     return D;
 }
 
 
 // Returns true if Expression is loop invariant in LoopNest.
 bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   case AliasResult::NoAlias:
     // If the objects noalias, they are distinct, accesses are independent.
     LLVM_DEBUG(dbgs() << "no alias\n");
     return nullptr;
   case AliasResult::MustAlias:
     break; // The underlying objects alias; test accesses for dependence.
   }
 
-  // establish loop nesting levels
-  establishNestingLevels(Src, Dst);
-  LLVM_DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
-  LLVM_DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");
-
-  FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
   ++TotalArrayPairs;
 
   unsigned Pairs = 1;
-  SmallVector<Subscript, 2> Pair(Pairs);
+  SmallVector<Subscript> Pair(Pairs);
   const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
   const SCEV *DstSCEV = SE->getSCEV(DstPtr);
   LLVM_DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
   LLVM_DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
   if (SE->getPointerBase(SrcSCEV) != SE->getPointerBase(DstSCEV)) {
     // If two pointers have different bases, trying to analyze indexes won't
     // work; we can't compare them to each other. This can happen, for example,
     // if one is produced by an LCSSA PHI node.
     //
     // We check this upfront so we don't crash in cases where getMinusSCEV()
     // returns a SCEVCouldNotCompute.
     LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");
     return std::make_unique<Dependence>(Src, Dst);
   }
   Pair[0].Src = SrcSCEV;
   Pair[0].Dst = DstSCEV;
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
       LLVM_DEBUG(dbgs() << "    delinearized\n");
       Pairs = Pair.size();
     }
   }
 
+  // establish loop nesting levels
+  establishNestingLevels(Src, Dst, Pair);
+  LLVM_DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
+  LLVM_DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");
+
+  FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
+
   for (unsigned P = 0; P < Pairs; ++P) {
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
     removeMatchingExtensions(&Pair[P]);
     Pair[P].Classification =
       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
   assert(isLoadOrStore(Src));
   assert(isLoadOrStore(Dst));
   Value *SrcPtr = getLoadStorePointerOperand(Src);
   Value *DstPtr = getLoadStorePointerOperand(Dst);
   assert(underlyingObjectsAlias(
              AA, F->getParent()->getDataLayout(), MemoryLocation::get(Dst),
              MemoryLocation::get(Src)) == AliasResult::MustAlias);
 
-  // establish loop nesting levels
-  establishNestingLevels(Src, Dst);
-
-  FullDependence Result(Src, Dst, false, CommonLevels);
-
   unsigned Pairs = 1;
-  SmallVector<Subscript, 2> Pair(Pairs);
+  SmallVector<Subscript> Pair(Pairs);
   const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
   const SCEV *DstSCEV = SE->getSCEV(DstPtr);
   Pair[0].Src = SrcSCEV;
   Pair[0].Dst = DstSCEV;
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
       LLVM_DEBUG(dbgs() << "    delinearized\n");
       Pairs = Pair.size();
     }
   }
 
+  // establish loop nesting levels
+  establishNestingLevels(Src, Dst, Pair);
+
+  FullDependence Result(Src, Dst, false, CommonLevels);
+
   for (unsigned P = 0; P < Pairs; ++P) {
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
     removeMatchingExtensions(&Pair[P]);
     Pair[P].Classification =
       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),

llvm/test/Analysis/DependenceAnalysis/MismatchingNestLevels.ll

+; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 | FileCheck %s
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test1':
+; CHECK: Src:  %src = load double, double* %arrayidx295, align 8 --> Dst:  %src = load double, double* %arrayidx295, align 8
+; CHECK-NEXT:    da analyze - consistent input [S 0]!
+; CHECK: Src:  %src = load double, double* %arrayidx295, align 8 --> Dst:  %1 = load double, double* %arrayidx98, align 8
+; CHECK-NEXT:    da analyze - input [S|<]!
+; CHECK: Src:  %1 = load double, double* %arrayidx98, align 8 --> Dst:  %1 = load double, double* %arrayidx98, align 8
+; CHECK-NEXT:    da analyze - consistent input [S]!
+
+define dso_local void @test1([512 x double]* %temp) local_unnamed_addr {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.end63, %entry
+  br label %for.body272
+
+for.body272:                                      ; preds = %for.body272, %for.cond1.preheader
+  %r.1597 = phi i32 [ 1, %for.cond1.preheader ], [ %add277, %for.body272 ]
+  %idxprom274 = zext i32 %r.1597 to i64
+  %add277 = add nuw nsw i32 %r.1597, 1
+  %arrayidx295 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 %idxprom274, i64 510
+  %src = load double, double* %arrayidx295, align 8
+  br i1 undef, label %for.body272, label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.body272
+  %c.2594 = phi i32 [ 1, %for.body272 ], [ %add27, %for.body6 ]
+  %add27 = add nuw nsw i32 %c.2594, 1
+  br i1 undef, label %for.body6, label %for.end63
+
+for.end63:                                        ; preds = %for.body6
+  %c.1.lcssa = phi i32 [ %add27, %for.body6 ]
+  %sub96 = add nsw i32 %c.1.lcssa, -1
+  %0 = zext i32 %sub96 to i64
+  %arrayidx98 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 0, i64 %0
+  %1 = load double, double* %arrayidx98, align 8
+  br label %for.cond1.preheader
+}
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test2':
+; CHECK: Src: %1 = load double, double* %arrayidx98, align 8 --> Dst:  %1 = load double, double* %arrayidx98, align 8
+; CHECK-NEXT:   da analyze - consistent input [S]!
+; CHECK: Src: %1 = load double, double* %arrayidx98, align 8 --> Dst:  %2 = load double, double* %arrayidx295, align 8
+; CHECK-NEXT:   da analyze - input [S|<]!
+; CHECK: Src: %2 = load double, double* %arrayidx295, align 8 --> Dst:  %2 = load double, double* %arrayidx295, align 8
+; CHECK-NEXT:   da analyze - consistent input [S 0]!
+
+define dso_local void @test2([512 x double]* %temp) local_unnamed_addr #0 {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.body272, %entry
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.cond1.preheader
+  %c.2594 = phi i32 [ 1, %for.cond1.preheader ], [ %add27, %for.body6 ]
+  %add27 = add nuw nsw i32 %c.2594, 1
+  br i1 undef, label %for.body6, label %for.end63
+
+for.end63:                                        ; preds = %for.body6
+  %c.1.lcssa = phi i32 [ %add27, %for.body6 ]
+  %sub96 = add nsw i32 %c.1.lcssa, -1
+  %0 = zext i32 %sub96 to i64
+  %arrayidx98 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 0, i64 %0
+  %1 = load double, double* %arrayidx98, align 8
+  br label %for.body272
+
+for.body272:                                      ; preds = %for.body272, %for.end63
+  %r.1597 = phi i32 [ 1, %for.end63 ], [ %add277, %for.body272 ]
+  %idxprom274 = zext i32 %r.1597 to i64
+  %add277 = add nuw nsw i32 %r.1597, 1
+  %arrayidx295 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 %idxprom274, i64 510
+  %2 = load double, double* %arrayidx295, align 8
+  br i1 undef, label %for.body272, label %for.cond1.preheader
+}