[DA] Handle mismatching loop levels by considering them non-linear

[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 simpler but much more conservative approach than D110972. It simply treats such cases as non-linear and therefore not analyzable.

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

935–936

Consider using ScalarEvolution::computeLoopDisposition()

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

905–918

isLoopInvariant is already using computeLoopDisposition(). We should use it even when Expr is a SCEVAddRecExpr.

[bmahjour]

Used getLoopDisposition and improved tests.

[congzhe]

llvm/lib/Analysis/DependenceAnalysis.cpp

937

Thanks for the change, It looks good to me. I don't know if Micheal has further comments?

[nit] I'm wondering if it would be better to simplify the code like this?

if (SE->getLoopDisposition(AddRec, LoopNest) == ScalarEvolution::LoopDisposition::LoopVariant )
  return false;

[congzhe]

llvm/lib/Analysis/DependenceAnalysis.cpp

937

Thanks for the change, It looks good to me. I don't know if Micheal has further comments?

[nit] I'm wondering if it would be better to simplify the code like this?

if (SE->getLoopDisposition(AddRec, LoopNest) == ScalarEvolution::LoopDisposition::LoopVariant )
  return false;

Actually could be futher simplified to

if (SE->getLoopDisposition(AddRec, LoopNest) == ScalarEvolution::LoopVariant )
  return false;

[bmahjour]

llvm/lib/Analysis/DependenceAnalysis.cpp

937

I thought about that too, but decided to check for LoopComputable and LoopInvariant specifically, in case new enums are added to LoopDisposition in the future. The logic also makes a bit more sense when I think about it as neither invariant nor computable. LoopVariant isn't the best wording for what it really means.

[congzhe]

llvm/lib/Analysis/DependenceAnalysis.cpp

937

Sure, makes sense to me.

[Meinersbur]

I was expecting that we only need to call getLoopDisposition once at the beginning of checkSubscript and then decide depending on whether it is a SCEVAddRecExpr, instead of

if (!AddRec)
  return isLoopInvariant(Expr, LoopNest);

Is this possible?

Also, this patch only checks the innermost loop while isLoopInvariant checks all loops in the nest. Would we need as well? Would this fix miss the following case?

for (int i = ) {
   int j = ...
   for (j < ...; ++j ) {
   }
   for (int k = ) {
      S[i][j][k];
  }
}

That is, j is invariant to the k-loop, put still contains a SCEVAddRecExpr of a loop outside the loop nest.

An alternative check:

diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 61bc6750277f7..4a3c5c5e4b202 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -891,6 +893,20 @@ void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
                                     SmallBitVector &Loops, bool IsSrc) {
+  DenseSet<const Loop *> LoopsInNest;
+  const Loop *L = LoopNest;
+  while (L) {
+    LoopsInNest.insert(L);
+    L = L->getParentLoop();
+  }
+
+  if (SCEVExprContains(Expr, [&](const SCEV *E) -> bool {
+        if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E))
+          return !LoopsInNest.contains(AddRec->getLoop());
+        return false;
+      }))
+    return false;
+
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return isLoopInvariant(Expr, LoopNest);

This change passes all the DA tests, inlcuding MismatchingNestLevels
I think (hope?) that such a loop will result in the SCEV loop disposition to be LoopDisposition::LoopVariant, so the getLoopDisposition solution should be better. However, it might not suffice if the loop is not in loop all:

int j = ...
for (j < ...; ++j ) {
}
S[j];

Here, we don't have a loop that we could check the accesses' disposition for.

[bmahjour]

In D110973#3492349, @Meinersbur wrote:

I was expecting that we only need to call getLoopDisposition once at the beginning of checkSubscript and then decide depending on whether it is a SCEVAddRecExpr, instead of

if (!AddRec)
  return isLoopInvariant(Expr, LoopNest);

Is this possible?

I don't think we can do that, because if input is an AddRec that is invariant at the "LoopNest" level but variant at an outer level, we don't have a good way to detect it. This is related to your question about checking "all loops in the nest" (similar to isLoopInvariant), which we cannot do as explained below.

Also, this patch only checks the innermost loop while isLoopInvariant checks all loops in the nest. Would we need as well?

When computing LoopDisposition of an AddRec at an outer loop that contains the AddRec's loop, the algorithm considers it LoopVariant due to the following logic in computeLoopDisposition:

// Everything that is not defined at loop entry is variant.
if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))
  return LoopVariant;

