rrthomas / mit

A simple stack-based VM
Other
10 stars 3 forks source link

`profile.py` can get into an impossible state #304

Closed apt1002 closed 4 years ago

apt1002 commented 4 years ago

In the context of Welly, Tom and I found a bug in "profile.py" (which generates the random instruction stream based on profiling data). It artificially avoids the fallback path. However, there are sometimes profile states in which fallback is the only path with non-zero probability. Then simulate-jit has to choose one of the zero-probability paths, which it does. Then you're in a profile state with no data, and an assertion fails.

apt1002 commented 4 years ago

The solution must be not to avoid the fallback path. profile.py must treat the fallback state (numbered -1) as just another state. If asked to continue the trace, it must pick at random from the whole instruction set, and then return to the root state.

In the past, we discussed profiling the fallback interpreter, i.e. collecting statistics about what instructions it sees. That's quite inconvenient, as it makes the structure of the profile file less regular. Indeed that was why we made profile.py avoid the fallback path, which now looks like a mistake. Fortunately, I think profiling the fallback interpreter is also unnecessary. We don't need accurate statistics for the fallback state; a uniform probability distribution, or any other that is not too biased, will suffice.

apt1002 commented 4 years ago

There is a knock-on simplification permitted by the proposed solution. We can remove from simulate-jit the code that constructs Labels for all possible singleton Paths.

apt1002 commented 4 years ago

When this bug is fixed, check whether we still get profile states with large numbers of wrong guesses and no correct guesses.