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.

Sign up for GitHub

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

Jump to bottom

incorrect reassociation at low bitwidth #91417

Closed
regehr opened this issue May 8, 2024 · 1 comment · Fixed by #91469
Closed

incorrect reassociation at low bitwidth #91417

regehr opened this issue May 8, 2024 · 1 comment · Fixed by #91469
Assignees
@dtcxzyw
Labels
llvm:transforms miscompilation

Comments

@regehr
Copy link
Contributor

regehr commented May 8, 2024

here's a function:

define i3 @f(i3 %0) {
  %2 = mul i3 %0, %0
  %3 = mul i3 %2, %0
  %4 = mul i3 %3, %0
  %5 = mul nsw i3 %4, %0
  ret i3 %5
}

reassociate seems to be getting it wrong:

Johns-MacBook-Pro:reduce regehr$ ~/alive2-regehr/build/alive-tv reduced.ll -passes=reassociate

----------------------------------------
define i3 @f(i3 %#0) {
#1:
  %#2 = mul i3 %#0, %#0
  %#3 = mul i3 %#2, %#0
  %#4 = mul i3 %#3, %#0
  %#5 = mul nsw i3 %#4, %#0
  ret i3 %#5
}
=>
define i3 @f(i3 %#0) {
#1:
  %#2 = mul i3 %#0, %#0
  %#3 = mul nsw i3 %#2, %#0
  ret i3 %#3
}
Transformation doesn't verify!

ERROR: Target is more poisonous than source

Example:
i3 %#0 = #x6 (6, -2)

Source:
i3 %#2 = #x4 (4, -4)
i3 %#3 = #x0 (0)
i3 %#4 = #x0 (0)
i3 %#5 = #x0 (0)

Target:
i3 %#2 = #x4 (4, -4)
i3 %#3 = poison
Source value: #x0 (0)
Target value: poison

Summary:
  0 correct transformations
  1 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors
Johns-MacBook-Pro:reduce regehr$

cc @nunoplopes
@dtcxzyw dtcxzyw self-assigned this May 8, 2024
@dtcxzyw
Copy link
Member

dtcxzyw commented May 8, 2024

Introduced by d7aeefe.

