In this "episode", we are going to build an application that generates and renders the exection graph of a method using QuickGraph and Lutz Reoder's IlReader. The execution graph is directed graph where each vertex is an IL instruction and each edge represent the transition between two instructions, it could be a jump or a simple move to the next instruction. The graph represents the different path that the application can take into your method. If you have access to the content of a method, you can potentially build.

In a future blog, I will use the execution graph to make "smart" test fixture generator by applying basic graph algorithms on the execution graph. In the following of the blog, I assume you have some basic knowledge of IL, Reflection and Reflection.Emit.

Step 1: creating the graph structures

We begin by creating a specialized type of vertex InstructionVertex that will hold a System.Reflection.Emit.Instruction instance:

using System.Reflection.Emit;
public class InstructionVertex : QuickGraph.Vertex
{
    private Reflector.Disassembler.Instruction instruction=null;
    public InstructionVertex(int id):base(id)
    {}
    public Reflector.Disassembler.Instruction Instruction
    {
        get
        {
            if (this.instruction==null)
                throw new InvalidOperationException();
            return this.instruction;
        }
        set
        {
            this.instruction = value;
        }
    }
    public override string ToString()
    {...}
}

Note that the ToString method uses the code Example.cs in the IlReader source to render an Instruction to string.

To generate a strongly-typed BidirecitonalGraph, that we call InstructionGraph, we use the CodeSmith template called AdjacencyGraph.cst located in the Templates directory.

Step 2: Loading the IL instructions of the method

The building of the graph is done by the IlGraphBuilder class. This class takes the type of the method as an argument. It contains one public method BuildGraph that takes a MethodInfo instance as argument as outputs a InstructionGraph instance containing the execution graph.

The code to extract the MethodBody from the method is almost entirely copy pasted from the IlReader sample:

public class IlGraphBuilder
{
    private Type visitedType;
    private ModuleReader reader;
    public IlGraphBuilder(Type visitedType)
    {
        this.visitedType = visitedType;
        this.reader = new ModuleReader(this.visitedType.Module, new AssemblyProvider());
    }
    public InstructionGraph BuildGraph(MethodInfo mi)
    { 
        // get method body using IlReaderr
        MethodBody methodBody = reader.GetMethodBody(mi);
        ...
    }

    private sealed class AssemblyProvider : IAssemblyProvider
    {
        public Assembly Load(string assemblyName)
        {
            return Assembly.Load(assemblyName); 
        }
        public Assembly[] GetAssemblies()
        {
            throw new NotImplementedException(); 
        }
    }
}

Step 3: Building the graph

The MethodBody instance contains the list of Instruction instances and the list of exception handlers. The building of the graph is done in 3 steps:

1. iterate the Instruction list and create the vertices in the graph. We also build a dictionary that associates the instruction offset to the corresponding vertex,

   // new field in the class
   Hashtable instructionVertices;
   ...
   foreach(Instruction i in methodBody.GetInstructions())
   {
       // avoid certain instructions
       if (i.Code.FlowControl == FlowControl.Phi || i.Code.FlowControl == FlowControl.Meta)
           continue;
       // add vertex
       InstructionVertex iv = g.AddVertex();
       iv.Instruction = i;
       // store in hashtable
       this.instructionVertices.Add(i.Offset,iv);
   }
   

2. iterate again over the instructions and add the edges that represent the transitions. This is the tricky part, I use a recursive exploration of the instructions, (this part of the code is a bit heavy for the blog)
3. iterate over the exception handlers to link the different sections: create the link to catch,finally handlers, etc...

Step 4: Drawing the graph

Drawing the graph is straight-foward using the GraphvizAlgorithm class:

GraphvizAlgorithm gv = new GraphvizAlgorithm(g); 
gv.Write(mi.Name);

Analysing some basic flow contructions:

As an application, I going to show the graph of some basic instruction flow like for, while, if, foreach, etc...

public void HelloWorld()
{
    Console.WriteLine("Hello World");
}

public void IfAlone(bool value)
{
    if (value)
        Console.Write("value is true");
}

public void IfThenElse(bool value)
{
    if (value)
        Console.Write("value is true");
    else
        Console.Write("value is false");
}

public void For()
{
    for(int i = 0;i!=10;++i)
    {
        Console.Write(i);
    }
}

public void While()
{
    int i = 0;
    while(i!=10)
    {
        i++;
    }
}

public void TryCatchFinally()
{
    try
    {
        Console.WriteLine("try");
    }
    catch(Exception)
    {
        Console.WriteLine("catch"); 
    }
    finally
    {
        Console.WriteLine("finally");
    }
}

public void TryMultiCatchFinally()
{
    try
    {
        Console.WriteLine("try");
    }
    catch(ArgumentException)
    {
        Console.WriteLine("catch(arg)"); 
    }
    catch(Exception)
    {
        Console.WriteLine("catch"); 
    }
    finally
    {
        Console.WriteLine("finally");
    }
}

public void ForEach(ICollection col)
{
    foreach(Object o in col)
    {
        Console.WriteLine(o);
    }
}

public void ForEachContinue(int[] col)
{
    foreach(int o in col)
    {
        Console.WriteLine(o);
        if (o == 0)
            continue;
    }
}

public void ForEachBreak(int[] col)
{
    foreach(int o in col)
    {
        Console.WriteLine(o);
        if (o == 0)
            break;
    }
}

public void SwitchIt(int value)
{
    switch(value)
    {
    case 0:
        Console.Write("0");
        break;
    case 1:
        Console.Write("1");
        break;
    default:
        Console.Write("default");
        break;
    }
}