[LAA] Fix ICE with scAddExpr in forked pointers

[huntergr]

Summary

The IR from https://github.com/llvm/llvm-project/issues/57368 results
in an assert firing when trying to create a runtime check for the
forked pointer. One of the forks is fine since it's loop invariant,
but the other is a scAddExpr (containing a scAddRecExpr, so not
invariant) when RtCheck::insert expects a scAddRecExpr.

This is a simple fix to just avoid forks which aren't AddRec or
loop invariant. We can allow it as a forked pointer later with
more work.

[huntergr]

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

899

This concerns me a bit -- the lower bound is correct, but the upper bound seems wrong. But that isn't related to my forked pointers patch -- I get the same output if I comment out the forked pointer detection code entirely.

[fhahn]

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

899

This is probably because PSE a predicate for this. The loop has an IV that start at 0 and we only exit if iv == 0. This can only happen if iv overflows AFAICT. But the IV increment is add nuw nsw i64 %indvars.iv.us1, 1, so if it overflows it is UB.

Can the issue be reproduced with a loop that doesn't have UB, e.g. replacing the existing exit check with something like cmp eq i64 %indvars.iv.next.us, %N?

925

The IR value names here seem a bit long which makes things a bit harder to read. It would probably be good to remove the naming prefixes/suffixes added be LLVM transforms (.e.g indvars, i.i., .us)

[huntergr]

Simplified the value names in the test case to improve readability.

[huntergr]

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

899

You're right, thanks. I see (Low: %Base2 High: ((8 * %N) + %Base2)) if I add a parameter for iterations.

[fhahn]

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

899

It would probably make the test easier to follow if the test would use the updated exit condition. It should still reproduce the AddRec issue I think.

[huntergr]

Changed test to use a non-constant-zero loop limit to remove UB.

[fhahn]

LGTM, thanks, with a few additional small test case suggestions.

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

928

Is the trunc & ext needed for the cash to reproduce? If not, it would be good to remove it.

929

Can you make the condition here a function argument? Not having the select being fold-able may make the test more robust in case SCEV gets extended to look through trivial selects.

[fhahn]

reverse ping?

[huntergr]

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

928

No. We might be able to use different instructions, but without the zext at least we would have an AddRecExpr, which would just be folded.

929

No. I think SCEV already looks through the select at some point; if the condition isn't constant we don't see the crash.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 findForkedPointer(PredicatedScalarEvolution &PSE,
                   const ValueToValueMap &StridesMap, Value *Ptr,
                   const Loop *L) {
   ScalarEvolution *SE = PSE.getSE();
   assert(SE->isSCEVable(Ptr->getType()) && "Value is not SCEVable!");
   SmallVector<std::pair<const SCEV *, bool>> Scevs;
   findForkedSCEVs(SE, L, Ptr, Scevs, MaxForkedSCEVDepth);
 
-  // For now, we will only accept a forked pointer with two possible SCEVs.
-  if (Scevs.size() == 2)
+  // For now, we will only accept a forked pointer with two possible SCEVs
+  // that are either SCEVAddRecExprs or loop invariant.
+  if (Scevs.size() == 2 &&
+      (isa<SCEVAddRecExpr>(Scevs[0].first) ||
+       SE->isLoopInvariant(Scevs[0].first, L)) &&
+      (isa<SCEVAddRecExpr>(Scevs[1].first) ||
+       SE->isLoopInvariant(Scevs[1].first, L))) {
+    LLVM_DEBUG(dbgs() << "LAA: Found forked pointer: " << *Ptr << "\n");
+    LLVM_DEBUG(dbgs() << "\t(1) " << *(Scevs[0].first) << "\n");
+    LLVM_DEBUG(dbgs() << "\t(2) " << *(Scevs[1].first) << "\n");
     return Scevs;
+  }
 
   return {
       std::make_pair(replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false)};
 }
 
 bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
                                           MemAccessInfo Access, Type *AccessTy,
                                           const ValueToValueMap &StridesMap,

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[G1:.+]]):
 ; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
 ; CHECK-NEXT:      Against group ([[G2:.+]]):
 ; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, ptr %Preds, i64 %indvars.iv
 ; CHECK-NEXT:    Check 1:
