[LoopVectorize] Clear cache of `LoopAccessInfoManager`

[Saldivarcher]

Summary

LAI is cached during the LoopDistribute pass, and is later re-used during LoopVectorize. The problem is that LoopVectorize changes SCEV, and the cached LAI does not get updated. Hence, when re-using the cached LAI, it references an invalid SCEV.

Fixes #59319

[fhahn]

Thanks for the patch! Some comments inline.

Could you add Fixes #59319 to the description, to make sure the issue is closed once this lands?

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

We only need to clear if changes were made AFAICT

llvm/test/Transforms/LoopDistribute/pr59319.ll

3

nit: remove

5

Is this needed? If so, the test requires something like ; REQUIRES: x86-registered-target to make sure it is only run when the X86 backend is built.

13

nit: strip the indvars. prefix, it doesn't add anything and makes the names unnecessarily long.

24

Could you improve the naming of the blocks, e.g. loop.1, loop.2, something like that to make things easier to parse.

[Saldivarcher]

@fhahn thanks for taking a look! I made all the changes/improvements you suggested, looks a lot better.

Yeah, the assertion is only hit when a target is present, so that's why the target was there.

[Saldivarcher]

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

The assertion is still hit if we only clear when changes are made, I think it's because we insert the loop here, then fail right after. So, there's still cached data when there are no changes made. Keep in mind that the LoopDistribute pass fails with all the loops, and all fail here.

[Saldivarcher]

@fhahn did you have any other comments/concerns?

[fhahn]

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

Right, this indicates that LoopDistribute isn't the right place to fix it. We should only need invalidation *after* the IR changes. If the IR stays the same, there should be no issue with the cached loop-info objects.

I think the right place to invalidate here is in LoopVectorize's runImpl.

llvm/test/Transforms/LoopDistribute/pr59319.ll

3

no need to use <

6

nit: usually there's a space after ; both here and below.

9

check the full IR?

[fhahn]

llvm/test/Transforms/LoopDistribute/pr59319.ll

40

move the end of function

[Saldivarcher]

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

When you mean invalidate, do you mean to clear the cache within LoopAccessInfoMap?

[Saldivarcher]

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

When you mean invalidate, do you mean to clear the cache within LoopAccessInfoMap?

When you say*

[fhahn]

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

995

When you mean invalidate, do you mean to clear the cache within LoopAccessInfoMap?

Yes

[Saldivarcher]

llvm/test/Transforms/LoopVectorize/pr59319.ll

9 ↗

