Repository: rust
Issue: Quadratic compilation time in release build.
Labels: I-compiletime,T-compiler,C-bug

I tried this code:

```rust
pub struct WeirdTrie {
	members: [[Option<Box<[Option<Box<[Vec<()>; 256]>>]>>; 256]; 256],
}

fn make_array<T>(f: impl Fn() -> T) -> [T; 256] {
	[
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
		f(), f(), f(), f(), f(), f(), f(), f(),
	]
}

impl WeirdTrie {
	pub fn new() -> Self {
		WeirdTrie {
			members: make_array(|| make_array(Default::default)),
		}
	}

	pub fn get_mut(&mut self, k: [u8; 5]) -> &mut () {
		let level = &mut self.members[k[0] as usize];
		let level = match &mut level[k[1] as usize] {
			Some(ref mut e) => e.as_mut(),
			none => {
				*none = Some(Box::new(make_array(Default::default)));
				none.as_mut().unwrap()
			}
		};
		let level = &mut level[0];
		let level = level.get_or_insert_with(|| Box::new(make_array(Default::default)));
		&mut level[0][0]
	}
}
```

I expected to see this happen: Compilation finished.

Instead, this happened: When using `opt-level=2` or `3` compilation hangs. Tested using `rustc --crate-type=lib src/lib.rs -Copt-level=2`

Note: This is a stripped down real-world example from https://gitlab.com/kevincox/ricochetrobots/-/blob/2ff959a53a7df32530bc9cedadd9d885b809cf5e/src/solver.rs. I was trying to optimize the `WeirdTrie` class further and ran into a hanging compilation. This seems related to the addition of `get_or_insert_with` call, but removing much more seems to avoid the problem.

Sampling times show super-linear behaviour with the size of the array created by `make_array()`.

Elements | Time (s)
--- | ---
32 | 0.87
64 | 7.168
90 | 23.674
112 | 53.641
128 | 100.32
160 | 238.3

![chart](https://github.com/rust-lang/rust/assets/494012/f591ce12-5258-433b-a096-5f0aa80af00d)

### Work Around

In this case the slow compilation can be worked around by replacing `make_array()` with the following implementation on newer versions of Rust that have the array `.map()` function available.

```rust
fn make_array<T>(f: impl Fn() -> T) -> [T; 256] {
	[(); 256].map(|()| f())
}
```

### Meta

`rustc --version --verbose`:
```
rustc 1.71.1 (eb26296b5 2023-08-03) (built from a source tarball)
binary: rustc
commit-hash: eb26296b556cef10fb713a38f3d16b9886080f26
commit-date: 2023-08-03
host: x86_64-unknown-linux-gnu
release: 1.71.1
LLVM version: 16.0.6
```