Drop elaboration emits `O(N^2)` cleanup for partially-initialized aggregate literals

[ashi009]

An aggregate literal of N droppable elements whose initializers can diverge could emit O(N^2) drop terminators. Which chokes LLVM's CVP pass and cost substantial time in optimized build.

For example, the following code will take over 60s to build with -O:

pub fn build(s: u64) -> Result<Big, ()> {
    Ok(Big { f0: make_one(s ^ 0)?, /* … N fields … */ f127: make_one(s ^ 127)? })
}

See https://github.com/ashi009/cvp-llvm-repro for a runnable example.

Reproducible on 1.96.0 stable (LLVM 22.1.2) and 1.98.0-nightly e7815e5 (LLVM 22.1.6).

[ashi009]

Where it originates: MIR drop elaboration emits an O(N²) cleanup ladder, before LLVM runs.

Counting basic blocks / drop terminators / cleanup blocks in the optimized MIR of build() (rustc 1.94.1 -O --emit=mir):

N	variant	bbs	drops	cleanup bbs
16	baseline (interleaved ?)	321	254	269
16	bind-then-build	82	30	31
32	baseline	1153	1022	1053
32	bind-then-build	162	62	63
64	baseline	4353	4094	4157
64	bind-then-build	322	126	127

For the interleaved-divergence aggregate literal, MIR drop terminators and cleanup blocks are ≈ N² (4094 ≈ 64² at N=64); the bind-then-build form is ≈ 2N. Each construction point gets its own cleanup chain that drops the suffix of already-initialized elements, so the partially-initialized aggregate produces a quadratic cleanup ladder at the MIR level — already present before any LLVM pass runs. The ~O(N³) wall-clock is then the function-opt pipeline (InstCombine/CorrelatedValuePropagation/JumpThreading) running super-linearly on top of that O(N²) CFG.

So this looks like it's rooted in drop elaboration for partially-initialized aggregate literals, with LLVM's super-linearity compounding it. python3 mir_count.py in the repro repo reproduces the counts.

[oli-obk]

Hi,

For the last few months we have been receiving an increased amount of LLM generated contributions. Your issue is generated (even if possibly with you in the loop), without a human written concise preamble. This makes it very hard to find the actual information in it.

We are a community of contributors, not just a code repository. We focus on contributors who desire to stay around and put in the work to produce high quality contributions or learn to do so.

We are thus warning you as per our policies (1) and contribution standards (2) to stop generating PRs and comments.

To make sure you can learn how to contribute, we invite you to join https://rust-lang.zulipchat.com/join/rlfvpemsaacs3pfi6kwqnqjb/ and start a thread asking for a mentor.

Thanks for understanding

Oli in the name of the mod team

[ashi009]

oh great, ignoring real bug, and no wonder rust has soo many bugs.

[traviscross]

@ashi009: It's my sense that you put in real effort on this. I appreciate that. As you noticed, we're building on this work in #157491. In your place, I'd probably be frustrated.

The reasons why the Rust Project needs to close this issue and issues like it are complicated and are not a judgment on your effort or on you as a person.

The offer that @oli-obk made to join us on Zulip is real. We want you to participate in the Rust Project, and we want to help you do that. Please consider joining us.