CODEWITHSUNDEEP
.netcompiler-constructionstackcil
Jay Lemmon
Jay Lemmon

Reputation: 1155

Compiling stack based language to CIL

I have a custom stack based language that I'm trying to compile to CIL, so it can be JITed. The language itself is fairly simple, as it only has integers and booleans. Each data type has a dedicated stack, however. The language itself is a stream of commands, where each command can peek, push, and/or pop values from either stack. The number of integers or booleans pushed/poped by a command never changes (so the commands have fixed arity). There's also a flat integer array that the language reads and writes values to, representing external memory. The stacks themselves can be arbitrarily deep.

For simple commands like "add", "subtract", etc., translating the integer stack commands to CIL is almost trivially easy: the CIL stack can wholesale replace the integer stack (although I have a side question: is there a limit on how deep the CIL stack can be, either in spec or in practice?) However there's also commands like StoreIfTrue, which will only store a value (from the integer stack) to the flat integer array at some index (the index also from the integer stack) if the top value of the boolean stack is true. So I need access to the boolean stack and the integer stack simultaneously for some of the commands.

Right now I have to maintain a System.Collections.Generic.Stack to represent the boolean stack. But I'm wondering if there's a known algorithm or method to "flatten" the two stack model of my custom language in to a single stack model that'd be more directly compatible with CIL.

Upvotes: 4

Views: 456

Answers (2)

Daniel A.A. Pelsmaeker
Daniel A.A. Pelsmaeker

Reputation: 50356

I cannot deduce from your question whether you know how to generate CIL code from, for example, C#. To do that, you can use either Reflection or Cecil.

For the Virtual Execution System (VES, the model of a virtual system that would execute the CIL instructions) values on the stack (and in registers) have no associated complex type. Only simple types (int32, int64, managed object reference, managed pointer and float) are tracked by the VES. So, the VES cannot see the difference between a boolean and an integer on the stack (internally, the VES treats booleans as 32-bit integers) so it is not possible to use the execution stack to simulate both your boolean and integer stacks. You could do the same: treat booleans as integers and non-zero integers as boolean true. So a compare on two integers would result in another integer. However, then you just have one stack and not two.

Edit:

Ah, I see. Your language is intended to be a generic programming language and must therefore be highly robust and have some predefined (or none) behavior for all possible inputs (including invalid ones). By having separate stacks for each of the possible types, it is more likely that a compatible operand is used instead of any random one.

As it is not possible to use a single stack to simulate multiple stacks, I'd go with a real Stack<T> object for each type and not try to use the CIL stack. This has several advantages:

  • Easier to add new types in the future
  • Allows stack bounds checks (e.g. to make an operation a no-op)
  • Easier to manage than any custom scheme for mixing types on one stack
  • Random access, if you need it
  • No need to know CIL internals, so can run on Mono and .Net
  • CIL stack is then only for temporary operands, stack frames and return addresses

Upvotes: 0

svick
svick

Reputation: 244988

I think storing two independent stacks in a single stack is not possible (at least without external temporary storage, but then you would get terrible performance). That's because there is no way how to have the tops of both stacks somehow always close to the top of the actual stack, no matter what representation you would use.

But CIL doesn't just have the stack and the heap, it also has local variables. But you can access local variables only through a constant index. So, if you always knew the index of the top of the stack at compile time, and you also knew the maximum size of the stack, you could use local variables to represent it. But I don't think these two conditions would hold in your case.

Because of that, I think using Stack<T> for one or both of your stacks is your best options.

Upvotes: 1

Related Questions