I don't really like the idea of counting instructions, personally. There's a lot of variation possible there. (Does your emulation count cycles at all, or is that a foreign concept to this emulator?)
I think you could make a practical simple idle test with reasonably low overhead. Something like:
1. Whenever you hit a branch or jump instruction, store the resulting location branched to.
2. If equal to the last branch location, increment a counter.
3. When the counter reaches some threshold, start doing progressive tests.
The baseline complexity is just little bit of extra work in every branch, and you don't have to do any more complicated tests until you've reached some threshold conditions, and if you detect the idle loop once you can just skip the test when you hit it again on subsequent frames.
Here's a quick code sketch of the idea: (not intended as a fully working solution, just an illustration of the concept)
uint8 idle_a, idle_x, idle_y;
void branch() // call after any branch or jump instruction
if (register.PC == last_branch) // if in a loop
if (register.PC == last_idle) // we already detected this loop last frame, skip the retest
idle(); // stop emulating PC until next NMI or IRQ or sprite-0 etc.
if (!idle_test) return; // already ruled this out as an idle loop
case 32: // some arbitrary threshold to begin idle testing
idle_a = register.A;
idle_x = register.X;
idle_y = register.Y;
case 33: // test #1
if (register.A != idle_a || register.X != idle.x || register.Y != idle_y) // probably not an idle loop e.g. if index registers are changing
idle_test = false;
idle_hash = hash_ram_state(); // most expensive test: try to detect any changes in RAM for the next loop
case 34: // test #2
if (idle_hash == hash_ram_state())
last_idle = register.PC; // remember this idle point to skip detection next time
idle_test = false;
else // branched to a new location, not currently in a loop
loop_count = 0;
idle_test = true;
last_branch = register.PC;
There's always ways to make cases that this can't detect, but you don't need to solve the general purpose case. You can tweak your detector to work with the kind of cases you expect, and tell your users how they should form their idle loops. (An idle loop with several branches obviously wouldn't work, for example, but you could extend the idea to "last 8 branches", etc. if you wanted that feature.)