Missed optimization: invert nested switches

[Kmeakin]

Reporting from rust-lang/rust#117970

SimplifyCFG could invert nested switches to reduce code size and number of comparisons

Rust example

Compiler explorer

extern "Rust" {
    fn foo() -> u32;
    fn bar() -> u32;
    fn baz() -> u32;
}

pub fn src(x: u32, y: u32) -> u32 {
    unsafe {
        match (x, y) {
            (1, 10) => foo(),
            (2, 10) => bar(),
            (3, 10) => baz(),
            _ => 0,
        }
    }
}

pub fn tgt(x: u32, y: u32) -> u32 {
    unsafe {
        match (y, x) {
            (10, 1) => foo(),
            (10, 2) => bar(),
            (10, 3) => baz(),
            _ => 0,
        }
    }
}

C equivalent

Compiler explorer

#include <stdint.h>

uint32_t foo();
uint32_t bar();
uint32_t baz();

uint32_t src(uint32_t x, uint32_t y) {
    switch (x) {
        case 1:
            switch (y) {
                case 10:
                    return foo();
                default:
                    return 0;
            }
        case 2:
            switch (y) {
                case 10:
                    return bar();
                default:
                    return 0;
            }
        case 3:
            switch (y) {
                case 10:
                    return baz();
                default:
                    return 0;
            }
        default:
            return 0;
    }
}

uint32_t tgt(uint32_t x, uint32_t y) {
    switch (y) {
        case 10:
            switch (x) {
                case 1:
                    return foo();
                case 2:
                    return bar();
                case 3:
                    return baz();
                default:
                    return 0;
            }
        default:
            return 0;
    }
}

[UsmanNadeem]

Hi, we have a downstream pass that does similar optimizations for switch statements, it is geared towards switch based state machines used in embedded products.

We are planning to upstream it in the near future. Please let me know if anyone is planning to work on this ticket.