[x86] Incorrect load combining causing OOB reads (and thus segfaults at runtime)

[scottmcm]

Context: Rust issue in today's 1.97 release, rust-lang/rust#159035
Rust repro with opt pipeline, https://rust.godbolt.org/z/dTPGY3rY1

Take this LLVM IR, particularly noting that %0 can be -1, 0, or 1 as conveyed by the !range attribute

define { i32, i32 } @"example[aafd2ff9cfc6cff8]::run"(ptr dead_on_return noalias nofree noundef readonly align 8 captures(none) dereferenceable(24) %c) unnamed_addr {
start:
  %0 = load i64, ptr %c, align 8, !range !4, !noundef !5
  %.not = icmp ne i64 %0, -1
  %_3.sroa.5.0.c.sroa_idx = getelementptr inbounds nuw i8, ptr %c, i64 12
  %_3.sroa.5.0.copyload = load i32, ptr %_3.sroa.5.0.c.sroa_idx, align 4
  %1 = trunc nuw i64 %0 to i1
  %2 = getelementptr inbounds nuw i8, ptr %c, i64 16
  %_3.sroa.6.0.copyload = load i32, ptr %2, align 8
  %_4.sroa.0.1 = select i1 %1, i32 %_3.sroa.6.0.copyload, i32 %_3.sroa.5.0.copyload
  %_0.sroa.3.0 = select i1 %.not, i32 %_4.sroa.0.1, i32 undef
  %_0.sroa.0.0 = zext i1 %.not to i32
  %3 = insertvalue { i32, i32 } poison, i32 %_0.sroa.0.0, 0
  %4 = insertvalue { i32, i32 } %3, i32 %_0.sroa.3.0, 1
  ret { i32, i32 } %4
}

!4 = !{i64 -1, i64 2}
!5 = !{}

Today on llc trunk that compiles to the following: https://llvm.godbolt.org/z/TcY99vhjE

"example[aafd2ff9cfc6cff8]::run":
        mov     rcx, qword ptr [rdi]
        xor     eax, eax
        cmp     rcx, -1
        setne   al
        mov     ecx, ecx
        mov     edx, dword ptr [rdi + 4*rcx + 12]
        ret

rcx there maps to %0, so it can be -1, 0, or 1 (as i64).

If it stayed that way, that would be fine, as the [rdi + 4*rcx + 12] would read 4 bytes from rdi + 8, rdi + 12, or rdi + 16, all of which are within the dereferenceable(24).

However, that mov ecx, ecx changes rcx to instead be 0x00000000FFFFFFFF, 0, or 1 (as i64), and thus the following mov reads massively out of bounds, causing a segfault.

---

Apologies in advance if I got the logic chain wrong here somewhere. I'm reasonably good at middle-end IR but worse at assembly and completely unfamiliar with backend IR.

