# Missed optimization opportunity for bounds checks

**URL:** <https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914>\
**Category:** Uncategorized\
**Created:** [January 4, 2022, 11:11am UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914 "2022-01-04T11:11:52Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 4, 2022, 11:11am UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/1 "2022-01-04T11:11:52Z")

</div>

This code

```rust
fn sum(a: &[i32]) -> i32 {
    a[0] + a[1] + a[2]
}

```

[is compiled to](https://rust.godbolt.org/z/6MGavnofo) something with 3 bounds checks, like this:

```rust
fn sum(a: &[i32]) -> i32 {
    if a.len() == 0 {
        panic!("0 out of range");
    } else if a.len() == 1 {
        panic!("1 out of range");
    } else if a.len() == 2 {
        panic!("2 out of range");
    } else {
        unsafe { a.get_unchecked(0) + a.get_unchecked(1) + a.get_unchecked(2) }
    }
}

```

However, if LLVM can see that the first 3 cases are unlikely because they go to panic code, why doesn't it optimize it to something with only 1 bounds check on the hot path, such as:

```rust
fn sum(a: &[i32]) -> i32 {
    if a.len() < 3 {
        if a.len() == 0 {
            panic!("0 out of range");
        } else if a.len() == 1 {
            panic!("1 out of range");
        } else {
            panic!("2 out of range");
        }
    } else {
        unsafe { a.get_unchecked(0) + a.get_unchecked(1) + a.get_unchecked(2) }
    }
}

```

---

<div class="post-metadata">

**Author:** ![Neutron3529](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/neutron3529/32/6976_2.png) [@Neutron3529](https://internals.rust-lang.org/u/Neutron3529)\
**Post date:** [January 4, 2022, 11:46am UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/2 "2022-01-04T11:46:53Z")

</div>

> [@tczajka](#):
>
> ```rust
> #[inline(never)]
> fn sum(a: &[i32]) -> i32 {
> assert!(a.len()>2);
> a[0] + a[1] + a[2]
> }
> #[inline(never)]
> fn sum2(a: &[i32]) -> i32 {
> a[2] + a[1] + a[0]
> }
> 
> ```

that would do the thing you want to do

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 4, 2022, 11:50am UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/3 "2022-01-04T11:50:14Z")

</div>

> [@Neutron3529](#):
>
> that would do the thing you want to do

I understand it's possible for programmers to optimize the code manually, but that's not the point. The point is that the compiler could optimize the code as written, by itself, and is not doing it for some reason. Question is, why is it not doing it, and whether it can be fixed.

---

<div class="post-metadata">

**Author:** ![mathstuf](https://avatars.discourse-cdn.com/v4/letter/m/958977/32.png) [@mathstuf](https://internals.rust-lang.org/u/mathstuf)\
**Post date:** [January 4, 2022, 12:31pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/4 "2022-01-04T12:31:59Z")

</div>

> [@tczajka](#):
>
> The point is that the compiler could optimize the code as written, by itself, and is not doing it for some reason.

The "as-if" rule. The compiler sees this:

```rust
(a[0] + a[1]) + a[2]

```

If `a[0] + a[1]` overflows, there's a panic in there before it gets to the `[2]` indexing. Your proposed optimization changes the panic that arises in that case (for non-release builds at least). A release build could probably "see" more.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 4, 2022, 12:34pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/5 "2022-01-04T12:34:12Z")

</div>

> [@mathstuf](#):
>
> A release build could probably "see" more.

In my original post I used the release mode, see the linked compiler output. There is no addition overflow check in the assembly.

---

<div class="post-metadata">

**Author:** ![SadiinsoSnowfall](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sadiinsosnowfall/32/8495_2.png) [@SadiinsoSnowfall](https://internals.rust-lang.org/u/SadiinsoSnowfall)\
**Post date:** [January 4, 2022, 1:16pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/6 "2022-01-04T13:16:04Z")

</div>

~~AFAIK this is only a problem if "touching" the `a[2]` momory address result in a invalid access or has side effects (and this might be why LLVM doesn't completly remove all but one bound checks), but, correct me if I'm wrong, this should not be the case in (safe) Rust.~~ Nevermind, I misunderstood the problem.

---

<div class="post-metadata">

**Author:** ![elidupree](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/elidupree/32/4304_2.png) [@elidupree](https://internals.rust-lang.org/u/elidupree)\
**Post date:** [January 4, 2022, 2:54pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/7 "2022-01-04T14:54:12Z")

</div>

Previous discussion on this topic: [More musings about slices and arrays](https://internals.rust-lang.org/t/more-musings-about-slices-and-arrays/13127)

---

<div class="post-metadata">

**Author:** ![kornel](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kornel/32/2711_2.png) [@kornel](https://internals.rust-lang.org/u/kornel)\
**Post date:** [January 4, 2022, 5:12pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/8 "2022-01-04T17:12:50Z")

</div>

I think the existing compiler rules for side effects don't cover this case properly.

`panic` is still a side effect, so it can't be simply removed. It can't be freely reordered either, because you can't end up with executing the read before the panic. It can't freely moved/hoisted earlier either, because you don't want a panic from `a[x]` escape something like `if x < len { a[x] }`.

So it's a tricky case where the compiler would probably have to explicitly understand the concept of bounds checks, and track relationships between them to properly reorder them to remove redundancy.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 4, 2022, 5:24pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/9 "2022-01-04T17:24:36Z")

</div>

> [@kornel](#):
>
> It can't be freely reordered either, because you can't end up with executing the read before the panic. It can't freely moved/hoisted earlier either, because you don't want a panic from `a[x]` escape something like `if x < len { a[x] }` .

I don't think this is it. What the code actually compiles to, and what I proposed it should compile to, actually do all the same reads and panics in the same order, and neither ever attemps to read anything out of bounds.

---

<div class="post-metadata">

**Author:** ![SlightlyOutOfPhase](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/slightlyoutofphase/32/5440_2.png) [@SlightlyOutOfPhase](https://internals.rust-lang.org/u/SlightlyOutOfPhase)\
**Post date:** [January 4, 2022, 5:44pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/10 "2022-01-04T17:44:24Z")

</div>

I think it's certainly important to keep in mind that the "standalone" codegen for functions is nearly always entirely unlike the codegen seen in contexts where they're actually being called.

[See here, for example.](https://rust.godbolt.org/z/zsn81W4Ex) `rustc` optimizes both the valid and invalid calls to `sum` out entirely, instead just immediately printing the literal number 3 and then immediately panicking.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 4, 2022, 5:48pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/11 "2022-01-04T17:48:40Z")

</div>

Obviously when `a.len()` is a compile time constant then all the ifs will get constant-folded. The issue is when the length is not known at compile time.

---

<div class="post-metadata">

**Author:** ![SlightlyOutOfPhase](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/slightlyoutofphase/32/5440_2.png) [@SlightlyOutOfPhase](https://internals.rust-lang.org/u/SlightlyOutOfPhase)\
**Post date:** [January 4, 2022, 5:51pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/12 "2022-01-04T17:51:10Z")

</div>

It's still likely to not look exactly as it does in your original link. You'd have to examine various realistic uses of it to get an idea of the "average" contexual codegen quality.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [January 5, 2022, 5:15pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/13 "2022-01-05T17:15:47Z")

</div>

> [@tczajka](#):
>
> However, if LLVM can see that the first 3 cases are unlikely because they go to panic code, why doesn't it optimize it to something with only 1 bounds check on the hot path

I would suggest [opening an issue on LLVM](https://github.com/llvm/llvm-project/issues/new/choose) -- their issues are on github, now, so it's much easier than it was before.

Rust's panicking functions are marked `cold`, so this transformation should probably happen in general in LLVM for all things that lead to cold paths with only side-effect-free things between them -- not just indexing and panics.

(The panicking things being marked cold is why LLVM puts the panicking paths at the end of the assembly for the function, for example.)

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [January 5, 2022, 6:45pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/14 "2022-01-05T18:45:37Z")

</div>

> [@scottmcm](#):
>
> I would suggest [opening an issue on LLVM](https://github.com/llvm/llvm-project/issues/new/choose)

[Opened an issue on LLVM](https://github.com/llvm/llvm-project/issues/53015) .

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [April 5, 2022, 6:46pm UTC](https://internals.rust-lang.org/t/missed-optimization-opportunity-for-bounds-checks/15914/15 "2022-04-05T18:46:02Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.