Sharp Blade: Code generation

Among the many good reasons to use Freya there's the high quality code generated by its compiler.

Optimizations by the code generator

Most of the following optimizations could be applied to any other imperative programming language. However, not all compilers applies them. The most probable reason is that those optimizations requires more contextual information and, if not programmed with care, may turn code generation a mess.

Aggresive constant folding

Most commercial compilers do a good work calculating constant expressions at compiling time, but Freya's compiler goes a step beyond: we make consistent use of algebraic transformation in order to detect and eliminate constant expressions. There are more reasons for this effort. For instance, string concatenation in the CLR depends on several Concat methods with a changing number of parameters. You can stuff up to four parameters in a single call to String.Concat. If you want to be sure you're generating the best possible code for string expressions, you'll have to play with the associative law to split a complex expression tree into manageable chunks.

Transforming assignments to Result

Freya uses the same technique as Delphi and Eiffel to assign a result value to a function call: you must assign the value to the predefined Result parameter. Unfortunately, the naive code generation algorithm will produce bad code in most cases. Consider this extremely simple property reader:

property Prop: Integer;
begin
    Result := propField;
end;

Optimizing boolean expressions

There are two well known techniques for generating code for simple boolean expressions as comparisons. In both cases, the compiler starts generating code for evaluating both operands. In the first technique, an operator as ceq is added: this operation checks whether the two operands in the top and subtop of the stack are equals, pops those values and pushes the result into the evaluation stack. The second technique, on the contrary, add a beq operation to the code stream. This operation pops both operand values, but the result is not pushed into the stack. Instead, the result decides whether a jump is performed or not. I will momentarily ignore compound expressions for the sake of simplicity.

The latter technique is useful when the comparison is directly used as the conditional in an if, while or repeat statements. On the contrary, the former is better when the comparison result must be assigned to a field or variable, and this includes returning a value from a method as a special case.

Let's suppose we have a method with a boolean result value. When the result expression is not a simple comparison, but involves the or/and logical operators, the compiler has to decide which kind of code generation technique is better. Logical operators require short-circuit evaluation, but comparisons inside the expression are better handled by the other technique. In these cases, our compiler uses a hybrid technique: jumping code is generated for all subexpressions, except the rightmost subexpression in the expression tree. As a result, the generated code is better, both from a speed and space point of view.

Cascading jumps

Though cascading branches are optimized by the peephole optimizer, the code generator still avoids most of the situations that lead into cascading jumps. This is not a redundant optimization: the peephole optimizer have a bad time when code must be generated for debugging.

Most of the detected cases has to do with loop statements and partial if statements inside other control structures.

Field-based properties

When you omit a property implementation, the property is automatically implemented using a hidden field. Inside the declaring class, all references to the property are translated to a reference to the hidden field. Our compiler goes beyond this point, and it also translates internal references to the property from other classes defined in the same assembly. Of course, this is possible because we declare the hidden field as an internal member of the declaring class.

Tail recursion detection

When a method call itselfs as the last statement in an execution branch, that call is considered as a tail recursive call. In the following example, Contains has two tail recursive calls:

method Contains(Value: X): TreeNode;
begin
    var Rslt := Value.CompareTo(Self.Value);
    if Rslt = 0 then
        Result := Self
    else
    begin
        Result := nil;
        if Rslt < 0 then
        begin
            if Left <> nil then
                Result := Left.Contains(Value)
        end
        else if Right <> nil then
            Result := Right.Contains(Value)
    end;
end;

This method, on the other hand, only contains one tail recursive call:

method Visit(Action: Visitor; Level: Integer);
begin
    if Left <> nil then
        Left.Visit(Action, Level + 1);
    Action(Value, Level);
    if Right <> nil then
        Right.Visit(Action, Level + 1)
end;

The compiler can detect these calls and, when some requirements are satisfied, can optimize the code replacing those calls by jumps to the beginning of the method. The method cannot be virtual, and all its parameters must be passed by value, including the hidden Self parameter for non-static methods.

Code generation in Freya

Optimizations by the code generator

See also