Bug fixed with four nops in an if(0), world no longer makes sense

Most times when you modify the code inconsequentially and it fixes your problem, it's a memory corruption problem of some sort. We may need to see the actual code to do proper analysis, but that would be my first guess, based on the available information.

It's faulty pointer arithmetic, either directly (through a pointer) or indirectly (by going past the end of an array). Check all your arrays. Don't forget that if your array is

 int a[4];

then a[4] doesn't exist.

What you're doing is overwriting something on the stack accidentally. The stack contains both locals, parameters, and the return address from your function. You might be damaging the return address in a way that the extra noops cures.

For example, if you have some code that is adding something to the return address, inserting those extra 16 bytes of noops would cure the problem, because instead of returning past the next line of code, you return into the middle of some noops.

One way you might be adding something to the return address is by going past the end of a local array or a parameter, for example

  int a[4];
  a[4]++;

I came back to this after a few days busy with other things, and figured it out right away. Sorry I didn't post the code sooner, but it was hard coming up with minimal example that displayed the problem.

The root problem was that I left out the return statements in the recursive function. I had:

bool function() {
    /* lots of code */
    function()
}

When it should have been:

bool function() {
    /* lots of code */
    return function()
}

This worked because, through the magic of optimization, the right value happened to be in the right register at the right time, and made it to the right place.

The bug was originally introduced when I broke the first call into its own special-cased function. And, at that point, the extra nops were the difference between this first case being inlined directly into the general recursive function.

Then, for reasons that I don't fully understand, inlining this first case led to the right value not being in the right place at the right time, and the function returning junk.