For this reason it would not be correct to check LoopDisposition all the way from innermost to outermost. Doing so, would pessimistically classify subscripts that we care about the most. isLoopInvariant on the other hand is only called for non-AddRecs (which are less analyzable anyway) so it conservatively checks for all loops to make sure the subscript is considered linear only if it's invariant at each loop level.

Would this fix miss the following case?

for (int i = ) {
   int j = ...
   for (j < ...; ++j ) {
   }
   for (int k = ) {
      S[i][j][k];
  }
}

That is, j is invariant to the k-loop, put still contains a SCEVAddRecExpr of a loop outside the loop nest.

I don't think this is a problem, because for the level-mismatch problem to occur there must be another aliasing access in a different level outside of loop j and loop k (for example at i level). If we have an access at i level that has a recurrence with loop j, the disposition will be LoopVariant at i level. See test2 in MismatchingNestLevels.ll below.

An alternative check:

diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 61bc6750277f7..4a3c5c5e4b202 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -891,6 +893,20 @@ void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
                                     SmallBitVector &Loops, bool IsSrc) {
+  DenseSet<const Loop *> LoopsInNest;
+  const Loop *L = LoopNest;
+  while (L) {
+    LoopsInNest.insert(L);
+    L = L->getParentLoop();
+  }
+
+  if (SCEVExprContains(Expr, [&](const SCEV *E) -> bool {
+        if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E))
+          return !LoopsInNest.contains(AddRec->getLoop());
+        return false;
+      }))
+    return false;
+
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return isLoopInvariant(Expr, LoopNest);

This change passes all the DA tests, inlcuding MismatchingNestLevels
I think (hope?) that such a loop will result in the SCEV loop disposition to be LoopDisposition::LoopVariant, so the getLoopDisposition solution should be better. However, it might not suffice if the loop is not in loop all:

int j = ...
for (j < ...; ++j ) {
}
S[j];

Here, we don't have a loop that we could check the accesses' disposition for.

computeLoopDisposition returns LoopVariant for cases where the loop is nullptr (ie function scope), so it should be sufficient for this case too. However, your alternative makes it more obvious and easier to understand, so I'd be ok with that too.

[bmahjour]

Fix test2 to make sure when D71539 is applied, it fails without this patch and passes with it.

[Meinersbur]

As mentioned I would experimented a bit more. Unfortunately I found more problems.

The following crashes even with this patch:

da-variant-crash.ll3 KBDownload

void foo(int n, double * restrict A, double * restrict B) {
    for (int i = 0; i < n; ++i) {
        int s = 0;
        for (; s*s < n*n; ++s) { } // incomputable AddRec
         for (int k = 0; k < n; ++k) 
            A[s] = 0; // Invariant in innermost loop
         
        A[i] = 1; // do create a dependency pair
    }
}

because the the index of A[s] is invariant to its innermost surrounding loop k is invariant and hence passes the additional test.

Even more concerning is something like this, even though it does not crash directly:

   int s = 0;
   for (; s*s < n*n; ++s) ; // incomputable AddRec

for (int i = 0; i < n; ++i) {
     for (int k = 0; k < n; ++k) 
         for (int j = 0; j < n; ++j) 
            A[s + k] = 0; // Invariant: j; Computable: k; Variant: s
     
    A[i] = 1; // do create a dependency pair
}

ScalarEvolution's LoopDisposition test skips s because it is nested inside an AddRec that is invariant because its of an outer loop (((8 * (sext i32 {{0,+,1}<nuw><nsw><%for.cond>,+,1}<nuw><%for.cond5> to i64))<nsw> + %A)) and hence returns the entire thing as invariant even though it contains an SCEVAddRecExpr outside the loop nest. I again tend towards to scanning the SCEVExpr for illegal SCEVAddRecExpr. See [the only important remark].

llvm/lib/Analysis/DependenceAnalysis.cpp

801–802

This seems in conflict with handling within ScalarEvolution:

// Instructions are never considered invariant in the function body
// (null loop) because they are defined within the "loop".

Suggested alternative comments/non-recursive implementation:

 // Outside any loop, an expression will not vary between executions (there is only one) and we consider it invariant. In contrast to ScalarEvolution::isLoopInvariant, we only consider expression evalution at a specific position, the array access, not accross the function.
 if (!LoopNest)
   return true;

 // If the expression is invariant in the outermost loop of the loop nest, it is invariant anywhere in the loop nest. 
const  Loop * OutermostLoop = LoopNest;
 while (OutermostLoop->getParentLoop())
     OutermostLoop = OutermostLoop->getParentLoop();
 return SE->isLoopInvariant(Expression, OutermostLoop);

900

We allow for non-zero Start value, hence it is affine, not linear.

920

