llvm / llvm/llvm-project

[DependenceAnalysis] Incorrect result with single iteration scoped alias metadata

Open
#223,173 2 comments 0 reactions 0 assignees View on GitHub
llvm:analysis miscompilation
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```llvm
; RUN: opt -passes='print' < %s
define void @f(ptr %A, i64 %n) {
entry:
br label %loop

loop:
%i = phi i64 [ 1, %entry ], [ %i.next, %loop ]
call void @llvm.experimental.noalias.scope.decl(metadata !2)
%im1 = add nsw i64 %i, -1
%src = getelementptr inbounds i32, ptr %A, i64 %im1
%v = load i32, ptr %src, align 4, !alias.scope !2
%v1 = add i32 %v, 1
%dst = getelementptr inbounds i32, ptr %A, i64 %i
store i32 %v1, ptr %dst, align 4, !noalias !2
%i.next = add nsw i64 %i, 1
%c = icmp slt i64 %i.next, %n
br i1 %c, label %loop, label %exit

exit:
ret void
}

!0 = !{!0}
!1 = !{!1, !0}
!2 = !{!1}
```
This reports a `none` dependence between the load and store. It should be an `anti` dependence.

There is no UB because the load and store access different locations within one iteration. (It would be UB if the noalias.scope.decl were outside the loop.)

LAA has special code to handle this correctly: https://github.com/llvm/llvm-project/blob/eb9844b5ceee01c9d9fad92cbcd027c5798c5ed4/llvm/lib/Analysis/LoopAccessAnalysis.cpp#L982

I believe that currently this miscompile is theoretical, because LoopInterchange will not interchange loops containing noalias.scope.decl in the first place.

Based on https://github.com/llvm/llvm-project/pull/222686#issuecomment-5647760268.

Contributor guide

Open the contributing guide

Research direction

Reproduce the report with the supplied LLVM IR and `opt -passes='print'`, then inspect the scoped-alias handling in `llvm/lib/Analysis/LoopAccessAnalysis.cpp` around the referenced code. Compare the dependence-analysis result for the load and store with the expected `anti` dependence, and add or update a focused regression test showing that result.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.