Instruction Re-Ordering

Question

I have a question about legal instruction re-ordering in C#/.NET.

Let's start with this example. We have this method defined in some class, where _a, _b, and _c are fields.

int _a;
int _b;
int _c;
void Foo()
{
   _a = 1; // Write 1
   _b = 1; // Write 2
   _c = 1; // Write 3
}

And our calling environment would look something like this.

//memory operations
ClassInstance.Foo();
//memory operations

I'm wondering what kind of legal instruction re-orderings are possible when this method call gets inlined vs a function call. More specifically, I'm wondering if/when is it legal to re-order memory operations within Foo(), with memory operations outside of it (from our previous example, the //memory operations).

Also, does a function call(no inline), in a sense, "generate memory barriers". As in, memory operations that happen before or after the function call cannot be re-ordered with memory operations within the function call.

If so, would it still have this "memory barrier" behavior when it gets inlined by the compiler?

Answer 1

The C# Language Specification can help answer this. The section on Execution Order has this to say:

3.10 Execution order

Execution of a C# program proceeds such that the side effects of each executing thread are preserved at critical execution points. ....The execution environment is free to change the order of execution of a C# program, subject to the following constraints:

• Data dependence is preserved within a thread of execution. That is, the value of each variable is computed as if all statements in the thread were executed in original program order.

• Initialization ordering rules are preserved (§10.5.4 and §10.5.5).

• The ordering of side effects is preserved with respect to volatile reads and writes (§10.5.3).

(there is more that I've left out; the spec is quite readable so I suggest taking a look if you really want to get into the gritty details).

Essentially, the rules can be thought of as "the jitter may rearrange the execution order as long as the difference is not observable by the executing thread". But, other threads may observe the differences. In a post by Eric Lippert on the Coverity blog, he says:

...the CPU may as an optimization choose to [rearrange execution order] provided that doing so is not detectable by the current thread. But that fact could be observed by another thread...

So, if the order of operations is important for other threads as well as the current thread, then you'll need to create a "critical execution point"; the easiest way to do this is probably to surround the statements with a lock.

Answer 2

When discussing instruction reordering keep in mind that there are usually two (or more) threads in play. The Execution Order clause in the specification is basically the formal definition of the intuitive idea that a thread should perceive side-effects in the same order as specified by the programmer. Applications would have non-deterministic behavior without it.

The real crux of the topic is how other threads perceive the side-effects. This is where that 3rd point about volatile reads and writes comes into play. It just so happens that all writes (in all versions of the .NET Framework that I am aware of) have release-fence semantics.

I like to use an arrow notation to help visualize the constraints placed on instruction reordering optimizations. I use an ↑ arrow to indicate a release-fence and a ↓ arrow to indicate an acquire-fence. Nothing is allowed to float down past an ↑ arrow or up past an ↓ arrow. Think of the arrow head as pushing everything away. Using this arrow notation and assuming writes still have release-fence semantics then your code would look like this.

void Foo()
{
   ↑
   _a = 1; // Write 1
   ↑
   _b = 1; // Write 2
   ↑
   _c = 1; // Write 3
}

Hopefully it is now easier to see that any of the writes is not allowed to float down past another one because an arrow blocks its movement. What this means is that other threads will, in fact, perceive these writes in the same order as they occurred in the thread executing Foo.

I describe other ways instructions can get reordered in questions here, here, here, here, and especially here.