Tim Robinson

(The second in what seems to be a day of obscure .NET facts)

While looking at some C++/CLI code in Reflector today at work, we encountered the try ... fault construct.

What's a fault block?

It's like a finally block, but it's only entered in the event of an exception.

So it's like a catch block, then?

Not exactly:

• fault blocks don't have filters like catch blocks do
• At the end of a fault block the exception is implicitly rethrown

Supposedly the benefit of a fault block is performance: that throw; statement at the end of a catch block has the same overhead as any other throw statement, whereas finally and fault blocks incur no runtime overhead. The stack is not unwound when a fault block is entered: fault blocks won't appear in the exception stack trace.

Where do fault blocks show up?

In the code the C++/CLI compiler emits in order to make sure that local variables have their destructors called in the event of an exception.

Daniel Fortunov wrote about an obscure use of duck typing in the C# spec for enumerators:

Although it is common to implement [IEnumerable and IEnumerator] when creating an enumerable class, if you were to drop the interfaces but leave the implementation, your class would still be enumerable by foreach. Voila! Duck-typing!

You can take advantage of this fact for a couple of performance tricks, as demonstrated by many of the standard collection classes in the base class library:

• Declare your IEnumerator<T> implementation as a struct, not a class. This saves you a heap allocation when MoveNext is called.
• Define a Enumerator<T> GetEnumerator() method on your collection class
• Note that you're returning your own struct, not IEnumerable<T>; this avoids a boxing operation. You'll still need to explicitly implement IEnumerator<T> GetEnumerator(), for people who only have an IEnumerable<T> reference to your collection. These performance tricks don't apply when you're making calls through this interface.

When somebody uses foreach over your collection, the compiler sees a series of MoveNext calls and accesses to the Current property, and it emits code to call these efficiently on your struct.

What's more, the code in your struct's methods is a candidate for inlining by the JIT compiler. The segment of the MoveNext method of System.Collections.Generic.List<T>+Enumerator that can throw an exception is split into its own method, apparently for this reason.

I don't claim any kind of definite performance benefits from using these techniques, but it does look like the language designers put some thought into making it possible to use foreach without incurring any overhead compared to some less elegant method.

I'd like to add tail call support to my Lisp compiler. I can think of two approaches to tail recursion:

• Use the .NET tail.call prefix
  • Translate call followed by ret into tail.call followed by ret
  • It's easier to spot this pattern if we put IL in our own data structure before emitting it
  • Our own data structure needs to represent all the IL we use, including labels (for branching) and local variables
  • The label data structure needs a way to represent the target of a branch
  • Note: The tail prefix is a hint that the JIT compiler doesn't have to obey - here's a good explanation of the limitations
• Translate functions that call themselves into loops
  • Our abstract syntax tree doesn't have a way to represent a loop
  • As above, it needs an AST capable of representing branches
  • The F# compiler does this; it's not able to rely on the tail prefix either
  • Can we apply this to functions that call each other recursively? At compile time we might not spot co-recursive functions: F# only allows co-recursive functions if they use the let ... and syntax to define both functions in the same source file.

The ability to represent loops, and control flow in general, seems to be important in your syntax tree. The LLVM approach to this is the basic block:

• One entry point: no branching into the middle of the block
• One exit point: always contains one branch instruction, at the end
• Basic blocks can be connected to form a control flow graph: blocks are vertices, branch instructions are edges
• Control flow graph is: directed (A branches to B); cyclic (A is allowed to branch to A - this is a loop)

How can we represent basic blocks in F#? The intuitive approach means defining a discriminated union:

// An instruction can be a regular opcode, 
//  or a branch to another basic block
type Instruction = CallInstruction of MethodInfo * obj
                 | Branch of BasicBlock

// A basic block is a list of instructions
and BasicBlock = BasicBlock of Instruction list

We have to construct a list of instructions before constructing a basic block. But how do we represent the following?

// C# pseudocode
while (true)
    Console.WriteLine("hello");

// F# abstract syntax tree for the above C#
let instructions =
    [
        Call (writeLine, "hello");

        // How can we branch to something we haven't constructed yet?
        Branch ???
    ]
let program = BasicBlock instructions

The answer is to separate identity of basic blocks from the instructions within them. We could assign names or ids to them. Or, since we're writing F# and not Haskell, we could drop immutability:

// F# abstract syntax tree with mutability - 
//  note property assignment with <-
let program = new BasicBlock()
let instructions =
    [
        Call (writeLine, "hello");
        Branch program
    ]

program.Instructions <- instructions

LLVM does something similar with its C++ API:

// LLVM equivalent in C++

// 'bb' is a basic block within func_main
BasicBlock* label_bb = BasicBlock::Create("bb", func_main, 0);

// First instruction in bb: call puts("hello")
CallInst::Create(func_puts, const_ptr_8, "", label_bb);

// Second instruction in bb: branch back to bb
BranchInst::Create(label_bb, label_bb);

I'm not yet sure of all the implications for my toy compiler, but already I can see some indications about how to structure the code to allow for optimisations like tail calling:

• Structure the entire program as a graph of basic blocks linked by branch instructions
• Abstract syntax trees can't do everything; instead, they appear as instructions within basic blocks
• Construction of basic blocks must be separate from construction of the instructions within them, so that we can refer to a basic block from one of its own instructions
• As it progresses through compiler passes, the program graph starts looking less functional and more imperative, until it eventually represents actual machine instructions
• I should probably read a compiler textbook