-; CHECK-NEXT:      Comparing group ([[G1:.+]]):
+; CHECK-NEXT:      Comparing group ([[G1]]):
 ; CHECK-NEXT:        %arrayidx5 = getelementptr inbounds float, ptr %Dest, i64 %indvars.iv
 ; CHECK-NEXT:      Against group ([[G3:.+]]):
 ; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
 ; CHECK-NEXT:        %arrayidx3 = getelementptr inbounds float, ptr %Base, i64 %offset
 ; CHECK-NEXT:    Grouped accesses:
-; CHECK-NEXT:      Group [[G1:.+]]:
+; CHECK-NEXT:      Group [[G1]]:
 ; CHECK-NEXT:        (Low: %Dest High: (400 + %Dest))
 ; CHECK-NEXT:          Member: {%Dest,+,4}<nuw><%for.body>
 ; CHECK-NEXT:      Group [[G2]]:
 ; CHECK-NEXT:        (Low: %Preds High: (400 + %Preds))
 ; CHECK-NEXT:          Member: {%Preds,+,4}<nuw><%for.body>
 ; CHECK-NEXT:      Group [[G3]]:
 ; CHECK-NEXT:        (Low: ((4 * %to_add) + (-4 * %to_sub) + %Base) High: (404 + (4 * %to_add) + (-4 * %to_sub) + %Base))
 ; CHECK-NEXT:          Member: {(4 + (4 * %to_add) + (-4 * %to_sub) + %Base),+,4}<%for.body>
for.body:
   store <4 x float> %.sink, ptr %1, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 4
   %exitcond.not = icmp eq i64 %indvars.iv.next, 100
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:
   ret void
 }
+
+; CHECK-LABEL: Loop access info in function 'sc_add_expr_ice':
+; CHECK-NEXT:   for.body:
+; CHECK-NEXT:     Memory dependences are safe with run-time checks
+; CHECK-NEXT:     Dependences:
+; CHECK-NEXT:     Run-time memory checks:
+; CHECK-NEXT:     Check 0:
+; CHECK-NEXT:       Comparing group ([[G1:.+]]):
+; CHECK-NEXT:       ptr %Base1
+; CHECK-NEXT:       Against group ([[G2:.+]]):
+; CHECK-NEXT:         %fptr = getelementptr inbounds double, ptr %Base2, i64 %sel
+; CHECK-NEXT:     Grouped accesses:
+; CHECK-NEXT:       Group [[G1]]:
+; CHECK-NEXT:         (Low: %Base1 High: (8 + %Base1))
+; CHECK-NEXT:           Member: %Base1
+; CHECK-NEXT:       Group [[G2]]:
+; CHECK-NEXT:         (Low: %Base2 High: ((8 * %N) + %Base2))
+; CHECK-NEXT:           Member: {%Base2,+,8}<%for.body>
+; CHECK-EMPTY:
+; CHECK-NEXT:     Non vectorizable stores to invariant address were not found in loop.
+; CHECK-NEXT:     SCEV assumptions:
+; CHECK-NEXT:     {0,+,1}<%for.body> Added Flags: <nusw>
+; CHECK-EMPTY:
+; CHECK-NEXT:     Expressions re-written:
+; CHECK-NEXT:     [PSE]  %fptr = getelementptr inbounds double, ptr %Base2, i64 %sel:
+; CHECK-NEXT:       ((8 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %Base2)<nuw>
+; CHECK-NEXT:       --> {%Base2,+,8}<%for.body>
+
+;;; The following test caused an ICE with the initial forked pointers work.
+;;; One fork is loop invariant (%Base2 + 0), the other is an scAddExpr that
+;;; contains an scAddRecExpr inside it:
+;;;   ((8 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %Base2)<nuw>
+;;;
+;;; RtCheck::insert was expecting either loop invariant or SAR, so asserted
+;;; on a plain scAddExpr. For now we restrict to loop invariant or SAR
+;;; forks only, but we should be able to do better.
+
+define void @sc_add_expr_ice(ptr %Base1, ptr %Base2, i64 %N) {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.trunc = trunc i64 %iv to i32
+  store double 0.000000e+00, ptr %Base1, align 8
+  %iv.zext = zext i32 %iv.trunc to i64
+  %sel = select i1 true, i64 %iv.zext, i64 0
+  %fptr = getelementptr inbounds double, ptr %Base2, i64 %sel
+  %dummy.load = load double, ptr %fptr, align 8
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %N
+  br i1 %exitcond, label %exit, label %for.body
+
+exit:
+  ret void
+}