SharpDevelop Community

Get your problems solved!
Welcome to SharpDevelop Community Sign in | Join | Help
in Search

Daniel Grunwald

ILSpy - Decompiler Architecture Overview

When ILSpy was only two weeks old, I blogged about the decompiler architecture. The basic idea of the decompiler pipeline (IL -> ILAst -> C#) is still valid, but there were several changes in the details, and tons of additions as ILSpy learned about more features in the C# language.

The pipeline has grown a lot - there are now 47 separate steps, while in the middle of February (when the previous architecture post was written), there were only 14.

If you want to follow this post, grab the source code of ILSpy and create a debug build, so that you can take a look at the intermediate steps while I am discussing them. Only debug builds will show all the intermediate steps in the language dropdown.

It's impossible to give a short sample where every intermediate step does something (the sample would have to use every possible C# feature), but the following sample should show what is going on in the most important steps:

static IEnumerable<IEnumerable<char>> Test(List<string> list)
{
    foreach (string current in list) {
        yield return (from c in current where char.IsUpper(c) || char.IsDigit(c) select char.ToLower(c));
    }
    yield return new List<char> { 'E', 'N', 'D' };
}

Take this code, compile it, and then decompile it with a debug build of ILSpy, so that you can take a look at the results of the intermediate steps.

Essentially, the decompiler pipeline can be separated into two phases: the first phase works on a tree representation of the IL code - we call this representation the ILAst. The second phase works on C# code, stored in the C# Abstract Syntax Tree provided by the NRefactory library.

ILSpy uses the Mono.Cecil library for reading assembly files. Cecil parses the IL code into a flat list of IL instructions, and also takes care of reading all the metadata. Thus, the decompiler's input is Cecil's object model, giving it approximately the same information as you see when you select 'IL' language in the dropdown.

ILAst

We construct the intermediate representation ILAst. Basically, every IL instruction becomes one ILAst instruction. The main difference is that ILAst does not use an implicit evaluation stack, but creates temporary variables for every write to a stack location. However, the ILAst also supports additional opcodes (called pseudo-opcodes) which are used by various decompiler steps to represent higher-level constructs.

Another difference is that we create a tree structure for try-finally blocks - Cecil just provides us with the exception handler table from the metadata.

Implementation: ILAstBuilder.cs

Variable Splitting

Using data flow analysis, we split up variables where possible. So if you had "x = 1; x = add(x, 1);", that will become "x_1 = 1; x_2 = add(x_1, 1)". We do not use SSA form for this (although there's an unused SSA implementation left over in the codebase), we only split variables up when this is possible without having to introduce phi-functions. The goal of this operation is to make compiler-generated variables eligible for inlining.

Implementation: ILAstBuilder.cs

ILAst Optimizations

  • Dead code removal. We remove unreachable code, because it's impossible to infer any information about the stack usage of unreachable code. Also, obfuscators tend to put invalid IL into unreachable code sections. This actually already happens as part of the ILAst construction, before variable splitting.
  • Remove redundant code
    • Delete 'nop' instructions
    • Delete 'br' instructions that jump directly to the next instruction
    • Delete 'dup' instructions - since ILAst works with variables for stack locations, we can just read a variable twice, eliminating the 'dup'.
  • Simplify instruction set for branch instructions
    • Replaces all conditional branches with 'brtrue'. This works by replacing the 'b*' instructions (branch instructions) with 'brtrue(c*)' (branch if compare instruction returns true). This step makes use the 'LogicNot' pseudo-opcode.
      The goal simply is to reduce the number of different cases that the following steps have to handle.
  • Copy propagation. This is a classical compiler optimization; however, ILSpy uses it only for two specific cases:
    • Any address-loading instruction is copied to its point of use. This ensures that no decompiler-generated variable has a managed reference as type - "ref int v = someVariable;" wouldn't be valid C# code, so we have to instead use "ref someVariable" in the place where "v" is used.
    • Copies of parameters of the current function are propagated, as long as the parameter is never written to. This mainly exists in order to propagate the "this" parameter, so that the following patterns can detect it more easily.
  • Dead store removal. If a variable is stored and nobody is there to read it, then was it really written?
    Originally we removed all such dead stores; but after some users complained about 'missing code', we restricted this optimization to apply only to stack locations. Dead stores to stack locations occur mainly after the removal of 'pop' instructions.

The optimizations are primarily meant to even out the differences between debug and release builds, by optimizing away the stuff that the C# compiler adds to debug builds.

Implementation: ILAstOptimizer.cs

Inlining

We perform 'inlining' on the ILAst. That is, if instruction N stores a variable, and instruction N+1 reads it, and there's no other place using that variable, then we move the definition of the variable into the next expression.

So "stack0 = local1; stack1 = ldc.i4(1); stack2 = add(stack0, stack1); local1 = stack2" will become "local1 = add(local1, ldc.i4(1))". Inlining is the main operation that produces trees from the flat IL.

Implementation: ILInlining.cs

Yield Return

If the method is an iterator (constructs a [CompilerGenerated] type that implements IEnumerator), then we perform the yield-return-transformation.

Implementation: YieldReturnDecompiler.cs

Analysis of higher-level constructs

After inlining, we tend to have a single C# statement in a single ILAst statement. However, some C# expressions compile to a sequence of statements. We now try to detect those constructs, and replace the statement sequence with a single statement using a pseudo-opcode.

We can detect and replace a construct only if it's represented by consecutive statements, so when one construct is nested in another, we first have to process the nested construct before processing the outer construct. Because constructs can be nested arbitrarily, we run all the analyses in a "do { ... } while(modified);" loop. If you select "ILAst (after step X)" in the language dropdown, decompilation will stop after that step in the first loop iteration.

  • SimplifyShortCircuit: introduces && and || operators.
  • SimplifyTernaryOperator: introduces ?: operator
  • SimplifyNullCoalescing: introduces ?? operator
  • JoinBasicBlocks: The decompiler tries to use the minimal possible number of basic blocks. Some optimizations might remove branches and therefore it is necessary to check whether two consecutive basic blocks can be joined into one after such optimizations. It is important to do this because other optimizations like inlining might not work if the code is split into two basic blocks.
  • TransformDecimalCtorToConstant: changes invocations of the "new decimal(int lo, int mid, int hi, bool isNegative, byte scale)" constructor into literals.
  • SimplifyLdObjAndStObj: replaces "ldobj(ldloca(X))" with "ldloc(X)", and similar for other kinds of address-loading instructions.
  • TransformArrayInitializers: introduces array initializers
  • TransformObjectInitializers: introduces object and collection initializers
  • MakeAssignmentExpression: detects when the result of an assignment is used in another expression, and inlines the stloc-instruction accordingly. This is essential for decompiling loops like "while ((line = r.ReadLine()) !null)", as otherwise the loop condition couldn't be represented as a single expression.
    This step also introduces the 'CompoundAssignment' opcode for C# code like "this.M().Property *10;". Only because this step de-duplicates the expression on the left-hand side of the assignment, the "this.M()" method call can be inlined into it.
  • IntroducePostIncrement: While pre-increments are handled as special case of compound assignments; post-increment expressions need to be handled separately.
  • InlineVariables2: this performs inlining again, since the steps in the loop might have opened up additional inlining possibilities. The next loop iteration depends on the fact that variables are inlined where possible.

Implementation: ILAstOptimizer.cs, PeepholeTransform.cs, InitializerPeepholeTransform.cs

To get more of an idea of what is going on, consider the collection initializer "new List<char> { 'E', 'N', 'D' }". In the ILAst, this is represented as 5 separate instructions:

stloc(g__initLocal0, newobj(List`1<char>::.ctor))
callvirt(List`1<char>::Add, ldloc(g__initLocal0), ldc.i4(69))
callvirt(List`1<char>::Add, ldloc(g__initLocal0), ldc.i4(78))
callvirt(List`1<char>::Add, ldloc(g__initLocal0), ldc.i4(68))
yieldreturn(ldloc(g__initLocal0))

The collection initializer transformation will change this into:

stloc(g__initLocal0, initcollection(newobj(List`1<char>::.ctor), callvirt(List`1<char>::Add, initializedobject(), ldc.i4(69)), callvirt(List`1<char>::Add, initializedobject(), ldc.i4(78)), callvirt(List`1<char>::Add, initializedobject(), ldc.i4(68))))
yieldreturn(ldloc(g__initLocal0))

Now after this transformation, the value g__initLocal0 is written to exactly once, and read from exactly one. This allows us to inline the 'initcollection' expression into the 'yieldreturn' statement, thus combining all of the 5 original statements into a single one.

Loop Detection and Condition Detection

Using control flow analysis (finding dominators and dominance frontiers), we detect loops in the control flow graph. A heuristic on a control flow graph is used to find the most likely loop body.

We also build 'if' statements from the remaining conditional branch instructions.

Implementation: LoopsAndConditions.cs

Goto Removal

Goto statements are removed when they are made redundant by the control flow structures built up in the previous step. Remaining goto statements are converted into 'break;' or 'continue;' statements where possible.

Implementation: GotoRemoval.cs

Reduce If Nesting

We try to re-arrange the if statements to reduce the nesting level. For example, if the end of the then-block is unreachable (e.g. because the then-block ends with 'return;'), we can move the else block below the if statement.

Remove Delegate Initialization

The C# compiler will use static fields (and in some cases also local variables) to cache the delegate instances associated with lambda expressions. This step will remove such caching, which opens up additional inlining opportunities. In fact, we will have to move this step into the big 'while(modified)' loop so that we can correctly handle lambda expressions within object/collection initializers.

Introduce Fixed Statements

.NET implements fixed statements as special 'pinned' local variables. As there isn't any representation for those in C#, we translate them into 'fixed' statements.

Variable Recombination

Split up variables were useful for inlining and some other analyses; but now we don't need them any more. This step simply recombines the variables that we split up earlier.

Type Analysis

Here, finally, comes the semantic analysis. All previous steps just transformed the IL code. Some were introducing some higher-level constructs, but those were defined as pseudo-IL-opcodes, which pretty much just are shorthands for certain IL sequences. Semantic analysis now figures out whether "ldc.i4(1)" means "1" or "true" or "StringComparison.CurrentCultureIgnoreCase".

This is formulated as a type inference problem: we determine the expected type and the actual type for each expression in the ILAst. In case some decompiler-generated variables (for the stack locations) weren't removed by the ILAst transformations, we also need to infer types for those.

Implementation: TypeAnalysis.cs

This concludes our discussion of the first phase of the decompiler pipeline. In the next post, I will describe the translation to C# and the remaining transformations.

Published Apr 26 2011, 05:15 PM by DanielGrunwald
Filed under:

Comments

 

lifting facciale said:

Very good and detailed article.

October 18, 2011 4:27 AM
Powered by Community Server (Commercial Edition), by Telligent Systems
Don't contact us via this (fleischfalle@alphasierrapapa.com) email address.