I think this is x86-specific because it was reported that neither aarch64 nor riscv64gc hit a problem here (Rust Zulip #t-compiler > Miscompilation in 1.97.0 with new Option::None discriminant @ 💬).

[llvmorg-github-actions]

@llvm/issue-subscribers-backend-x86

Author: scottmcm

Details

Context: Rust issue in today's 1.97 release, https://github.com/rust-lang/rust/issues/159035 Rust repro with opt pipeline, https://rust.godbolt.org/z/dTPGY3rY1

Take this LLVM IR, particularly noting that %0 can be -1, 0, or 1 as conveyed by the !range attribute

define { i32, i32 } @"example[aafd2ff9cfc6cff8]::run"(ptr dead_on_return noalias nofree noundef readonly align 8 captures(none) dereferenceable(24) %c) unnamed_addr {
start:
  %0 = load i64, ptr %c, align 8, !range !4, !noundef !5
  %.not = icmp ne i64 %0, -1
  %_3.sroa.5.0.c.sroa_idx = getelementptr inbounds nuw i8, ptr %c, i64 12
  %_3.sroa.5.0.copyload = load i32, ptr %_3.sroa.5.0.c.sroa_idx, align 4
  %1 = trunc nuw i64 %0 to i1
  %2 = getelementptr inbounds nuw i8, ptr %c, i64 16
  %_3.sroa.6.0.copyload = load i32, ptr %2, align 8
  %_4.sroa.0.1 = select i1 %1, i32 %_3.sroa.6.0.copyload, i32 %_3.sroa.5.0.copyload
  %_0.sroa.3.0 = select i1 %.not, i32 %_4.sroa.0.1, i32 undef
  %_0.sroa.0.0 = zext i1 %.not to i32
  %3 = insertvalue { i32, i32 } poison, i32 %_0.sroa.0.0, 0
  %4 = insertvalue { i32, i32 } %3, i32 %_0.sroa.3.0, 1
  ret { i32, i32 } %4
}

!4 = !{i64 -1, i64 2}
!5 = !{}

Today on llc trunk that compiles to the following: <https://llvm.godbolt.org/z/TcY99vhjE>

"example[aafd2ff9cfc6cff8]::run":
        mov     rcx, qword ptr [rdi]
        xor     eax, eax
        cmp     rcx, -1
        setne   al
        mov     ecx, ecx
        mov     edx, dword ptr [rdi + 4*rcx + 12]
        ret

rcx there maps to %0, so it can be -1, 0, or 1 (as i64).

If it stayed that way, that would be fine, as the [rdi + 4*rcx + 12] would read 4 bytes from rdi + 8, rdi + 12, or rdi + 16, all of which are within the dereferenceable(24).

However, that mov ecx, ecx changes rcx to instead be 0x00000000FFFFFFFF, 0, or 1 (as i64), and thus the following mov reads massively out of bounds, causing a segfault.

---

Apologies in advance if I got the logic chain wrong here somewhere. I'm reasonably good at middle-end IR but worse at assembly and completely unfamiliar with backend IR.

I think this is x86-specific because it was reported that neither aarch64 nor riscv64gc hit a problem here (Rust Zulip #t-compiler > Miscompilation in 1.97.0 with new Option::None discriminant @ 💬).

[workingjubilee]

Note that it seems to also be x86-64 related, as it doesn't seem to produce the fault on i686. But maybe that's naive and the issue is present but merely latent, subject to the size of the values in question.

[scottmcm]

That example above does seem to be related to the ecx/rcx mixing, which indeed is x64-only.

---

@theemathas found another version that manifest slightly differently -- and slightly more concerningly. Original Rust: https://rust.godbolt.org/z/coq96Ej41, this time from Rust 1.96

Take this LLVM-IR:

define { i64, i64 } @"example[aafd2ff9cfc6cff8]::run"(ptr dead_on_return noalias nofree noundef readonly align 8 captures(none) dereferenceable(24) %c) unnamed_addr #0 {
start:
  %0 = load i16, ptr %c, align 8, !range !3, !noundef !4
  %.not = icmp ne i16 %0, 2  ; <-- note the 2 instead of the -1
  %x.sroa.51.0.c.sroa_idx = getelementptr inbounds nuw i8, ptr %c, i64 8
  %x.sroa.51.0.copyload = load i64, ptr %x.sroa.51.0.c.sroa_idx, align 8
  %1 = trunc nuw i16 %0 to i1
  %x.sroa.7.0.c.sroa_idx = getelementptr inbounds nuw i8, ptr %c, i64 16
  %x.sroa.7.0.copyload = load i64, ptr %x.sroa.7.0.c.sroa_idx, align 8
  %s.sroa.0.0 = select i1 %1, i64 %x.sroa.7.0.copyload, i64 %x.sroa.51.0.copyload
  %_0.sroa.3.0 = select i1 %.not, i64 %s.sroa.0.0, i64 undef
  %_0.sroa.0.0 = zext i1 %.not to i64
  %2 = insertvalue { i64, i64 } poison, i64 %_0.sroa.0.0, 0
  %3 = insertvalue { i64, i64 } %2, i64 %_0.sroa.3.0, 1
  ret { i64, i64 } %3
}

!3 = !{i16 0, i16 3}
!4 = !{}

Which llc trunk compiles to https://llvm.godbolt.org/z/MacjYhebd

"example[aafd2ff9cfc6cff8]::run":
        movzx   ecx, word ptr [rdi]
        xor     eax, eax
        cmp     ecx, 2
        setne   al
        mov     rdx, qword ptr [rdi + 8*rcx + 8]
        ret

Now %0 is !range !{i16 0, i16 3}, and thus ecx is 0/1/2 zero-extended from 16-bit to 32-bit.

But that means the ending mov can read a qword from rdi + 8*2 + 8 ⇒ rdi + 24, which is an out-of-bounds read for the input that's only dereferenceable(24). (Note that the two loads in the middle-end LLVM IR were at offsets 8 and 16.

---

Potential idea: Is the backend incorrectly depending on the trunc nuw to decide that %0 is only 0/1? I don't think it's legal for it to do that, because IIUC that's just a poison that's fully defanged by another select ignoring it (to turn it into a returned undef).

Certainly if I replace the trunc nuw with just trunc then the output gets and ecx, 1 which makes it no longer out-of-bounds.

[nikic]

I believe the problematic transform is https://github.com/llvm/llvm-project/blob/83c5973a0a9e849efdec168a1b712f355e59ff4c/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L30436, which fails to account for the condition being poison.