Large amount of generated code for match statements with large arrays

[alex]

Consider the following code, which matches on a 64-element array:

type T = [u8; 64];

const X: T = [0x06, 0x04, 0x88, 0x37, 0x89, 0x52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

pub fn f(x: &T) -> bool {
    matches!(x, &X)
}

When built with rustc --crate-type=lib t.rs --emit=llvm-ir this emits 64 basic blocks, each doing a comparison. At -O, the optimizer is able to reduce it to 64 single-byte loads, which are OR'd together. Finally, at -C opt-level=3, the optimizer is able to put the whole thing back together into a single icmp ne <64 x i8>.

The large number of basic blocks are visible in the MIR, which leads me to believe that all the optimizations here are being accomplished by LLVM.

Generating this large number of basic blocks is inefficient, and puts a lot of unnecessary pressure on LLVM to optimize things. It would be much better if either an integer comparison, or even a call to memcmp, was emitted, as it could simple be lowered as LLVM wished. This is how normal, non-match, comparisons with arrays of primitives are handled (see https://github.com/rust-lang/rust/blob/master/library/core/src/array/equality.rs#L146-L152 and https://github.com/rust-lang/rust/blob/master/compiler/rustc_codegen_llvm/src/intrinsic.rs#L298-L336).

This whole thing is extracted and minimized from https://github.com/alex/rust-asn1/blob/main/src/object_identifier.rs#L5-L24, which is used in many match statements in https://github.com/pyca/cryptography/tree/main/src/rust

[john-h-k]

I'd like to give this a shot (maybe ambitiously). Which files are relevant to lowering matches into MIR? Would this potentially be implementable by lowering array matches into simple equality?

[alex]

I'm far from an expert in the rustc source, but I think https://github.com/rust-lang/rust/tree/master/compiler/rustc_mir_build/src/build/matches is the place to start.

[kehrazy]

the IR in question:

• with -C opt-level=3

%0 = load <64 x i8>, ptr %x, align 1, !dbg !11
%.fr = freeze <64 x i8> %0, !dbg !11
%1 = icmp ne <64 x i8> %.fr, <i8 6, i8 4, i8 -120, i8 55, i8 -119, i8 82, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>, !dbg !11
%2 = bitcast <64 x i1> %1 to i64, !dbg !11
%3 = icmp eq i64 %2, 0, !dbg !11
ret i1 %3, !dbg !12

• with -C opt-level=0

; this code block gets executed 64 times
%187 = getelementptr inbounds [64 x i8], ptr %x, i64 0, i64 62, !dbg !11
%188 = load i8, ptr %187, align 1, !dbg !11, !noundef !10
%189 = icmp eq i8 %188, 0, !dbg !11
br i1 %189, label %bb63, label %bb64, !dbg !11

What I find particularly interesting is the inclusion of the following zeroes in the icmp - we should use [58 x i64] zeroinitializer instead.

[jieyouxu]

When ~const PartialEq becomes usable in libcore, the MIR lowering simplification for slice patterns should be quite easy to implement.

[alex]

Looks like this has in fact regressed (or at least changed), in terms of the LLVM IR that it optimized to.

Here's what it looks like with Rust 1.71.0: https://rust.godbolt.org/z/W5K4Gofv9 (basically just an icmp).

And here's with Rust 1.72.0: https://rust.godbolt.org/z/j9zsnPqxv (chain of many comparisons).

[Nadrieril]

I'm guessing this is an LLVM change, because we don't do anything clever in the lowering algorithm. The lowering algorithm needs to handle subpatterns so today it compiles array (and tuple and everything) patterns like a trie:

match x {
    [0, 0, 0, ...] => 0,
    [1, 0, 0, ...] => 1,
    [0, 1, 0, ...] => 2,
    [1, 1, 0, ...] => 3,
    ...
}
// would compile to:
if x[0] == 0 {
    if x[1] == 0 {
        ...
    } else if x[1] == 1 {
        ...
    }
} else if x[0] == 1 {
    if x[1] == 0 {
        ...
    } else if x[1] == 1 {
        ...
    }
}

So a single array pattern becomes a chain of ifs. We could detect array constants and do something better. As @jieyouxu mentioned we'll need const PartialEq support first.