Table of Contents

3.5 Kaleidoscope: Generating LLVM IR With optimizations

This chapter focuses on the basics of optimization with LLVM IR. It diverges from the official tutorial where that mixes the optimization with the use of a JIT. This sub chapter is attempting to isolate those and was born as a means to test/validate the core library and optimization without a JIT (The JIT wrappers didn't exist yet).

The general goal is to parse Kaleidoscope source code to generate a Module representing the source as optimized LLVM IR. This is broken out as a distinct chapter to help identify the support for profiling and how it is different from the LLVM source samples that link directly to the LLVM libraries (That is, the samples are written in C++ AND use the C++ pass builder and management support that is NOT exported via the stable LLVM-C API. This level of functionality is only available as the legacy pass management system with VERY limited support in the LLVM-C API. [It is so legacy now that almost ALL remnants of it are removed from the LLVM-C API, not just deprecated])

Code generation

The Core of this sample doesn't change much from Chapter 3. It simply adds module generation with optimized IR. To do that there are a few changes to make. In fact the optimizations provided don't do much and the resulting IR is much the same. [Coming up with a more complex Kaleidoscope sample that actually uses the optimizations more is left as an exercise for the reader. 😉 ]

Initialization

The code generation maintains state for the transformation as private members. To support optimization generally only requires a set of named passes and to call the method to run the passes on a function or module. [Technically an overload provides the chance to set PassBuilderOptions but this sample just uses the overload that applies defaults.] The new pass management system uses the string names of passes instead of a distinct type and named methods for adding them etc...

These Options are initialized in a private static member for the passes.

private readonly Module Module;
private readonly DynamicRuntimeState RuntimeState;
private readonly Context Context;
private readonly InstructionBuilder InstructionBuilder;
private readonly Dictionary<string, Value> NamedValues = [];
private static readonly LazyEncodedString[] PassNames = [
    "default<O3>"u8
];

Special attributes for parsed functions

Warning

When performing optimizations with the new pass builder system the TargetLibraryInfo (Internal LLVM concept) is used to determine what the "built-in" functions are. Unfortunately, they leave little room for manipulating or customizing this set (In C++ there is some "wiggle room", in LLVM-C there is NO support for this type at all!). Unfortunately, that means that if any function happens to have the same name as the TargetLibraryInfo for a given Triple then it will be optimized AS a built-in function (even if not declared as one) unless explicitly declared as "not" at the call site with an attribute. This is an unfortunate state of affairs with the LLVM support for C++ and highly problematic for C based bindings/projections like this library. Fortunately, there is a scapegoat for this. The function can include a nobuiltin attribute at the call site to prevent the optimizer from assuming the call is to one of the well known built-in functions. This isn't used for Kaleidoscope. But does leave room for problems with names that match some arbitrary set of "built-in" symbols.


// Retrieves a Function for a prototype from the current module if it exists,
// otherwise declares the function and returns the newly declared function.
private Function GetOrDeclareFunction( Prototype prototype )
{
    if(Module.TryGetFunction( prototype.Name, out Function? function ))
    {
        return function;
    }

    var llvmSignature = Context.GetFunctionType( returnType: Context.DoubleType, args: prototype.Parameters.Select( _ => Context.DoubleType ) );
    var retVal = Module.CreateFunction( prototype.Name, llvmSignature );

    int index = 0;
    foreach(var argId in prototype.Parameters)
    {
        retVal.Parameters[ index ].Name = argId.Name;
        ++index;
    }

    return retVal;
}

Function Definition

The only other major change for optimization support is to actually run the optimizations. In LLVM optimizations are supported at the module or individual function level. For this sample each function definition is optimized as each is returned individually. That will change in later chapters. Thus the only real change is after generating a new function for a given AST definition the optimization passes are run for it. This involves calling one of the overloads of the TryRunPasses function and then checking for errors.

public override Value? Visit( FunctionDefinition definition )
{
    ArgumentNullException.ThrowIfNull( definition );

    var function = GetOrDeclareFunction( definition.Signature );
    if(!function.IsDeclaration)
    {
        throw new CodeGeneratorException( $"Function {function.Name} cannot be redefined in the same module" );
    }

    try
    {
        var entryBlock = function.AppendBasicBlock( "entry" );
        InstructionBuilder.PositionAtEnd( entryBlock );
        NamedValues.Clear();
        foreach(var param in definition.Signature.Parameters)
        {
            NamedValues[ param.Name ] = function.Parameters[ param.Index ];
        }

        var funcReturn = definition.Body.Accept( this ) ?? throw new CodeGeneratorException( ExpectValidFunc );
        InstructionBuilder.Return( funcReturn );
        function.Verify();

        // pass pipeline is run against the module
        using var errInfo = function.ParentModule.TryRunPasses( PassNames );
        return errInfo.Success ? (Value)function : throw new CodeGeneratorException( errInfo.ToString() );
    }
    catch(CodeGeneratorException)
    {
        function.EraseFromParent();
        throw;
    }
}
Edit this page