[suggestion] SCEVAddRecExpr has a member isAffine that could be queried directly.

931–934

mapSrcLoop/mapDstLoop may already be out-of-range because AddRec->getLoop() is not surrounding the SCEVExpr.

One could include a sanity check inside mapSrcLoop/mapDstLoop:

const Loop* L = LoopNest;
while (L && AddRec->getLoop() != L) 
    L = L->getParentLoop();
assert (L && "Must be in loop nest, otherwise mapSrcLoop/mapDstLoop will be out-of-range");

935

This recursive call may also return false, in which case Loops.set has already been executed. (This may be irrelevant because when returning false, Loops is probably be ignored anyway).

937

[the only important remark] I suggest to use this check instead to fix the additional crash:

// The AddRec must depend on one of the surrounding loops. Otherwise, mapSrcLoop and mapDstLoop return indices outside the intended range. This can happen when a subscript in one loop references an IV from a sibling loop that could not be replaced with a concrete exit value by getSCEVAtScope. 
const Loop* L = LoopNest;
while (L && AddRec->getLoop() != L) 
    L = L->getParentLoop();
if (!L)
    return false;

Currently I am too unsure whether we can make computeLoopDisposition work reliably.

This ignores that there could be SCEVAddRecExpr in other SCEV subexpressions, but I think DA doesn't try to reach them anyway. Maybe add a comment about this somewhere.

[bmahjour]

The following crashes even with this patch:

I actually don't see any crashes with the examples provided, but I do see that A[s] is being treated as invariant, so it does seem to bypass the getLoopDisposition checks. I'm changing checkSubscript to look for the addrec loop in the nest as you've suggested.

llvm/lib/Analysis/DependenceAnalysis.cpp

920

I think this change should be pursued as a separate patche. isAffine just checks the number of operands, and for example doesn't check that the step is invariant, so there could be some semantic differences.

935

Yes, classifyPair returns immediately if checkSubscript returns false, and the loop lists get destructed without being used.

[Meinersbur]

LGTM

llvm/lib/Analysis/DependenceAnalysis.cpp

931

[nit] whitespace

[bmahjour]

Rebased and added Michael's test case.

llvm/lib/Analysis/DependenceAnalysis.cpp

931–934

I tried adding this assert inside checkSubscripts right before the calls to mapSrcLoop and mapDstLoop and was able to get your test case to assert with the previous version of this patch. I've now added your test into MismatchingNestLevels.ll.

I also looked into adding this assert, but decided not to do it for the following reasons:

1. Except for checkSubscripts, all callers of mapSrcLoop and mapDstLoop, get their loops from an AddRec. Checking that the AddRec's loop exists in the loop nest will always satisfy the assertion, so it's pointless to add in those cases. Inside checkSubscript with this patch we already check for the condition being asserted and exit early, so no point in adding the assert inside checkSubscript either.
2. I tried adding assert(D > 0 && D <= MaxLevels) to mapSrcLoop and mapDstLoop, but it didn't get triggered with the previous version of this patch. That's actually expected because with the numbering system a level will never be outside of this range. The consideration for a level to be out of range depends on the specific dependence test (eg. while exactSIVtest asserts that Level <= CommonLevels, weakZeroSrcSIVtest asserts that Level <= MaxLevels), so there is no way to add such assertion to mapSrcLoop and mapDstLoop because they are used by various kinds of dependence tests.

[fhahn]

Thanks for pushing the fix through! I think this should unblock D71539 now.

[bmahjour]

In D110973#3567685, @fhahn wrote:

Thanks for pushing the fix through! I think this should unblock D71539 now.

Yes, D71539 should be safe to re-commit now. I've also closed https://github.com/llvm/llvm-project/issues/50612. Thanks!

llvm/lib/Analysis/DependenceAnalysis.cpp

 }
 
 
 // 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,
                                      const Loop *LoopNest) const {
+  // Unlike ScalarEvolution::isLoopInvariant() we consider an access outside of
+  // any loop as invariant, because we only consier expression evaluation at a
+  // specific position (where the array access takes place), and not across the
+  // entire function.
   if (!LoopNest)
     return true;
-  return SE->isLoopInvariant(Expression, LoopNest) &&
-    isLoopInvariant(Expression, LoopNest->getParentLoop());
+
+  // If the expression is invariant in the outermost loop of the loop nest, it
+  // is invariant anywhere in the loop nest.
+  const Loop *OutermostLoop = LoopNest;
+  while (OutermostLoop->getParentLoop())
+    OutermostLoop = OutermostLoop->getParentLoop();
+  return SE->isLoopInvariant(Expression, OutermostLoop);
 }
 
 
 
 // Finds the set of loops from the LoopNest that
 // have a level <= CommonLevels and are referred to by the SCEV Expression.
 void DependenceInfo::collectCommonLoops(const SCEV *Expression,
                                         const Loop *LoopNest,
if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
     const SCEV *DstCastOp = DstCast->getOperand();
     if (SrcCastOp->getType() == DstCastOp->getType()) {
       Pair->Src = SrcCastOp;
       Pair->Dst = DstCastOp;
     }
   }
 }
 
