CLR stack

[Joel]

I would like to learn if there is any difference between the stack that
MSIL
uses for each method for executing instructions and the stack that it
uses
for storing Value types. Are they the same?

Also the processor has its own stack pointer right,.. so are these
stacks related
to the processor's stack? or are they virtually implemented by the CLR
?

Thanks

Joel

 

[Barry Kelly]

I would like to learn if there is any difference between the stack that
MSIL
uses for each method for executing instructions and the stack that it
uses
for storing Value types. Are they the same?

Also the processor has its own stack pointer right,.. so are these
stacks related
to the processor's stack? or are they virtually implemented by the CLR

IL is based on a conceptual model called the VES, Virtual Execution
System. IL instructions logically use the VES stack for implementing
primitives like addition and subtraction (both of these pop two values
off and push the result), and to hold intermediate values while
evaluating complex expressions (any complex expression can be converted
into stack manipulations, often called RPN, or reverse polish notation).
The VES does not model local variables as being stored on its stack.
Instead, they are directly modeled as locals, described in a table at
the start of a method (actually, a signature, which is a kind of
compressed description of a table) and are accessed with instructions
like ldloc and stloc.

When people talk about a stack in the context of differentiating value
types from reference types, they are talking about the CPU stack as in
more traditional languages. The translation from the VES model to the
physical model is at the discretion of the implementation of the CLI
(CLR for .NET).

Typically the CLR on x86 will implement the VES stack as register
operations, and locals as registers but spilling out to stack where
necessary.

Don't confuse the VES stack with the CPU stack, because one doesn't
translate into the other (it could be done that way, but it would be
inefficient). Instead, think of the IL stream with respect to
expressions as a serialization of an expression tree. In fact, with
'dup' instructions, it is actually a serialization of an expression dag,
or Directed Acyclic Graph.

For example, calculating (42 + 24) / 2 could be modeled as the following
RPN:

push 42
push 24
add
push 2
div

This could alternatively be modeled as the following Lisp tree. Notice
that a post-order traversal of the tree produces the RPN expression.

(/ (+ 42 24) 2)

These two expressions are equivalent, but RPN is more space-efficient
when opcodes are mostly byte-size. Once viewed as a tree, traditional
compiler code generation techniques can be directly applied.

-- Barry

 

[Joel]

Thanks a lot, that was really helpful.

One question,.. as you said, value types are stored in the x86
processor stack and VES locals are actually stored there.
How are these locals accessed from the stack?
push and pop instructions store or retrieve only the top of the
stack as pointed by the CPU stack pointer, how are locals at
intermediate locations in the stack accessed then?

Joel

 

[Barry Kelly]

Thanks a lot, that was really helpful.

One question,.. as you said, value types are stored in the x86
processor stack

That is how people think of them, i.e. avoiding GC overhead, but if the
value type is small enough it may be in a register instead. (Of course,
if the value types are fields of another object, then they are stored
inline in that object's memory; if the other object is a value of a
reference type, then the memory of the field of the value type is stored
inline in the value of the reference type's memory, allocated from the
GC. "Value types on the stack" refers only to parameters and locals, not
fields.)

and VES locals are actually stored there.

When IL is compiled to machine code, VES locals may allocated to
registers if they are available and the value is small enough, and only
spill to stack when necessary, just like any optimizing native code
compiler. IL is like simplified source code for an optimizing native
code compiler.

How are these locals accessed from the stack?

With CPU instructions that the CLR generates when it compiles the IL
code.

push and pop instructions store or retrieve only the top of the
stack as pointed by the CPU stack pointer, how are locals at
intermediate locations in the stack accessed then?

The x86 CPU models the top of stack as being the thing pointed to by the
ESP register, and convention uses the EBP register as the frame
register. The x86 processor's instructions such as PUSH and POP modify
ESP as they push and pop, but that does not stop other instructions like
MOV and ADD from directly accessing memory operands via expressions that
use ESP or EBP. For example:

mov eax,[esp+4]

or

add eax,[ebp+12]

.... are instructions that are using locals and arguments. The x86 stack
grows downwards, so ESP+n is deeper into the stack, while values higher
than EBP would typically be arguments that have been passed on the
stack.

Don't confuse the VES model with the CPU model. The VES is an abstract
machine, or virtual machine, which provides a context for the exact
definition and specification of what IL means. IL is only a language for
a native code compiler. The fact that IL can only push and pop and can't
directly address its stack does not limit the CPU, which can do whatever
the IL compiler (the JIT compiler in the CLR) generates code for it to
do.

-- Barry

 

[Joel]

Thanks a lot, that was very insightful.

mov eax,[esp+4]

or

add eax,[ebp+12]

... are instructions that are using locals and arguments.

In other words, are you saying IL instructions like ldc and ldarg
translate
into the above?

The x86 stack
grows downwards, so ESP+n is deeper into the stack, while values higher
than EBP would typically be arguments that have been passed on the
stack.

Can you please rephrase the above statement in simpler terms.

Regards

Joel

 

[Barry Kelly]

Thanks a lot, that was very insightful.

mov eax,[esp+4]

or

add eax,[ebp+12]

... are instructions that are using locals and arguments.

In other words, are you saying IL instructions like ldc and ldarg
translate
into the above?

Yes (specifically ldloc and ldarg), but not usually that directly, not
that simply. The IL instructions are source code for another compiler,
the CLR JIT compiler, which will reconstitute a simple expression graph
from the IL and use that with more traditional compiler algorithms to
generate optimized code.

Can you please rephrase the above statement in simpler terms.

This is to do with the x86 CPU architecture. You can get specification
documents from Intel's site which fully describe the hardware and the
instruction set. It's drifting away from .NET, but I'll write some brief
info.

ESP is a 32-bit register whose value is an address in memory. x86 stack
operations like PUSH and POP modify ESP as they store and retrieve
values from the stack. By the stack growing downwards, I mean that ESP
gets smaller every time you push, and gets larger every time you pop. In
picture terms and very simplified, imagine memory, broken into dwords
here (32-bit values), addresses on the left, values on the right (but
I've used small numbers here for simplicity):

118 50
114 42
110 10
10C 90
108 90

(Memory is usually visualized with low addresses at the bottom, high
addresses at the top.)

If ESP had the value 110, that means that 10 is the value on top of the
stack. If the CPU next executed 'POP EAX', it would be equivalent to
saying 'MOV EAX, [ESP]; ADD ESP, 4'. That is, popping from the x86 stack
has increased the value of ESP, and after popping it will have the value
114, and now 42 is on top of the stack. That is, the stack grows
downwards in the picture, and shrinks upwards.

The x86 stack is different from the VES stack though. The two are
similar but different. For example, the VES stack is per-activation
record while the x86 stack helps implement subroutine calling. When the
x86 'CALL' instruction is executed, it pushes the address of the next
instruction after the CALL instruction onto the stack, and similarly a
RET instruction pops the return value into EIP (the instruction pointer
register) and continues where it left off. (There can be more to it than
that, see the Intel docs for more info.) There is no equivalent in the
VES model.

EBP has to do with the x86 calling conventions and setting up a stack
frame. You can find more info about this by (e.g.) Googling "x86 stack
frame", without the quotes it will get lots more info.

-- Barry