Skip to content

Rust generates suboptimal code for x.div_euclid(2) #118392

@LunaBorowska

Description

@LunaBorowska
Contributor

I tried this code:

pub fn div2(a: i32) -> i32 {
    a.div_euclid(2)
}

I expected to see this happen:

After compiling to assembly with -C opt-level=3 to generate the following x86 assembly code.

div2:
        mov     eax, edi
        sar     eax
        ret

Instead, this happened:

div2:
        mov     eax, edi
        shr     eax, 31
        add     eax, edi
        sar     eax
        not     edi
        and     edi, -2147483647
        cmp     edi, 1
        sbb     eax, 0
        ret

Meta

rustc --version --verbose:

rustc 1.74.0 (79e9716c9 2023-11-13)
binary: rustc
commit-hash: 79e9716c980570bfd1f666e3b16ac583f0168962
commit-date: 2023-11-13
host: x86_64-unknown-linux-gnu
release: 1.74.0
LLVM version: 17.0.4

Activity

added
needs-triageThis issue may need triage. Remove it if it has been sufficiently triaged.
on Nov 27, 2023
Urgau

Urgau commented on Nov 27, 2023

@Urgau
Member

Those are not equivalent! (EDIT: was wrong, see below) div_euclid say it it will round towards negative infinity if self < 0; while self / 2 always rounds towards positive infinity.

A simple playground example with -7 proves that they do not return the same value:

fn main() {
    assert_eq!(
        (-7i32) / 2, // -3 
        (-7i32).div_euclid(2) // -4
    );
}

However if you use u32 (or any unsigned integer) you will get the expected assembly.

@rustbot labels -C-bug -needs-triage +C-discussion

added
C-discussionCategory: Discussion or questions that doesn't represent real issues.
and removed
C-bugCategory: This is a bug.
needs-triageThis issue may need triage. Remove it if it has been sufficiently triaged.
on Nov 27, 2023
LunaBorowska

LunaBorowska commented on Nov 27, 2023

@LunaBorowska
ContributorAuthor

Those are not equivalent!

@Urgau I believe x.div_euclid(2) and x >> 1 (not to be confused with x / 2) are in fact equivalent, and Alive2 tells me that this optimization is valid (https://alive2.llvm.org/ce/z/YVeJvZ), albeit I tested it with i8 (testing with i32 gets a timeout).

x / 2 on the other hand compiles down to the following:

div2:
        mov     eax, edi
        shr     eax, 31
        add     eax, edi
        sar     eax
        ret

Note how the generated code adds sign bit, which is correct. x / 2 is not the same thing as x >> 1 specifically because it rounds towards 0, and not negative infinity.

Jules-Bertholet

Jules-Bertholet commented on Nov 28, 2023

@Jules-Bertholet
Contributor

@rustbot labels +C-bug +needs-triage -C-discussion I-heavy I-slow A-LLVM A-codegen T-compiler

added
A-codegenArea: Code generation
A-LLVMArea: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues.
C-bugCategory: This is a bug.
I-heavyIssue: Problems and improvements with respect to binary size of generated code.
I-slowIssue: Problems and improvements with respect to performance of generated code.
needs-triageThis issue may need triage. Remove it if it has been sufficiently triaged.
and removed
C-discussionCategory: Discussion or questions that doesn't represent real issues.
on Nov 28, 2023

2 remaining items

nikic

nikic commented on Nov 28, 2023

@nikic
Contributor

LLVM issue: llvm/llvm-project#73622 Worth noting that the problem only occurs with 2, not other power of two constants.

Urgau

Urgau commented on Nov 28, 2023

@Urgau
Member

@Urgau I believe x.div_euclid(2) and x >> 1 (not to be confused with x / 2) are in fact equivalent, and Alive2 tells me that this optimization is valid (https://alive2.llvm.org/ce/z/YVeJvZ), albeit I tested it with i8 (testing with i32 gets a timeout).

My bad, I wrongly deduced that you meant x / 2 not x >> 1. I even checked under Alive2. 👀

added
llvm-fixed-upstreamIssue expected to be fixed by the next major LLVM upgrade, or backported fixes
on Nov 30, 2023
nikic

nikic commented on Feb 14, 2024

@nikic
Contributor

Confirmed fixed by #120055, needs codegen test.

added
E-needs-testCall for participation: An issue has been fixed and does not reproduce, but no test has been added.
and removed
llvm-fixed-upstreamIssue expected to be fixed by the next major LLVM upgrade, or backported fixes
on Feb 14, 2024
added 5 commits that reference this issue on Jun 9, 2024
b7edafe
a1b4415
b1761a2
4936869
7ac6c2f
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

    A-LLVMArea: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues.A-codegenArea: Code generationC-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-heavyIssue: Problems and improvements with respect to binary size of generated code.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

      Participants

      @nikic@LunaBorowska@Urgau@saethlin@rustbot

      Issue actions

        Rust generates suboptimal code for x.div_euclid(2) · Issue #118392 · rust-lang/rust