Missed optimization: Useless branches are kept when matching pattern

[tesuji]

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

[tesuji]

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

[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 https://github.com/rust-lang/rust/pull/81451

[Muximize]

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