Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[BasicAA] Incorrect AA result due to overflow #63266

Closed
nikic opened this issue Jun 12, 2023 · 2 comments
Closed

[BasicAA] Incorrect AA result due to overflow #63266

nikic opened this issue Jun 12, 2023 · 2 comments

Comments

@nikic
Copy link
Contributor

nikic commented Jun 12, 2023

; RUN: opt -passes=aa-eval -print-all-alias-modref-info < %s
define void @test(i1 %c, ptr %base) {
entry:
  %offset16 = getelementptr inbounds i8, ptr %base, i64 16
  %gep1 = getelementptr i8, ptr %base, i64 -9223372036854775792
  br i1 %c, label %if, label %join

if:
  br label %join

join:
  %phi = phi i64 [ -9223372036854775808, %if ], [ 0, %entry ]
  %gep2 = getelementptr i8, ptr %gep1, i64 %phi
  store i8 0, ptr %gep2
  load i8, ptr %offset16
  ret void
}

Produces:

  NoAlias:	i8* %gep2, i8* %offset16

Which is incorrect.

@nikic
Copy link
Contributor Author

nikic commented Jun 12, 2023

The post-subtract decomposed GEP is:

(DecomposedGEP Base=base, Offset=-9223372036854775808, VarIndices=[(V=phi, zextbits=0, sextbits=0, truncbits=0, scale=-1)])

What this doesn't tell you is that the index has IsNSW set, which is incorrect, because we'll end up multiplying INT_MIN by -1. This ultimately results in incorrectly computed offset ranges.

This is because

VariableGEPIndex Entry = {Src.Val, -Src.Scale, Src.CxtI, Src.IsNSW};
always preserves the IsNSW flag when negating the scale.

Just dropping the NSW flag there may be quite problematic though, because this cause symmetry issues, where we produce different results depending on the order of the GEPs, and which one will contribute the negative scales.

@nikic
Copy link
Contributor Author

nikic commented Jun 19, 2023

Candidate patch: https://reviews.llvm.org/D153270

@nikic nikic closed this as completed in c31eb82 Jun 27, 2023
Chenyang-L pushed a commit to intel/llvm that referenced this issue Jul 11, 2023
We currently preserve the nsw flag when negating scales, which is
incorrect for INT_MIN.

However, just dropping the NSW flag in this case makes BasicAA
behavior unreliable and asymmetric, because we may or may not
drop the NSW flag depending on which side gets subtracted.

Instead, leave the Scale alone and add an additional IsNegated flag,
which indicates that the whole VarIndex should be interpreted as a
subtraction. This allows us to retain the NSW flag.

When accumulating the offset range, we need to use subtraction
instead of adding for IsNegated indices. Everything else works on
the absolute value of the scale, so the negation does not matter
there.

Fixes llvm/llvm-project#63266.

Differential Revision: https://reviews.llvm.org/D153270
veselypeta pushed a commit to veselypeta/cherillvm that referenced this issue Sep 2, 2024
We currently preserve the nsw flag when negating scales, which is
incorrect for INT_MIN.

However, just dropping the NSW flag in this case makes BasicAA
behavior unreliable and asymmetric, because we may or may not
drop the NSW flag depending on which side gets subtracted.

Instead, leave the Scale alone and add an additional IsNegated flag,
which indicates that the whole VarIndex should be interpreted as a
subtraction. This allows us to retain the NSW flag.

When accumulating the offset range, we need to use subtraction
instead of adding for IsNegated indices. Everything else works on
the absolute value of the scale, so the negation does not matter
there.

Fixes llvm/llvm-project#63266.

Differential Revision: https://reviews.llvm.org/D153270
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants