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

Missed optimization when using split_first #109328

Closed
xTachyon opened this issue Mar 18, 2023 · 4 comments · Fixed by #125347
Closed

Missed optimization when using split_first #109328

xTachyon opened this issue Mar 18, 2023 · 4 comments · Fixed by #125347
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-enhancement Category: An issue proposing an enhancement or a PR with one. C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-slow Issue: Problems and improvements with respect to performance of generated code. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@xTachyon
Copy link
Contributor

Impl 1:

pub fn f(input: &mut &[u64]) -> Option<u64> {
    match input {
        [] => None,
        [first, rest @ ..] => {
            *input = rest;
            Some(*first)
        }
    }
}

Impl 2:

pub fn f(input: &mut &[u64]) -> Option<u64> {
    let (first, rest) = input.split_first()?;
    *input = rest;
    Some(*first)
}

Godbolt: https://godbolt.org/z/aasq15z7a

These functions should be equivalent, but the second function generates one more if than the first one. This also happens when using .get(0) and then doing the slicing manually. I expected the impls to generate the same code.
@xTachyon xTachyon added the C-bug Category: This is a bug. label Mar 18, 2023
@JakobDegen JakobDegen added A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. I-slow Issue: Problems and improvements with respect to performance of generated code. labels Mar 18, 2023
@JakobDegen
Copy link
Contributor

Quoting myself on Zulip:

I've seen this before too. The extra comparison is a null pointer check and is going to be the result of something creating a Option<&T>

@JakobDegen JakobDegen added C-enhancement Category: An issue proposing an enhancement or a PR with one. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. and removed C-bug Category: This is a bug. labels Mar 18, 2023
@nikic
Copy link
Contributor

nikic commented Mar 19, 2023

This is a metadata preservation failure during SimplifyCFG speculation: https://llvm.godbolt.org/z/frs8o853f

Preserving !nonnull here used to be illegal, but thanks to https://reviews.llvm.org/D141386 we are allowed to preserve it now. Only need to drop !noundef.

@nikic nikic self-assigned this Mar 22, 2023
@nikic
Copy link
Contributor

nikic commented Mar 22, 2023

Upstream patch: https://reviews.llvm.org/D146629

@TDecking TDecking mentioned this issue Apr 3, 2023
Merged
@nikic nikic added the E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. label Aug 14, 2023
@nikic nikic removed their assignment Aug 14, 2023
@nikic
Copy link
Contributor

nikic commented Aug 14, 2023

Fixed by #114048, needs codegen test.

@reez12g reez12g mentioned this issue Oct 1, 2023
Closed
@workingjubilee workingjubilee added the C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such label Oct 8, 2023
tesuji added a commit to tesuji/rustc that referenced this issue May 20, 2024
@tesuji
add codegen test for rust-lang#109328
44dce08
@tesuji tesuji mentioned this issue May 20, 2024
Merged
tesuji added a commit to tesuji/rustc that referenced this issue Jun 8, 2024
@tesuji
add codegen test for rust-lang#109328
eeffa51
tesuji added a commit to tesuji/rustc that referenced this issue Jun 9, 2024
@tesuji
add codegen test for rust-lang#109328
7d967ff
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 9, 2024
@bors
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
b7edafe 
Add codegen tests for E-needs-test

close rust-lang#36010
close rust-lang#68667
close rust-lang#74938
close rust-lang#83585
close rust-lang#93036
close rust-lang#109328
close rust-lang#110797
close rust-lang#111508
close rust-lang#112509
close rust-lang#113757
close rust-lang#120440
close rust-lang#118392
close rust-lang#71096

r? nikic
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 10, 2024
@bors
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
a1b4415 
Add codegen tests for E-needs-test

close rust-lang#36010
close rust-lang#68667
close rust-lang#74938
close rust-lang#83585
close rust-lang#93036
close rust-lang#109328
close rust-lang#110797
close rust-lang#111508
close rust-lang#112509
close rust-lang#113757
close rust-lang#120440
close rust-lang#118392
close rust-lang#71096

r? nikic
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 11, 2024
@bors
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
b1761a2 
Add codegen tests for E-needs-test

close rust-lang#36010
close rust-lang#68667
close rust-lang#74938
close rust-lang#83585
close rust-lang#93036
close rust-lang#109328
close rust-lang#110797
close rust-lang#111508
close rust-lang#112509
close rust-lang#113757
close rust-lang#120440
close rust-lang#118392
close rust-lang#71096

r? nikic
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 13, 2024
@bors
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
4936869 
Add codegen tests for E-needs-test

close rust-lang#36010
close rust-lang#68667
close rust-lang#74938
close rust-lang#83585
close rust-lang#93036
close rust-lang#109328
close rust-lang#110797
close rust-lang#111508
close rust-lang#112509
close rust-lang#113757
close rust-lang#120440
close rust-lang#118392
close rust-lang#71096

r? nikic
@bors bors closed this as completed in 7ac6c2f Jun 14, 2024
@GrigorenkoPV GrigorenkoPV mentioned this issue Jun 24, 2024
Merged
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
@matthiaskrgr
Rollup merge of rust-lang#126906 - GrigorenkoPV:fixme-split_at_first,…
4cf6f8b 
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
@matthiaskrgr
Rollup merge of rust-lang#126906 - GrigorenkoPV:fixme-split_at_first,…
6fc769b 
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
@matthiaskrgr
Rollup merge of rust-lang#126906 - GrigorenkoPV:fixme-split_at_first,…
fe1f83c 
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
rust-timer added a commit to rust-lang-ci/rust that referenced this issue Jun 30, 2024
@rust-timer
Unrolled build for rust-lang#126906
ef3d5d8 
Rollup merge of rust-lang#126906 - GrigorenkoPV:fixme-split_at_first, r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-enhancement Category: An issue proposing an enhancement or a PR with one. C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-slow Issue: Problems and improvements with respect to performance of generated code. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add codegen tests for E-needs-test tesuji/rustc
4 participants
@nikic @xTachyon @workingjubilee @JakobDegen