CTFE fails to detect a certain class of infinite loops #52475
Description
#51702 implemented a limited form of infinite loop detection during const evaluation by periodically comparing MIR interpreter states.
Currently, the detector considers AllocIds when comparing interpreter memory. It is possible for two interpreter states which have different AllocIds to be functionally equivalent if the underlying allocations have the same structure and values. For example, the following code, which could easily be terminated by the infinite loop detector, causes const evaluation to continue forever.
#![feature(const_fn, const_let)]
const fn churn_alloc_id() -> usize {
let mut x: &i32 = &5;
loop {
x = &5;
}
0
}
fn main() {
let _ = [(); churn_alloc_id()];
}This hangs the current nightly build (2017-07-16).
@oli-obk suggested to ignore AllocIds by traversing all allocations in interpreter memory at a given moment in time in a predictable order. If two traversals observe logically equivalent Allocations in the same order, the interpreter state as a whole is logically equivalent as well.
I have some free time again, so I'll try to implement this.