Skip to content

Missed optimization: Useless branches are kept when matching pattern #74183

Open
@tesuji

Description

@tesuji
Contributor

EDIT: this is now reasonably optimized: https://rust.godbolt.org/z/nP599MaKM
So it just needs tests: @rustbot label +E-needs-test


I tried this code: https://rust.godbolt.org/z/hP3YKe

The code below does not compile because I strip some code, try the godbolt link above:

const fn doc_comment_kind(s: &str) -> Option<(DocCommentKind, AttrStyle)> {
    match s.as_bytes() {
        [b'/', b'/', b'/', b'/', ..] => None,
        [b'/', b'/', b'/', ..] => Some((DocCommentKind::Line, AttrStyle::Inner)),
        [b'/', b'/', b'!', ..] => Some((DocCommentKind::Line, AttrStyle::Outer)),
        [b'/', b'*', b'*', b'*', _, ..] => None,
        [b'/', b'*', b'*', _, _, ..] => Some((DocCommentKind::Block, AttrStyle::Inner)),
        [b'/', b'*', b'!', _, _, ..] => Some((DocCommentKind::Block, AttrStyle::Outer)),
        _ => None,
    }
}

pub const fn is_line_doc_comment(s: &str) -> bool {
    match doc_comment_kind(s) {
        Some((DocCommentKind::Line, _)) => true,
        _ => false
    }
}

I expected to see this happen:
The generated code of is_line_doc_comment should be optimized out useless branches.
And it should be equivalent to this function:

pub const fn is_line_doc_comment_2(s: &str) -> bool {
    match s.as_bytes() {
        [b'/', b'/', b'/', b'/', ..] => false,
        [b'/', b'/', b'/', ..] => true,
        [b'/', b'/', b'!', ..] => true,
        _ => false,
    }
}

How would the two is_line_doc_comment functions be able to generate the same code?

When doc_comment_kind inlined in is_line_doc_comment,
the optimizer could see that

  • Some((DocCommentKind::Block, _)) branches are useless and remove it
const fn doc_comment_kind(s: &str) -> Option<(DocCommentKind, AttrStyle)> {
    match s.as_bytes() {
        [b'/', b'/', b'/', b'/', ..] => None,
        [b'/', b'/', b'/', ..] => Some((DocCommentKind::Line, AttrStyle::Inner)),
        [b'/', b'/', b'!', ..] => Some((DocCommentKind::Line, AttrStyle::Outer)),
        [b'/', b'*', b'*', b'*', _, ..] => None,
        _ => None,
    }
}
  • is_line_doc_comment doesn't care about AttrStyle,
const fn doc_comment_kind(s: &str) -> Option<DocCommentKind> {
    match s.as_bytes() {
        [b'/', b'/', b'/', b'/', ..] => None,
        [b'/', b'/', b'/', ..] => Some(DocCommentKind::Line),
        [b'/', b'/', b'!', ..] => Some(DocCommentKind::Line),
        [b'/', b'*', b'*', b'*', _, ..] => None,
        _ => None,
    }
}
  • The first branch overlaps with second branch of DocCommentKind::Line branches,
    keep this branch.

  • Other None branches don't overlap, just make them as fallback:

const fn doc_comment_kind(s: &str) -> Option<DocCommentKind> {
    match s.as_bytes() {
        [b'/', b'/', b'/', b'/', ..] => None,
        [b'/', b'/', b'/', ..] => Some(DocCommentKind::Line),
        [b'/', b'/', b'!', ..] => Some(DocCommentKind::Line),
        _ => None,
    }
}

Final result: https://rust.godbolt.org/z/jrPGr7

Instead, this happened:
The generated code still keeps some useless branches.
Maybe I am just asking too much from optimizer.

Meta

rustc --version --verbose:

rustc 1.46.0-nightly (8aa18cbdc 2020-07-08)
binary: rustc
commit-hash: 8aa18cbdc5d4bc33bd61e2d9a4b643d87f5d21de
commit-date: 2020-07-08
host: x86_64-unknown-linux-gnu
release: 1.46.0-nightly
LLVM version: 10.0

Activity

tesuji

tesuji commented on Jul 9, 2020

@tesuji
ContributorAuthor

cc @nikic @cuviper as you are often involved in these issues.

changed the title [-]Useless branches are kept when matching pattern[/-] [+]Missing optimization: Useless branches are kept when matching pattern[/+] on Jul 9, 2020
changed the title [-]Missing optimization: Useless branches are kept when matching pattern[/-] [+]Missed optimization: Useless branches are kept when matching pattern[/+] on Jul 9, 2020
added
I-slowIssue: Problems and improvements with respect to performance of generated code.
T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.
on Jul 9, 2020
MSxDOS

MSxDOS commented on Jul 19, 2020

@MSxDOS

This is most likely related to the fact that Rust\LLVM doesn't optimize out unused match branches for non-inline functions: https://rust.godbolt.org/z/TPY69b
As you can see, both the code and data for all five variants are present even though only two of them are ever used.

In C++ the story is the same on clang and MSVC, but GCC does optimize those out with -O3:
https://godbolt.org/z/G6T9Y8

EDIT: In Rust example the unused branches are removed on nightly, could be #81451

Muximize

Muximize commented on Mar 13, 2021

@Muximize

Do edits trigger notifications? Aka did @tesuji get notified of this edit 20 hours ago? If so, sorry for the double ping.

added
E-needs-testCall for participation: An issue has been fixed and does not reproduce, but no test has been added.
on May 25, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-bugCategory: This is a bug.E-needs-testCall for participation: An issue has been fixed and does not reproduce, but no test has been added.I-slowIssue: Problems and improvements with respect to performance of generated code.T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @jonas-schievink@Muximize@tesuji@MSxDOS@rustbot

        Issue actions

          Missed optimization: Useless branches are kept when matching pattern · Issue #74183 · rust-lang/rust