>So long as the behavior meets the contract, the compiler/interpreter is free to do whatever it wants.

Yes, and that's how it's supposed to be. Any description that determines the totality of a problem space is an implementation itself.

Imagine the following requirements:

f(0) = 0, f(2) = 4

Both f(x) = x^2 and f(x) = 2x are correct ways to implement said requirements. But if you start relying on f(1) = 2, you might get in trouble with a coworker that relies on f(1) = 1. This is undefined behavior and should be avoided.

>There’s nothing in the C spec I’m aware of that says the C compiler has to ensure that each invocation of a piece of code will execute the same machine instructions.

It can't, because C can be written for any system you want. If I ask the compiler to compile x *= 2, it might use the mul primitive or it might use shl, both are ok.