-// Examine the scev and return true iff it's linear.
+// Examine the scev and return true iff it's affine.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
                                     SmallBitVector &Loops, bool IsSrc) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return isLoopInvariant(Expr, LoopNest);
+
+  // The AddRec must depend on one of the containing loops. Otherwise,
+  // mapSrcLoop and mapDstLoop return indices outside the intended range. This
+  // can happen when a subscript in one loop references an IV from a sibling
+  // loop that could not be replaced with a concrete exit value by
+  // getSCEVAtScope.
+  const Loop *L = LoopNest;
+  while (L && AddRec->getLoop() != L)
+    L = L->getParentLoop();
+  if (!L)
+    return false;
+
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;
     }
   }
   if (!isLoopInvariant(Step, LoopNest))
     return false;
   if (IsSrc)
     Loops.set(mapSrcLoop(AddRec->getLoop()));
   else
     Loops.set(mapDstLoop(AddRec->getLoop()));
   return checkSubscript(Start, LoopNest, Loops, IsSrc);
 }
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
                                        SmallBitVector &Loops) {
   return checkSubscript(Src, LoopNest, Loops, true);
 }
 
 // Examine the scev and return true iff it's linear.

llvm/test/Analysis/DependenceAnalysis/MismatchingNestLevels.ll

+; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 | FileCheck %s
+
+;; void test1(long n, double *A) {
+;;     long  i;
+;;     for (i = 0; i*n <= n*n; ++i) {
+;;         A[i] = i;
+;;     }
+;;     A[i] = i;
+;; }
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test1':
+; CHECK: Src:  store double %conv, ptr %arrayidx, align 8 --> Dst:  store double %conv, ptr %arrayidx, align 8
+; CHECK-NEXT:    da analyze - none!
+; CHECK: Src:  store double %conv, ptr %arrayidx, align 8 --> Dst:  store double %conv2, ptr %arrayidx3, align 8
+; CHECK-NEXT:    da analyze - output [|<]!
+; CHECK: Src:  store double %conv2, ptr %arrayidx3, align 8 --> Dst:  store double %conv2, ptr %arrayidx3, align 8
+; CHECK-NEXT:    da analyze - none!
+
+define void @test1(i64 noundef %n, ptr nocapture noundef writeonly %A) {
+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
+  %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
+
+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
+  ret void
+}
+
+
+;; int test2(unsigned n, float A[][n+1], float B[n+1]) {
+;;  for (int i = 0; i <= n; i++) {
+;;    long j = 0;
+;;    for (; j <= n; ++j) {
+;;      B[j] = j;
+;;    }
+;;    A[i][j] = 123;
+;;    for (int k = 0; k <= n; k++) {
+;;      A[i][k] = k;
+;;    }
+;;  }
+;;
+;; Make sure we can detect depnendence between A[i][j] and A[i][k] conservatively and without crashing.
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test2':
+; CHECK:       Src:  store float 1.230000e+02, ptr %arrayidx7, align 4 --> Dst:  store float %conv13, ptr %arrayidx17, align 4
+; CHECK-NEXT:    da analyze - output [*|<]!
+
+define dso_local void @test2(i32 noundef zeroext %n, ptr noundef %A, ptr noalias noundef %B) #0 {
+entry:
+  %add = add i32 %n, 1
+  %0 = zext i32 %add to i64
+  %1 = zext i32 %n to i64
+  %2 = add nuw nsw i64 %1, 1
+  %wide.trip.count9 = zext i32 %add to i64
+  br label %for.i
+
+for.i:                                         ; preds = %entry, %for.inc21
+  %indvars.iv6 = phi i64 [ 0, %entry ], [ %indvars.iv.next7, %for.inc21 ]
+  br label %for.j
+
+for.j:                                        ; preds = %for.i, %for.j
+  %j.01 = phi i64 [ 0, %for.i ], [ %inc, %for.j ]
+  %conv5 = trunc i64 %j.01 to i32
+  %arrayidx = getelementptr inbounds i32, ptr %B, i64 %j.01
+  store i32 %conv5, ptr %arrayidx, align 4
+  %inc = add nuw nsw i64 %j.01, 1
+  %exitcond = icmp ne i64 %inc, %2
+  br i1 %exitcond, label %for.j, label %for.end
+
+for.end:                                          ; preds = %for.j
+  %inc.lcssa = phi i64 [ %inc, %for.j ]
+  %3 = mul nuw nsw i64 %indvars.iv6, %0
+  %arrayidx6 = getelementptr inbounds float, ptr %A, i64 %3
+  %arrayidx7 = getelementptr inbounds float, ptr %arrayidx6, i64 %inc.lcssa
+  store float 1.230000e+02, ptr %arrayidx7, align 4
+  %wide.trip.count = zext i32 %add to i64
+  br label %for.k
+
+for.k:                                       ; preds = %for.end, %for.k
+  %indvars.iv = phi i64 [ 0, %for.end ], [ %indvars.iv.next, %for.k ]
+  %4 = trunc i64 %indvars.iv to i32
+  %conv13 = sitofp i32 %4 to float
+  %5 = mul nuw nsw i64 %indvars.iv6, %0
+  %arrayidx15 = getelementptr inbounds float, ptr %A, i64 %5
+  %arrayidx17 = getelementptr inbounds float, ptr %arrayidx15, i64 %indvars.iv
+  store float %conv13, ptr %arrayidx17, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond5 = icmp ne i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond5, label %for.k, label %for.inc21
+
+for.inc21:                                        ; preds = %for.k
+  %indvars.iv.next7 = add nuw nsw i64 %indvars.iv6, 1
+  %exitcond10 = icmp ne i64 %indvars.iv.next7, %wide.trip.count9
+  br i1 %exitcond10, label %for.i, label %for.end23
+
+for.end23:                                        ; preds = %for.inc21
+  ret void
+}
+
+
+;; void test3(int n, double *restrict A, double *restrict B) {
+;;   for (int i = 0; i < n; ++i) {
+;;     int s = 0;
+;;     for (; s * s < n * n; ++s) {
+;;     }
+;;     for (int k = 0; k < n; ++k)
+;;       A[s] = 0; // Invariant in innermost loop
+;;
+;;     A[i] = 1;
+;;   }
+;; }
+;;
+;; Make sure we can detect depnendence between A[i] and A[s] conservatively and without crashing.
+
+; CHECK-LABEL: 'Dependence Analysis' for function 'test3':
+; CHECK:       Src:  store double 0.000000e+00, ptr %arrayidx, align 8 --> Dst:  store double 1.000000e+00, ptr %arrayidx21, align 8
+; CHECK-NEXT:    da analyze - output [*|<]!
+
+define void @test3(i32 noundef %n, ptr noalias noundef %A, ptr noalias noundef %B) {
+entry:
+  br label %for.i
+
+for.i:                                         ; preds = %for.end19, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc23, %for.end19 ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.s, label %for.end24
+
+for.s:                                        ; preds = %for.i, %for.inc
+  %s.0 = phi i32 [ %inc, %for.inc ], [ 0, %for.i ]
+  %mul = mul nsw i32 %s.0, %s.0
+  %mul2 = mul nsw i32 %n, %n
+  %cmp3 = icmp slt i32 %mul, %mul2
+  br i1 %cmp3, label %for.inc, label %for.k
+
+for.inc:                                          ; preds = %for.s
+  %inc = add nsw i32 %s.0, 1
+  br label %for.s
+
+for.k:                                        ; preds = %for.s, %for.body.k
+  %k.0 = phi i32 [ %inc10, %for.body.k ], [ 0, %for.s ]
+  %cmp6 = icmp slt i32 %k.0, %n
+  br i1 %cmp6, label %for.body.k, label %for.end19
+
+for.body.k:                                        ; preds = %for.k
+  %idxprom = sext i32 %s.0 to i64
+  %arrayidx = getelementptr inbounds double, ptr %A, i64 %idxprom
+  store double 0.000000e+00, ptr %arrayidx, align 8
+  %inc10 = add nsw i32 %k.0, 1
+  br label %for.k
+
+for.end19:                                        ; preds = %for.k
+  %idxprom20 = sext i32 %i.0 to i64
+  %arrayidx21 = getelementptr inbounds double, ptr %A, i64 %idxprom20
+  store double 1.000000e+00, ptr %arrayidx21, align 8
+  %inc23 = add nsw i32 %i.0, 1
+  br label %for.i
+
+for.end24:                                        ; preds = %for.i
+  ret void
+}