(On Diff #486153)

check the full IR?

The resulting IR is pretty long, around ~150 lines. I think it might be a bit exhaustive to check the full resulting IR, is there something else I should check?

[Saldivarcher]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10603 ↗

(On Diff #486153)

@fhahn I wasn't sure where the best place to invalidate cache, if you think I should do it elsewhere I can do that.

[Saldivarcher]

llvm/test/Transforms/LoopVectorize/pr59319.ll

1 ↗

(On Diff #486153)

@fhahn I moved the test over to the LoopVectorize directory, hope that's alright! :)

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10603 ↗

(On Diff #486153)

It *should* be sufficient to do it if processLoop at line 10632 made modifications I think

llvm/test/Transforms/LoopVectorize/pr59319.ll

5 ↗

(On Diff #486153)

If it requires X86, please move it to the X86 subdirectory.

[Saldivarcher]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10603 ↗

(On Diff #486153)

That makes more sense, I only invalidate if something changed.

llvm/test/Transforms/LoopVectorize/X86/pr59319.ll

1 ↗

(On Diff #486310)

Ok, moved to the x86 directory, thanks for pointing that out.

[fhahn]

LGTM, with the comments addressed.

llvm/test/Transforms/LoopVectorize/X86/pr59319.ll

1 ↗

(On Diff #486310)

is it possible to specify a fixed VF/UF using -force-vector-width=X -force-vector-interleave=Y?

5 ↗

(On Diff #486310)

not needed now

8 ↗

(On Diff #486310)

It still would be good to make sure the IR we generate makes sense. You can use llvm/utils/update_test_checks.py to generate checks.

[fhahn]

As #59319 describes, enabling LoopDistribute along with LoopVectorize causes an assertion to be hit. The reason seems to be because the LoopDistribute pass doesn't clear out the cache of the LoopAccessInfoManager.

This needs updating, the reason is that we cache LAI during LoopDistribute, LoopVectorize makes changes that invalidate SCEV and then we re-use the cache LAI which references invalid SCEV expressions.

[Saldivarcher]

In D139601#4029994, @fhahn wrote:

As #59319 describes, enabling LoopDistribute along with LoopVectorize causes an assertion to be hit. The reason seems to be because the LoopDistribute pass doesn't clear out the cache of the LoopAccessInfoManager.

This needs updating, the reason is that we cache LAI during LoopDistribute, LoopVectorize makes changes that invalidate SCEV and then we re-use the cache LAI which references invalid SCEV expressions.

Updated!

llvm/test/Transforms/LoopVectorize/X86/pr59319.ll

8 ↗

(On Diff #486310)

Addressed all the comments. TIL about update_test_checks.py, thank you!

[fhahn]

LGTM, thanks! Just a few additional small comments for the test .

llvm/test/Transforms/LoopVectorize/X86/pr59319.ll

5 ↗

(On Diff #486724)

I *think* with the vectorization factor forced, the test doesn't need to be X86 specific. I think the triple now could be removed and the test moved out of the X86 directory.

might also be good to include a quick comment in the test that this tests LoopAccessInfo invalidation after LV modifying the IR. Might also be good to include something like loop-access-info-invalidation in the test name (in addition to prXXXX)

[Saldivarcher]

In D139601#4030711, @fhahn wrote:

LGTM, thanks! Just a few additional small comments for the test .

Thanks for taking the time to review this stuff, I appreciate it!

All comments should be addressed now. :)

[Saldivarcher]

@fhahn also, would you be able to commit this for me? I don't have commit access.

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT,
   bool Changed = false;
   for (Loop *L : Worklist) {
     LoopDistributeForLoop LDL(L, &F, LI, DT, SE, LAIs, ORE);
 
     // If distribution was forced for the specific loop to be
     // enabled/disabled, follow that.  Otherwise use the global flag.
     if (LDL.isForced().value_or(EnableLoopDistribute))
       Changed |= LDL.processLoop();
+    LAIs.clear();
   }
 
   // Process each loop nest in the function.
   return Changed;
 }
 
 namespace {
 

llvm/test/Transforms/LoopDistribute/pr59319.ll

+; RUN: opt -passes=loop-distribute,loop-vectorize -enable-loop-distribute -S \
+; RUN: < %s | FileCheck %s
+; ModuleID = '<bc file>'
+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"
+
+define void @reduced(i32* %0, i32* %1, i64 %indvars.iv, i32* %2, i64 %indvars.iv76, i64 %indvars.iv93) {
+;CHECK-LABEL: @reduced(
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv761 = phi i64 [ 0, %entry ], [ %indvars.iv.next77, %for.body ]
+  %indvars.iv4 = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next77 = add i64 %indvars.iv761, 1
+  %arrayidx.i.i50 = getelementptr i32, i32* %0, i64 %indvars.iv76
+  %indvars.iv.next = add i64 %indvars.iv4, 1
+  %exitcond.not = icmp eq i64 %indvars.iv4, %indvars.iv
+  br i1 %exitcond.not, label %for.body13.preheader, label %for.body
+
+for.body13.preheader:                             ; preds = %for.body
+  br label %for.body13
+
+for.body26.lr.ph:                                 ; preds = %for.body13
+  %idxprom.i.i61 = and i64 %indvars.iv761, 1
+  %arrayidx.i.i62 = getelementptr i32, i32* %0, i64 %idxprom.i.i61
+  br label %for.body26
+
+for.body13:                                       ; preds = %for.body13, %for.body13.preheader
+  %indvars.iv846 = phi i64 [ %indvars.iv.next85, %for.body13 ], [ 0, %for.body13.preheader ]
+  %indvars.iv.next87 = add i64 0, 0
+  %arrayidx.i.i56 = getelementptr i32, i32* %0, i64 %indvars.iv761
+  %3 = load i32, i32* %arrayidx.i.i56, align 4
+  store i32 0, i32* %1, align 4
+  %indvars.iv.next85 = add i64 %indvars.iv846, 1
+  %exitcond92.not = icmp eq i64 %indvars.iv846, %indvars.iv
+  br i1 %exitcond92.not, label %for.body26.lr.ph, label %for.body13
+
+for.cond.cleanup25:                               ; preds = %for.body26
+  ret void
+
+for.body26:                                       ; preds = %for.body26, %for.body26.lr.ph
+  %indvars.iv932 = phi i64 [ 0, %for.body26.lr.ph ], [ %indvars.iv.next94, %for.body26 ]
+  %4 = load i32, i32* %arrayidx.i.i62, align 4
+  %arrayidx.i.i653 = getelementptr i32, i32* %2, i64 %indvars.iv93
+  store i32 0, i32* %1, align 4
+  %indvars.iv.next94 = add i64 %indvars.iv932, 1
+  %exitcond97.not = icmp eq i64 %indvars.iv932, %indvars.iv
+  br i1 %exitcond97.not, label %for.cond.cleanup25, label %for.body26
+}