[LAA] Avoid non-determinism due to blocks order. PR56672

[mkazantsev]

Summary

As test in PR56672 shows, LAA produces different results which lead to either
positive or negative vectorization decisions depending on the order of blocks
in loop. The exact reason of this is not clear to me, however this makes investigation
of related bugs extremely complex.

Current order of blocks in the loop is arbitrary. It may change, for example, if loop
info analysis is dropped and recomputed. Seems that it interferes with LAA's logic.
This patch fixates the traversal order of blocks in loops, making it RPOT.

[aeubanks]

lg

[fhahn]

It would be good to clean up the test first.

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

2 ↗

(On Diff #447307)

As this test a LAA issue, could you just use print<loop-accesses> instead?

46 ↗

(On Diff #447307)

adressspace not needed.

48 ↗

(On Diff #447307)

please replace the undef to avoid the test having UB

54 ↗

(On Diff #447307)

Please avoid loads from null, as this is UB.

[fhahn]

I am not sure this patch completely fixes the underlying issue causing the mis-compile. I should know more by tomorrow and also be able to add a few cleaned up test cases.

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

2 ↗

(On Diff #447307)

use print<loop-accesses>

The pass name is actually print-access-info, which should probably be fixed.

[mkazantsev]

Updated test as @fhahn has proposed and moved it to LAA tests. Floran, if you can take a look into it and confirm or disprove this is a correct fix, I'd appreciate that. I'm not familiar with LAA's algorithm, so I'm just seeing this as blackbox which behaves non-deterministically depending on blocks order, and I don't know if it's expected or not. If there is a more targeted fix, that'd be nice. I'll hold this patch for a while.

[fhahn]

In D130482#3678511, @mkazantsev wrote:

Updated test as @fhahn has proposed and moved it to LAA tests. Floran, if you can take a look into it and confirm or disprove this is a correct fix, I'd appreciate that. I'm not familiar with LAA's algorithm, so I'm just seeing this as blackbox which behaves non-deterministically depending on blocks order, and I don't know if it's expected or not. If there is a more targeted fix, that'd be nice. I'll hold this patch for a while.

Thanks for your patience! After taking a closer look, it seems like the patch is a good first step and clearly improves the current situation. Fixing the remaining issue will require more time, and visiting the blocks in deterministic order is helpful in general.

LGTM, thanks!

llvm/test/Analysis/LoopAccessAnalysis/pr56672.ll

6

nit: shouldn't be needed

8

nit: Remove reference to vectorizer?

20

nit: test case might be slightly easier to read if the block would come after the loop header (%bb4), potentially also with more descriptive names for the blocks.

33

nit: could this just be an unconditional branch? If not, bb10 could be removed.

[efriedma]

In general, I prefer not to refer to any issue that involves different inputs leading to different outputs as "non-determinism". It might be bad for various reasons to make the output sensitive to minor details of the input, but actual non-determinism is a much more serious problem because the output isn't reproducible.

[reames]

In D130482#3682855, @efriedma wrote:

In general, I prefer not to refer to any issue that involves different inputs leading to different outputs as "non-determinism". It might be bad for various reasons to make the output sensitive to minor details of the input, but actual non-determinism is a much more serious problem because the output isn't reproducible.

Agreed here. Better wording would be to say that we're removing a block order sensitivity.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2131–2135

nit: replace deterministic with "fixed".

[mkazantsev]

llvm/test/Analysis/LoopAccessAnalysis/pr56672.ll

6

Not sure, but let's try to remove.

8

Ok

20

No, non-standard blocks order is what seems to be causing the bug. We can't rearrange them. Renamin will do.

33

Yup, we can.

[mkazantsev]

llvm/test/Analysis/LoopAccessAnalysis/pr56672.ll

33

Rrrr, scratch that. Thank you for finding this. No, removal of this branch still reproduces the bug, but the fix doesn't help for it.

[mkazantsev]

llvm/test/Analysis/LoopAccessAnalysis/pr56672.ll

33

Let's frame this patch as "algo depends on blocks order" issue. I will file this separately, along with modified test. The answer for now is "we can't remove this to show *this* bug".

[mkazantsev]

Filed issue found during test reduction as https://github.com/llvm/llvm-project/issues/56771

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/BasicBlock.h"
void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
   PtrRtChecking->Need = false;
 
   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
 
   const bool EnableMemAccessVersioningOfLoop =
       EnableMemAccessVersioning &&
       !TheLoop->getHeader()->getParent()->hasOptSize();
 
-  // For each block.
-  for (BasicBlock *BB : TheLoop->blocks()) {
+  // Traverse blocks in fixed RPOT order, regardless of their storage in the
+  // loop info, as it may be arbitrary.
+  LoopBlocksRPO RPOT(TheLoop);
+  RPOT.perform(LI);
+  for (BasicBlock *BB : RPOT) {
     // Scan the BB and collect legal loads and stores. Also detect any
     // convergent instructions.
     for (Instruction &I : *BB) {
       if (auto *Call = dyn_cast<CallBase>(&I)) {
         if (Call->isConvergent())
           HasConvergentOp = true;
       }
 

llvm/test/Analysis/LoopAccessAnalysis/pr56672.ll

+; RUN: opt -passes='loop(loop-rotate),print-access-info' -S %s 2>&1 | FileCheck %s
+; RUN: opt -passes='loop(loop-rotate),invalidate<loops>,print-access-info' -S %s 2>&1 | FileCheck %s
+
+; Make sure that the result of analysis is consistent regardless of blocks
+; order as they are stored in loop. This test demonstrates the situation when
+; recomputation of LI produces loop with different blocks order, and LA gives
+; a different result for it. The reason of this bug hasn't been found yet, but
+; the algorithm is somehow dependent on blocks order.
+define void @test_01(i32* %p) {
+; CHECK-LABEL: test_01
+; CHECK:       Report: unsafe dependent memory operations in loop.
+; CHECK-NOT:   Memory dependences are safe
+entry:
+  br label %loop
+
+loop.progress:                                              ; preds = %loop
+  br label %loop.backedge
+
+loop.backedge:                                              ; preds = %loop.progress
+  store i32 1, i32* %tmp7, align 4
+  %tmp = add nuw i64 %tmp5, 1
+  %tmp3 = icmp ult i64 %tmp, 1000
+  br i1 %tmp3, label %loop, label %loop.progress1
+
+loop:                                              ; preds = %loop.backedge, %entry
+  %tmp5 = phi i64 [ %tmp, %loop.backedge ], [ 16, %entry ]
+  %tmp6 = phi i64 [ %tmp5, %loop.backedge ], [ 15, %entry ]
+  %tmp7 = getelementptr inbounds i32, i32* %p, i64 %tmp5
+  %tmp8 = load i32, i32* %tmp7, align 4
+  %tmp9 = add i32 %tmp8, -5
+  store i32 %tmp9, i32* %tmp7, align 4
+  br i1 false, label %never, label %loop.progress
+
+never:                                             ; preds = %loop
+  unreachable
+
+loop.progress1:                                             ; preds = %loop.backedge
+  ret void
+}