Wishlist: MIR-level integer range analysis

@oli-obk

This is a tracking issue for MIR-level integer range analysis.
I'm very new to this, and there's no associated PR (yet!) nor RFC, so apologies in advance for any issues or mistakes.

Description

Integration of integer range analysis into the MIR will allow the compiler to, on a best effort basis, understand roughly the range of values any particular expression can take on.

let x: u8 = ...; // VRange(0, 255)
let b = x / 2; // VRange(0, 127)
assert!(b < 128); // Elideable, rustc understands b cannot be larger than 128.
                  // Removal of assert can be done at a MIR level instead of by LLVM!
let c = b << 2; // VRange(0, 255). Could theoretically be recognized as VRange(0, 0) + VRange(4, 255) at the cost of extra complexity.
assert!(c != 3); // Theoretically elidable, more complicated in practice, but plenty doable.

Steps

Initial implementation (gated)

Unresolved Questions

How much should the compiler attempt to do? There is, theoretically, a very large number of situations it could recognize.
Should there be some way to access this best effort range data? It has it's uses, but the fact that this information is best-effort and not consistent would need special emphasis. Either way, an intrinsic in core would be helpful for writing unit tests.

@oli-obk per request.

Integer range analysis will get better once we have ranged integers in the Rust type system (similar to Ada ones, for for integral values only).

that's for the type system, and while that will make it easier for optimizations to handle such things, a basic version just as an optimization will give benefits to all existing cases

cc @rust-lang/wg-mir-opt

@oli-obk

I opened this issue as i have a decent level of interest in trying to produce an initial implementation. @oli-obk You said you would write something up. Once you do make sure to mention me.

@moonheart08

I think we can start out with the integer range analysis being its own MIR pass and only later integrating it with const propagation. I'd put the new MIR pass right after const propagation, so we get a good starting point from which to run said analysis.
For creating a new MIR pass I wrote a quickstart guide on zulip (that we should probably put into the rustc guide): https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/multiple.20return.20terminators/near/203699347

The MIR dataflow framework resides in https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/index.html

The relevant traits are AnalysisDomain and Analysis.

AnalysisDomain specifies the datastructures and join operation (via https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/lattice/trait.JoinSemiLattice.html) that your analysis will use, while the Analysis will perform the actual operations (e.g. copying for assignments, or moving the legal range on additions and similar).

For the only example where we use this kind of analysis in rustc look at

rust/compiler/rustc_mir/src/dataflow/impls/mod.rs

Line 471 in 0e2c128

type Domain = lattice::Dual<BitSet<MovePathIndex>>;

which, when you follow the lattice::Dual type should give you some examples on how to implement the appropriate traits for whatever datastructure you choose for representing the integer range. Since you need to track the integer range for each local, you're going to need something like FxHashMap<Local, YourState>

In general, I would expect that the MIR optimization would create your analysis, for which both the analysis traits and the https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/visit/trait.MutVisitor.html trait are implemented. You then implement the visitor's methods for the sites you want to check for possibly mutating it. I think as an MVP we should just look at Terminator where the kind is SwitchInt. You then fast forward the dataflow analysis to the current location and check its status, if that status allows eliminating targets from the terminator, then you drop them.

A test example that would work here is

fn foo(x: bool) -> &'static str {
    match x as u8 {
        0 => "null",
        1 => "one",
        2 => "meh",
        _ => "muh",
    }
}

The final mir should only contain the 0 and 1 arms.

cc @moonheart08

cc @ecstatic-morse in case I'm talking nonsense somewhere

It would be good to look at lattice::FlatSet, since it's the only (interesting) lattice that doesn't use set inclusion as the ordering operator at the moment (your Range lattice will be the second). Also, IndexVec<Local, T> implements JoinSemiLattice as long as T does. If you want to do the same for FxHashMap, just have a look at that impl.

Also, there was some brief discussion about convergence on Zulip (search for "widening"), since a lattice on set of all possible integer ranges is quite tall . There's no one solution to this, so you'll need to pick an approach.

@oli-obk

For creating a new MIR pass I wrote a quickstart guide on zulip (that we should probably put into the rustc guide): https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/multiple.20return.20terminators/near/203699347

@oli-obk Did that ever end up in the dev-guide? If not, I can try to put it there :)

Not as far as I know. That would be great! Thanks.

@rustbot

Visiting for T-compiler steering meeting backlog bonanza.

This is tagged C-tracking-issue, but it is not a tracking issue in the sense that that label is meant for. (The C-tracking-issue label is meant to tag issues that we want ongoing knowledge of their current state, for e.g. coordination within the team or across the project.)

Removing label.

@rustbot label: -C-tracking-issue

@alex-j-wang

Hi all, @alex-j-wang and I would like to pick this up.

We're currently working on a design/implementation and expect to have a draft PR in ~2 weeks. The current prototype removes unreachable match branches, prunes assert statements, and performs constant propagation when singleton values can be determined. We haven’t implemented widening/narrowing or loop handling yet.

If anyone is interested in reviewing or has concerns about the direction, we’d really appreciate early feedback. Thanks!

My main concern/question is how it relates to GVN. I want to avoid duplicating logic or calling GVN and another pass in a loop until nothing more changes.

IMO, as an alternative, #148443 that use GVN for range calculation can be more general.

@qiaochloe

FYI @qiaochloe, I have seen your great work in https://github.com/qiaochloe/rust-range-analysis. I'm doing another range analysis in #150192 and #148443, but this is a different approach. I use SSA (or GVN) rather than the dataflow framework. They are not conflicted.

@oli-obk

@oli-obk The MIR pass we're currently working on does not interact with or call GVN at all (similar to dataflow_const_prop). We were thinking that dataflow_const_prop would run first and modify the body, so logic won't be duplicated.

@dianqk Thanks for checking it out! We're not too sure about the practicality of our approach compared to integrating it into dataflow_const_prop or working with SSA/GVN. Our branch passes current Rust tests, but we see neutral performance change when running ./x perf locally. We're thinking that the overhead of path sensitivity might be contributing to this, so we have to do some more testing.

Would it be helpful to discuss this on Zulip, or would a Zoom meeting or continuing here on GitHub work better?

Would it be helpful to discuss this on Zulip, or would a Zoom meeting or continuing here on GitHub work better?

I think #t-compiler/mir-opts is fine.

Navigation Menu

Repository navigation

Wishlist: MIR-level integer range analysis #76579

Description

Steps

Unresolved Questions

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Wishlist: MIR-level integer range analysis #76579

Description

Description

Steps

Unresolved Questions

Activity

leonardo-m commented on Sep 10, 2020

oli-obk commented on Sep 10, 2020

moonheart08 commented on Sep 10, 2020

oli-obk commented on Sep 11, 2020

ecstatic-morse commented on Sep 11, 2020

camelid commented on Jan 23, 2021

oli-obk commented on Jan 23, 2021

pnkfelix commented on Oct 14, 2022

qiaochloe commented on Dec 1, 2025

oli-obk commented on Dec 1, 2025

dianqk commented on Dec 1, 2025

dianqk commented on Dec 22, 2025

alex-j-wang commented on Dec 24, 2025

dianqk commented on Dec 28, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions