Making Magic: How Sigil Works

Posted: 2013/05/16 | Author: kevinmontrose | Filed under: code | Tags: sigil | 3 Comments

Version 3.0.0 of Sigil was just released (grab it on Nuget and check out the source on Github).  The big new feature this release is a disassembler, one which allows for some inspection of the flow of values through a .NET delegate.

But that’s not what I’m writing about.  I figure now’s as good a time as any to write up the “how” of Sigil, given that I covered the “what” and “why” in an earlier post and that recent releases have refactored Sigil’s internals into a state I’m happier with.

Bytecode Verifiers And You

In essence Sigil is a “bytecode verifier”.  If you’ve done JVM or .NET development you should be familiar with the concept, the bytecode verifiers on those platforms make sure that the class files or assemblies you load contain bytecode that can safely be executed.

The definition of “safe” is very particular, a bytecode verifier doesn’t prevent errors from occurring at execution time but rather prevents invariants of the runtime from being violated.  For example, a bytecode verifier would guarantee that invoking an instance method is passed the proper number and types of parameters and that it is invoked against an instance of the appropriate type.

One way to think about bytecode verifiers is that they guarantee that every operation receives the correct types as inputs and every operation leaves the runtime in a well formed state.

Sigil’s Special Features

Where Sigil differs from other bytecode verifiers is that it doesn’t operate on “finished” instruction sequences.  It verifies as you build a sequence, failing as soon as it can be sure the sequence is invalid.

Because Sigil deals with incomplete instruction sequences it also has to do with a lot of unknowns, especially around branches.  It’s quite common to branch to an instruction you haven’t actually emitted yet or emit instructions that aren’t yet provably reachable, both cases a traditional verifier can never encounter.

Sigil also has to explain itself when it fails, so it has to be able to deliver where and why a given sequence became invalid (which can be far removed from the last emitted instruction because of branches).  Similar complications exist when verification is successful, as things like eliding trivial casts and replacing branches with their short forms (which are deferred until an instruction stream is finalized) requires a lot of information about the instruction stream be retained.

Simple Verifying

If you ignore branches, verifying a bytecode sequence is pretty simple.  You can think of it as executing instructions as if they consumed and produced types instead of values.  Since Sigil is a .NET library I’ll be using .NET examples, though the basic idea applies to all similar verifiers.

For example, assume the following is an implementation of a Func<int>:

ldc.i4 1
ldc.i4 2
add
ret

We know “ldc.i4” consumes nothing, and produces an int, “add” actually consumes and produces a wide range of types but one of them is “int int -> int”.  The “ret” instruction either consumes nothing or a single type, dependent on the signature of the method it is used in; in this case it consume an “int” which we know because the method is a “Func<int>”.

I’ve written out the state of the stack (the .NET runtime is specified as a stack machine) after each instruction executes:

         // --empty--
ldc.i4 1 // int
ldc.i4 2 // int int
add      // int
ret      // --empty--

We need to add one more rule, which is that control flow ends with a “ret” which leaves the stack empty, and with that it’s clear that this sequence would verify.

The following sequence wouldn’t verify:

ldc.i4 1            // int
ldstr "hello world" // string int
mult                // !ERROR!
ret

Since “mult” doesn’t have a transition from “string int” verification could be shown to fail as soon as “mult” is emitted.

The earliest releases of Sigil were simple verifiers as they didn’t try and trace through.  Through version 1.2.9 you instead had to assert types when marking labels under certain circumstances.

Complex Verifying

As soon as you add branches life gets considerably more complicated.  Now you have to deal with cases where you can’t infer what types are on the stack immediately.

Consider the following:

ldc.i4 1
br end_label

middle_label:
add
ret

end_label:
ldc.i4 2
br middle_label

In this example the types passed to “add” are unclear when it is emitted, it’s only when “br middle_label” is encountered that it becomes clear that “add” will verify.

Furthermore, whether or not “ret” verifies depends on the method being built. It would verify if we’re building a Func<int> then it verifies.  If we’re building a Func<string> it should fail when emitted, since there’s no way for “add” to pass a string to “ret”.  If we’re building a Func<double>, then it should fail when “br middle_label” is emitted since then “add” is known to produce and pass an Int32 to “ret”.

How Sigil Copes

Sigil deals with the complexities of verifying partial sequences in two ways: tracking the possible types on the stack, and creating a verifier for each possible code path.

Reconsidering the above example:

                // ** Initial Verifier: V1, with empty stack **
ldc.i4 1        // int
br end_label    // int
                // ** New Verifier: V2 with unknown stack, V1 stashed **
middle_label:
add             // int|long|float|double|etc.
ret             // --empty--
                // ** New Verifier: V3 with unknown stack, V2 stashed **
end_label:      // ** V1 restored (stack is: int) **
ldc.i4 2        // int int
br middle_label // int int (V2 now verified with int int as initial stack)

There’s rather a lot going on now, what with verifiers being stashed and restored.  Also note that when “add” is first encountered it places an “or” clause onto the stack, which allows “ret” to verify if it expects any type in that “or” clause.

The logic around creating and restoring verifiers is tricky, but boiled down:

• At an unconditional branch, store the current stack state and remove the current verifiers
  • If the branched to label has already been marked, take the current stack and check it against the expected initial stack at that label
• At a conditional branch do the same checks and stores as an unconditional one, but don’t remove the current verifiers
• When marking a label, if there is no verifier create a new one with an unknown initial stack
  • If there are stacks stored against that label from previous branches, check that those stacks are consistent and make them the new verifiers initial stack
• Treat “ret” as an unconditional branch which doesn’t store the stack state
• If at any point an instruction is emitted and there is no current verifier, the newly emitted code is unreachable

This logic is captured in Sigil’s RollingVerifier UnconditionalBranch, ConditionalBranch, Return, and Mark methods.

As for tracking all possible values on the stack (as in the “or” with “add” in the previous example), Sigil considers transitions rather than types on the stack.  So long as there’s at least one transition that could be taken for every instruction a verifier has seen, the instruction stream is considered verifiable.

Take for example the, rather complex, transitions for “add”:

new[]
{
    new StackTransition(new [] { typeof(int), typeof(int) }, new [] { typeof(int) }),
    new StackTransition(new [] { typeof(int), typeof(NativeIntType) }, new [] { typeof(NativeIntType) }),
    new StackTransition(new [] { typeof(long), typeof(long) }, new [] { typeof(long) }),
    new StackTransition(new [] { typeof(NativeIntType), typeof(int) }, new [] { typeof(NativeIntType) }),
    new StackTransition(new [] { typeof(NativeIntType), typeof(NativeIntType) }, new [] { typeof(NativeIntType) }),
    new StackTransition(new [] { typeof(float), typeof(float) }, new [] { typeof(float) }),
    new StackTransition(new [] { typeof(double), typeof(double) }, new [] { typeof(double) }),
    new StackTransition(new [] { typeof(AnyPointerType), typeof(int) }, new [] { typeof(SamePointerType) }),
    new StackTransition(new [] { typeof(AnyPointerType), typeof(NativeIntType) }, new [] { typeof(SamePointerType) }),
    new StackTransition(new [] { typeof(AnyByRefType), typeof(int) }, new [] { typeof(SameByRefType) }),
    new StackTransition(new [] { typeof(AnyByRefType), typeof(NativeIntType) }, new [] { typeof(SameByRefType) })
};

One more thing to track when dealing with verifiers is whether or not we know their initial stack, what I call “baseless” in the code.  It is not an error for an instruction stream to underflow a baseless verifier, since it’s stack could be anything.  Instead of failing verification, Sigil considers the result of underflowing a baseless stack to be a “wildcard” type which satisfies any transition; this is how “add” can pop a value to continue verification after “middle_label”.

Trickier Things

.NET has a couple hairy CIL opcodes that require special handling: dup, localloc, and leave.

“dup” duplicates the current value on the stack, the difficulty being that we only know the type on the stack if we can verify the preceding instructions which isn’t always.  Sigil handles this by making “dup” place a special type on the stack, which when encountered by the verifier pushes a copy the preceeding transition’s result or a wildcard if underflowing a baseless verifier.

“localloc” is analogous to alloca(), pushing a pointer to memory on the stack, which requires that only a single value be on the stack when executed.  This means the current verifier cannot be baseless to verify.  In this case Sigil uses a special transition which asserts that the size of the stack is one if the verifier is based, and is ignored if it is not.

“leave” is an unconditional branch out of an exception or catch block which empties the stack entirely.  Sigil considers this equivalent to “pop”-ing exactly the number of items currently on the stack, which like “localloc” means the current verifier cannot be baseless.  Like “dup” Sigil uses a special type to indicate that the stack needs to be emptied to the verifier.

Optimizing Emitted Code

There are two kinds of optimizations Sigil can do to emitted CIL: eliding trivial casts, and replacing instructions with their short forms.

Conceptually eliding is straight forward, just keep track of what types are guaranteed to go into a castclass or isinst operation and if those types are assignable to the type encoding with the instruction elide it.  Sigil attaches callbacks, like this one, to “castclass” and “isinst” transitions which are called whenever a verifier processes those operations and passed enough information to decide whether to elide themselves or not.

Some short forms are easy, any of the LoadConstant methods with short forms can be changed at call time.  The trickier ones are branches, as we need to wait until we’re done emitting code and can calculate offsets.  Tracking offsets is handled by BufferedILGenerator (which maintains a cache of byte offsets to each instruction) and a last minute call to Emit.PatchBranches patches all the branch instructions that can fit their offsets into a signed byte.

Optimizing Sigil

Sigil employs some tricks to keep it relatively snappy.

Perhaps most importantly, it doesn’t re-verify operations unless it absolutely has to.  Every currently in scope verifier maintains a cache of its state when it last verified the instruction stream and re-uses that cache when new instructions are added.  The cache does have to be invalidated when the initial stack state changes, which only happens when branching to or marking labels.

Sigil also tries to keep the number of verifiers in scope limited by discarding any non-baseless verifiers past the first one.  Since any verifier that isn’t baseless can be traced back to the start of the method, we know that there are no “or” type clauses on the stack so the verifiers are equivalent going forward even if they took different paths through the code.

Other Tidbits

To wrap this up I’m just going to list some minor things of note found in Sigil.

• Sigil has most of an implementation of Linq-to-Objects to run on pre-.NET 3.5 runtimes, heavily influenced by Jon Skeet’s Edulinq series
• Sigil has it’s own Tuple implementation for similar reasons
• Sigil’s disassembler, while doing a great deal more, started as a replacement for the Mono.Reflection disassembler in our code base
• Sigil’s exception blocks are slightly different from ILGenerators in that you explicitly attach catches and finallys to them, this makes nested exception handling easier to debug

And again, Sigil can be installed from Nuget and the source is available on Github.

---

Improving Sigil

Posted: 2013/03/04 | Author: kevinmontrose | Filed under: code | Tags: sigil | 2 Comments

A few weeks ago I announced Sigil, a fail-fast validating wrapper around .NET’s ILGenerator.  Since then I’ve pushed a number of updates and bug fixes, culminating in the fairly significant 2.0.0 release now on Nuget.

I figured now was a good time to write down what’s changed, and where I see this code going.

A Smarter Validator

The biggest change between 1.x and 2.x is that Sigil no longer requires stack type assertions after unconditional branches.

In version 1.x you had to do something like the following:

var emit = Emit<Func<int>>.NewDynamicMethod();

var label1 = emit.DefineLabel();
var label2 = emit.DefineLabel();

emit.LoadConstant(0);
emit.Branch(label1);

emit.MarkLabel(label2, new [] { typeof(int) }); // Sigil wasn't smart enough to know what the stack was here
emit.Return();

emit.MarkLabel(label1);
emit.Branch(label2);

Version 2.x removes the need to pass types to certain MarkLabel() calls entirely.  This removes the most painful bit of busywork entailed in using the initial release of Sigil.

As a consequence of this new validator, a few breaking changes were made to Sigil’s interface.  The obvious removal of stack assertions, plus the removal of GetStack (as the stack state is not always known) and the addition of some required parameters to array manipulation methods (as the array involved cannot always be inferred).

Better Debugging Information

Sigil is all about failing fast and helpfully, and several changes have been made to the string returned by SigilVerificationException.GetDebugInfo() since Sigil’s initial release.

Examples include:

• Non-returning paths indicated by the labels that path flows through
• Instructions that take locals are annotated with the names and types of the involved local
• The instruction that causes a verification error
• As in version 1.x the stack state at any error, now including all possible types

Optimizations

Since it’s initial release, Sigil has gained the ability to elide trivial casts (thanks to Marc Gravell for the first version of this feature).

Modest performance improvements have been made to rewriting branches into their short forms, and the ability to disable such rewriting has been added (credit to Jason Punyon for some of this).

Performance

Sigil has been tuned somewhat since it’s initial release, but the introduction of a smarter validator has come at a performance price under certain circumstances.  As a rough guideline, if you’re generating methods with hundreds of labels and branches or tens of thousands of instructions Sigil may be too slow for you.

In addition to the aforementioned optimization options (passed as OptimizationOptions), the option to defer some validation has also been added (via the ValidationOptions enumeration).  Between the two a great deal of Sigil’s utility can still be had even for very large or very branch intensive generated code.

Minor Improvements

• While debugging all declared labels and in scope locals are exposed as the Labels and Locals properties
• The WriteLine(string, params Locals[]) method
• Automatic insertion of the volatile prefix when able
• The ability to refer to locals and labels by name

The Future

I’m not really satisified with Sigil’s performance just yet.  Profiling suggests that the slowest part of Sigil is gluing together instruction sequences for post-branch validation; I’m sure this can be done more quickly and probably skipped altogether in a lot of cases.

I’d also like to support the last four CIL instructions: Arglist, Mkrefany, Refanytype, and Refanyval.  Sigil has focused mostly on the DynamicMethod case where these instructions are rarely useful, but for completion’s sake they should be available.

Sigil currently has .NET 4.5 and 3.5 builds, it’d be nice to get a .NET 2.0 build as well.  This is non-trivial as Sigil makes heavy use of LINQ and extension methods.

A more long term goal is to abstract most of Sigil’s dependency on System.Reflection and System.Reflection.Emit so that its validation and optimization features can be used for a wider array of meta-programming tasks.  Freely switching between standard .NET and IKVM.Reflection is probably the first place to start, as there’s already a similar feature in protobuf-net’s precompiler.

As before, Sigil’s source is on github and the latest stable releases are on Nuget.

---

Sigil: Adding Some (More) Magic To IL

Posted: 2013/02/14 | Author: kevinmontrose | Filed under: code | Tags: sigil | 5 Comments

A nifty thing you can do in .NET is generate bytecode (properly Common Intermediate Language [CIL], formerly Microsoft Intermediate Language [MSIL], commonly called just IL) on the fly.  Previously I’ve used it to do dumb things with strings, and build a serializer on top of protobuf-net.  Over at Stack Exchange it’s used in small but critical parts of our API, in our caching layer via protobuf-net, and in our micro-ORM Dapper.

The heart of IL generation is the ILGenerator class which lets you emit individual opcodes and keeps track of labels, locals, try/catch/finally blocks, and stack depth.

To illustrate .NET’s built-in IL generation, here’s how you’d add 1 & 2:

var method = new DynamicMethod("AddOneAndTwo", typeof(int), Type.EmptyTypes);
var il = method.GetILGenerator();
il.Emit(OpCodes.Ldc_I4, 1);
il.Emit(OpCodes.Ldc_I4, 2);
il.Emit(OpCodes.Add);
il.Emit(OpCodes.Ret);
var del = (Func<int>)method.CreateDelegate(typeof(Func<int>));

del(); // returns 3

But…
ILGenerator is quite powerful, but it leaves a lot to be desired in terms of ease of use.  For example, leave one of the Ldc_I4’s out of the above…
var method = new DynamicMethod("AddOneAndTwo", typeof(int), Type.EmptyTypes);
var il = method.GetILGenerator();
il.Emit(OpCodes.Ldc_I4, 1);
// Woops, we left out the 2!
il.Emit(OpCodes.Add);
il.Emit(OpCodes.Ret);
var del = (Func<int>)method.CreateDelegate(typeof(Func<int>));

del();

And what happens?  You’d expect an error to be raised when we emit the Add opcode, but I’d understand deferring verification until the delegate was actually created.
Of course nothing’s ever easy, and what actually happens is an InvalidProgramException is thrown when the delegate is first used with a phenomenally unhelpful “Common Language Runtime detected an invalid program.” message.  Most of the time, ILGenerator gives you no indicator as to where or why you went wrong.
Frustrations I’ve had with ILGenerator, in descending severity:

Fails very late during code generation, and doesn’t indicate what went wrong
Allows obviously malformed instructions, like Emit(OpCodes.Ldc_I4, “hello”)
Lack of validation around “native int” allows for code that only works on specific architectures


Enter Sigil
Naturally I have a solution, and that solution’s name is Sigil (defined as “an inscribed or painted symbol considered to have magical power”, pronounced “Si-jil”).  Sigil wraps ILGenerator, exposes much less error prone alternatives to Emit, and does immediate verification of the instruction stream.
The erroneous code above becomes:
var il = Emit<Func<int>>.NewDynamicMethod("AddOneAndTwo");
il.LoadConstant(1);
// Still missing that 2!
il.Add();
il.Return();
var del = il.CreateDelegate();
del();

And Sigil throws an exception at il.Add() with the much more helpful message “Add expects 2 values on the stack”.  Also notice how Sigil does away with all that nasty casting.
Sigil does much more than just checking that enough values are on the stack.  It’ll catch type mismatches (including esoteric ones, like trying to add a float and a double), illegal control transfers (like branching out of catch blocks), and bad method calls.
Data For Debugging
In addition to not failing helpfully, ILGenerator doesn’t give you much to go on when it does fail.  You don’t get an instruction listing or stack states, and your locals and labels are nothing but indexes and offsets.
When verification fails using Sigil the full instruction stream to data and current state of the stack (possibly two stacks, if a branch is involved) are captured by the thrown SigilVerificationException.  Every local and label gets a name in the instruction listing (which you can override), and the values on the stack that caused the failure are indicated.
For example…

var il = Emit<Func<string, Func<string, int>, string>>.NewDynamicMethod("E1");
var invoke = typeof(Func<string, int>).GetMethod("Invoke");
var notNull = il.DefineLabel("not_null");

il.LoadArgument(0);
il.LoadNull();
il.UnsignedBranchIfNotEqual(notNull);
il.LoadNull();
il.Return();
il.MarkLabel(notNull);
il.LoadArgument(1);
il.LoadArgument(0);
il.CallVirtual(invoke);
il.Return();

var d1 = il.CreateDelegate();


… throws an SigilVerificationException on Return(), and calling GetDebugInfo() on it gives you the following:
Top of stack
------------
System.Int32 // Bad value

Instruction stream
------------------
ldarg.0
ldnull
bne.un not_null
ldnull
ret
not_null:
ldarg.1
ldarg.0
callvirt Int32 Invoke(System.String)

You still have to puzzle through it, but’s a lot easier to see what went wrong (that return from the passed delegate needs to be converted to a string before calling Return()).
But Wait, There’s More
Since Sigil is already doing some correctness validation that requires waiting until a method is “finished” (like making sure branches end up with their “expected” stacks), it has all it needs to automated a lot of tedious optimizations you typically do by hand when using ILGenerator.
For example, “Emit(OpCodes.Ldc_I4, {count})” shouldn’t be used if {count} is between -1 and 8; but who wants to remember that, especially if you’re rapidly iterating?  Similarly almost every branching instruction has a short form you should use when the offset (in bytes, not instructions) fits into a single byte.  Sigil automates all of that, you just call “LoadConstant” or “Branch” and move on.
Sigil also automates picking the appropriate version of some opcodes based on type.  In raw IL, there are separate instructions for loading bytes, ints, arbitrary ValueTypes, and reference types from an array.  Using ILGenerator you’d have to pick the appropriate opcode, but with Sigil you just call “LoadElement()” and the preceding instructions are used to figure it out.
Finally, Sigil detects when the Tailcall and Readonly prefixes can be used and inserts them into the command stream.  It’s not possible to detect when the  Volatile and Unaligned prefixes should be inserted (at least so far as I know), but Sigil does only allow them to be added in conjuction with opcodes they’re legal on which is still better than ILGenerator.
Unconditional Branch Caveat
There is one pain point Sigil does not yet address, though I have plans.  Right now, Sigil requires type assertions immediately after unconditional branches (Br, and Leave to be precise) as it’s incapable of inferring the state of the stack in this case.  This doesn’t come up quite as much as you’d expect, since truly unconditional branches are rare; especially when creating DynamicMethods.
Asserting types is attached to marking labels, and looks like the following:
var il = Emit<Func<int>>.NewDynamicMethod();

var b0 = il.DefineLabel("b0"), b1 = il.DefineLabel("b1"), b2 = il.DefineLabel("b2");
il.LoadConstant("abc");
il.Branch(b0); // jump to b0 with "abc"

il.MarkLabel(b1, new [] { typeof(int) }); // incoming: 3
il.LoadConstant(4);
il.Call(typeof(Math).GetMethod("Max", new[] { typeof(int), typeof(int) }));
il.Branch(b2); // jump to b2 with 4

il.MarkLabel(b0, new[] { typeof(string) }); // incoming: "abc"
il.CallVirtual(typeof(string).GetProperty("Length").GetGetMethod());
il.Branch(b1); // jump to b1 with 3
il.MarkLabel(b2, new[] { typeof(int) }); // incoming: 4
il.Return();

You can assert types along with any MarkLabel call, in cases where Sigil can infer the stack state a SigilVerificationException will be thrown when there’s a mismatch.
Check It Out, Try It Out, Break It
Sigil’s source is on github, and it’s available on Nuget.
While I’ve done a fair amount of testing and converted some projects from ILGenerator to Sigil to flush out bugs, I wouldn’t at all be surprised if there are more.  Likewise, I wouldn’t be shocked if Sigil’s validation has some holes or if it’s too strict in some cases.
So grab Sigil and try it out, I love working on this sort of stuff so don’t be shy about opening issues.