@dtcxzyw dtcxzyw mentioned this issue May 8, 2024
Merged
dtcxzyw added a commit that referenced this issue May 29, 2024
@dtcxzyw
[Reassociate] Drop weight reduction to fix issue 91417 (#91469)
3bcccb6 
See the following case: https://alive2.llvm.org/ce/z/A-fBki
```
define i3 @src(i3 %0) {
  %2 = mul i3 %0, %0
  %3 = mul i3 %2, %0
  %4 = mul i3 %3, %0
  %5 = mul nsw i3 %4, %0
  ret i3 %5
}

define i3 @tgt(i3 %0) {
  %2 = mul i3 %0, %0
  %5 = mul nsw i3 %2, %0
  ret i3 %5
}
```


d7aeefe
introduced weight reduction during weights combination of the same
operand. As the weight of `%0` changes from 5 to 3, the nsw flag in `%5`
should be dropped.

However, the nsw flag isn't cleared by `RewriteExprTree` since `%5 = mul
nsw i3 %0, %4` is not included in the range of `[ExpressionChangedStart,
ExpressionChangedEnd)`.
```
Calculated Rank[] = 3
Combine negations for:   %2 = mul i3 %0, %0
Calculated Rank[] = 4
Combine negations for:   %3 = mul i3 %0, %2
Calculated Rank[] = 5
Combine negations for:   %4 = mul i3 %0, %3
Calculated Rank[] = 6
Combine negations for:   %5 = mul nsw i3 %0, %4
LINEARIZE:   %5 = mul nsw i3 %0, %4
OPERAND: i3 %0 (1)
ADD USES LEAF: i3 %0 (1)
OPERAND:   %4 = mul i3 %0, %3 (1)
DIRECT ADD:   %4 = mul i3 %0, %3 (1)
OPERAND: i3 %0 (1)
OPERAND:   %3 = mul i3 %0, %2 (1)
DIRECT ADD:   %3 = mul i3 %0, %2 (1)
OPERAND: i3 %0 (1)
OPERAND:   %2 = mul i3 %0, %0 (1)
DIRECT ADD:   %2 = mul i3 %0, %0 (1)
OPERAND: i3 %0 (1)
OPERAND: i3 %0 (1)
RAIn:   mul i3  [ %0, #3] [ %0, #3] [ %0, #3] 
RAOut:  mul i3  [ %0, #3] [ %0, #3] [ %0, #3] 
RAOut after CSE reorder:        mul i3  [ %0, #3] [ %0, #3] [ %0, #3] 
RA:   %5 = mul nsw i3 %0, %4
TO:   %5 = mul nsw i3 %4, %0
RA:   %4 = mul i3 %0, %3
TO:   %4 = mul i3 %0, %0
```

The best way to fix this is to inform `RewriteExprTree` to clear flags
of the whole expr tree when weight reduction happens.

But I find that weight reduction based on Carmichael number never
happens in practice.
See the coverage result
https://dtcxzyw.github.io/llvm-opt-benchmark/coverage/home/dtcxzyw/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp.html#L323

I think it would be better to drop `IncorporateWeight`.

Fixes #91417
vg0204 pushed a commit to vg0204/llvm-project that referenced this issue May 29, 2024
@dtcxzyw @vg0204
[Reassociate] Drop weight reduction to fix issue 91417 (llvm#91469)
0da0e21 
See the following case: https://alive2.llvm.org/ce/z/A-fBki
```
define i3 @src(i3 %0) {
  %2 = mul i3 %0, %0
  %3 = mul i3 %2, %0
  %4 = mul i3 %3, %0
  %5 = mul nsw i3 %4, %0
  ret i3 %5
}

define i3 @tgt(i3 %0) {
  %2 = mul i3 %0, %0
  %5 = mul nsw i3 %2, %0
  ret i3 %5
}
```


llvm@d7aeefe
introduced weight reduction during weights combination of the same
operand. As the weight of `%0` changes from 5 to 3, the nsw flag in `%5`
should be dropped.

However, the nsw flag isn't cleared by `RewriteExprTree` since `%5 = mul
nsw i3 %0, %4` is not included in the range of `[ExpressionChangedStart,
ExpressionChangedEnd)`.
```
Calculated Rank[] = 3
Combine negations for:   %2 = mul i3 %0, %0
Calculated Rank[] = 4
Combine negations for:   %3 = mul i3 %0, %2
Calculated Rank[] = 5
Combine negations for:   %4 = mul i3 %0, %3
Calculated Rank[] = 6
Combine negations for:   %5 = mul nsw i3 %0, %4
LINEARIZE:   %5 = mul nsw i3 %0, %4
OPERAND: i3 %0 (1)
ADD USES LEAF: i3 %0 (1)
OPERAND:   %4 = mul i3 %0, %3 (1)
DIRECT ADD:   %4 = mul i3 %0, %3 (1)
OPERAND: i3 %0 (1)
OPERAND:   %3 = mul i3 %0, %2 (1)
DIRECT ADD:   %3 = mul i3 %0, %2 (1)
OPERAND: i3 %0 (1)
OPERAND:   %2 = mul i3 %0, %0 (1)
DIRECT ADD:   %2 = mul i3 %0, %0 (1)
OPERAND: i3 %0 (1)
OPERAND: i3 %0 (1)
RAIn:   mul i3  [ %0, llvm#3] [ %0, llvm#3] [ %0, llvm#3] 
RAOut:  mul i3  [ %0, llvm#3] [ %0, llvm#3] [ %0, llvm#3] 
RAOut after CSE reorder:        mul i3  [ %0, llvm#3] [ %0, llvm#3] [ %0, llvm#3] 
RA:   %5 = mul nsw i3 %0, %4
TO:   %5 = mul nsw i3 %4, %0
RA:   %4 = mul i3 %0, %3
TO:   %4 = mul i3 %0, %0
```

The best way to fix this is to inform `RewriteExprTree` to clear flags
of the whole expr tree when weight reduction happens.

But I find that weight reduction based on Carmichael number never
happens in practice.
See the coverage result
https://dtcxzyw.github.io/llvm-opt-benchmark/coverage/home/dtcxzyw/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp.html#L323

I think it would be better to drop `IncorporateWeight`.

Fixes llvm#91417
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@dtcxzyw dtcxzyw

Labels
llvm:transforms miscompilation
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[Reassociate] Drop weight reduction to fix issue 91417 dtcxzyw/llvm-project
3 participants
@regehr @EugeneZelenko @dtcxzyw