Can MIR have irreducible control flow?

[RalfJung]

All Rust programs have reducible control flow -- except if we write them with custom MIR:

#![feature(custom_mir, core_intrinsics)]
extern crate core;
use core::intrinsics::mir::*;

#[custom_mir(dialect = "built")]
pub fn irreducible(x: bool) { mir! (
    // start block jumps to one of two different blocks inside the below loop
    {
        match x {
            true => bb1,
            _ => bb2
        }
    }

    // bb1, bb2 form a loop
    bb1 = {
        Goto(bb2)
    }
    bb2 = {
        Goto(bb1)
    }
)}

Here is a more complicated example that doesn't get optimized away immediately:

#![feature(custom_mir, core_intrinsics)]
extern crate core;
use core::intrinsics::mir::*;

#[inline(never)]
pub fn black_box() -> i32 {
    std::hint::black_box(42)
}

#[custom_mir(dialect = "built")]
pub fn irreducible(x: bool) { mir! (
    let y: i32;
    // start block jumps to one of two different blocks inside the below loop
    {
        match x {
            true => bb1,
            _ => bb3
        }
    }

    // bb1, bb2, bb3, bb4 form a loop (with some early exit points)
    bb1 = {
        Call(y, bb2, black_box())
    }
    bb2 = {
        match y {
            1 => bb3,
            _ => ret
        }
    }
    
    bb3 = {
        Call(y, bb4, black_box())
    }
    bb4 = {
        match y {
            1 => bb1,
            _ => ret
        }
    }
    ret = {
        Return()
    }
)}

This should probably be rejected right after Custom MIR building? At least I assume later MIR passes can generally assume reducible control flow.

Thanks to @cbeuw for the examples.

Cc @JakobDegen

[JakobDegen]

since later MIR passes can generally assume reducible control flow.

Can they? Can you give an example of this assumption existing somewhere?

[RalfJung]

Hm, at least I thought I had heard that this is documented as an assumption somewhere. I can't find the assumption right now.

But given that Rust-generated MIR is always reducible, it seems unnecessary to require MIR passes to support irreducible control flow?

[JakobDegen]

Well, the other option is to require Mir passes to avoid creating it. It's non-obvious to me which of those is easier

[RalfJung]

Fair.

@rust-lang/wg-mir-opt has it been decided already whether MIR can be irreducible or not?

[cbeuw]

DeduplicateBlocks can make reducible CFG irreducible:

#![feature(custom_mir, core_intrinsics)]
extern crate core;
use core::intrinsics::mir::*;

#[inline(never)]
fn black_box() -> i32 {
    std::hint::black_box(42)
}

#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn reducible(x: bool, y: i32) { mir! (
    {
        match x {
            true => bb1,
            _ => bb3,
        }
    }
    bb1 = {
        Call(y, bb2, black_box())
    }

    bb2 = {
        match y {
            1 => bb1,
            _ => ret,
        }
    }
    
    bb3 = {
        match y {
            1 => bb1,
            _ => ret,
        }
    }

    ret = {
        Return()
    }
)}

The above is reducible:

      bb0
       │
    ┌──┴──┐
    ▼     │
 ┌►bb1◄┐  │
 │  │  │  │
 │  │  │  │
 │  ▼  │  ▼
 └─bb2 └─bb3
    │     │
    └──┬──┘
       │
       ▼
      ret

After -Zmir-opt-level=0 -Zmir-enable-passes=+DeduplicateBlocks:

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
fn black_box() -> i32 {
    let mut _0: i32;

    bb0: {
        _0 = std::hint::black_box::<i32>(const 42_i32) -> [return: bb1, unwind continue];
    }

    bb1: {
        return;
    }
}

fn reducible(_1: bool, _2: i32) -> () {
    let mut _0: ();

    bb0: {
        switchInt(_1) -> [1: bb1, otherwise: bb2];
    }

    bb1: {
        _2 = black_box() -> [return: bb2, unwind continue];
    }

    bb2: {
        switchInt(_2) -> [1: bb1, otherwise: bb3];
    }

    bb3: {
        return;
    }
}

[RalfJung]

Oh, interesting.

Cc @xldenis @vakaras who mentioned reducibilty in the past.

[xldenis]

I have very little knowledge about whether allowing irreducibility is beneficial for optimization (I feel like it could easily cut both ways), for verification however, it is beneficial. If MIR is guaranteed to stay reducible it makes it easier to consume different stages of MIR code for verification (for example to build translation validation or verify optimizations).

[workingjubilee]

Note that compiling irreducible control flow to wasm can be a deoptimization, as it does not naturally have ways to express irreducible control flow, requiring the Relooper construct (which can result in some fairly horrifying codegen).

[bjorn3]

There is a mir pass to break critical edges for call terminators which runs right before codegen. cg_ssa's lowering of unwinding calls depends on this.

[RalfJung]

I think even a CFG without critical edges can be irreducible?

[bjorn3]

Yeah, I just realized that.