8. Kaleidoscope: Compiling to Object Code

This tutorial describes how to adapt the Kaleidoscope JIT engine into an Ahead of Time (AOT) compiler by generating target specific native object files.

Choosing a target

LLVM has built-in support for cross-compilation. This allows compiling to the architecture of the platform you run the compiler on or, just as easily, for some other architecture. For the Kaleidoscope tutorial we'll focus on just the native target the compiler is running on.

LLVM uses a "Triple" string to describe the target used for code generation. This takes the form <arch><sub>-<vendor>-<sys>-<abi> (see the description of the Triple type for more details)

Fortunately, it is normally not required to build such strings directly.

Grammar

In the preceding chapters the Kaleidoscope implementation provided an interactive JIT based on the classic Read Evaluate Print Loop (REPL). So the grammar focused on a top level rule "repl" that processes individual expressions one at a time. For native compilation this complicates the process of parsing and processing a complete file. To handle these two distinct scenarios the grammar has different rules. For the interactive scenario the previously mentioned "repl" rule is used. When parsing a full source file the "fullsrc" rule is used as the start.

// Full source parse accepts a series of definitions or prototypes, all top level expressions
// are generated into a single function called Main()
fullsrc
    : repl*;

This rule simply accepts any number of expressions so that a single source file is parsed to a single complete parse tree. (This particular point will become even more valuable when generating debug information in Chapter 9 as the parse tree nodes contain the source location information based on the original input stream).

Code Generation Changes

The changes in code generation are fairly straight forward and consist of the following basic steps.

Remove JIT engine support
Expose the bit code module generated, so it is available to the "driver".
Saving the target machine (since it doesn't come from the JIT anymore)
Keep track of all generated top level anonymous expressions
Once generating from the parse tree is complete generate a main() that includes calls to all the previously generated anonymous expressions.

Most of these steps are pretty straight forward. The anonymous function handling is a bit distinct. Since the language syntax allows anonymous expressions throughout the source file, and they don't actually execute during generation - they need to be organized into an executable form. Thus, a new list of the generated functions is maintained and, after the tree is generated, a new main() function is created and a call to each anonymous expression is made with a second call to printd() to show the results - just like they would appear if typed in an interactive console. A trick used in the code generation is to mark each of the anonymous functions as private and always inline so that a simple optimization pass can eliminate the anonymous functions after inlining them all into the main() function.

// mark anonymous functions as always-inline and private so they can be inlined and then removed
if( isAnonymous )
{
    retVal.AddAttribute( FunctionAttributeIndex.Function, AttributeKind.AlwaysInline )
          .Linkage( Linkage.Private );
}
else
{
    retVal.Linkage( Linkage.External );
}

These settings are leveraged after generating from the tree to create the main function. A simple loop generates a call to each expression along with the call to print the results. Once, that is completed a ModulePassManager is created to run the Always inliner and a global dead code elimination pass. The always inliner will inline the functions marked as inline and the dead code elimination pass will eliminate unused internal/private global symbols. This has the effect of generating the main function with all top level expressions inlined and the originally generated anonymous functions removed.

public OptionalValue<BitcodeModule> Generate( IAstNode ast )
{
    ast.ValidateNotNull( nameof( ast ) );
    ast.Accept( this );

    if( AnonymousFunctions.Count > 0 )
    {
        var mainFunction = Module.AddFunction( "main", Context.GetFunctionType( Context.VoidType ) );
        var block = mainFunction.AppendBasicBlock( "entry" );
        var irBuilder = new InstructionBuilder( block );
        var printdFunc = Module.AddFunction( "printd", Context.GetFunctionType( Context.DoubleType, Context.DoubleType ) );
        foreach( var anonFunc in AnonymousFunctions )
        {
            var value = irBuilder.Call( anonFunc );
            irBuilder.Call( printdFunc, value );
        }

        irBuilder.Return( );

        // Use always inline and Dead Code Elimination module passes to inline all of the
        // anonymous functions. This effectively strips all the calls just generated for main()
        // and inlines each of the anonymous functions directly into main, dropping the now
        // unused original anonymous functions all while retaining all of the original source
        // debug information locations.
        using var mpm = new ModulePassManager( );
        mpm.AddAlwaysInlinerPass( )
           .AddGlobalDCEPass( )
           .Run( Module );
    }

    return OptionalValue.Create( Module );
}

Most of the rest of the changes are pretty straightforward following the steps listed previously.

Anonymous Function Definitions

As previously mentioned, when generating the top level expression the resulting function is added to the list of anonymous functions to generate a call to it from main().

public override Value? Visit( FunctionDefinition definition )
{
    definition.ValidateNotNull( nameof( 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 );
        using( NamedValues.EnterScope( ) )
        {
            foreach( var param in definition.Signature.Parameters )
            {
                var argSlot = InstructionBuilder.Alloca( function.Context.DoubleType )
                                                .RegisterName( param.Name );
                InstructionBuilder.Store( function.Parameters[ param.Index ], argSlot );
                NamedValues[ param.Name ] = argSlot;
            }

            foreach( LocalVariableDeclaration local in definition.LocalVariables )
            {
                var localSlot = InstructionBuilder.Alloca( function.Context.DoubleType )
                                                  .RegisterName( local.Name );
                NamedValues[ local.Name ] = localSlot;
            }

            EmitBranchToNewBlock( "body" );

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

            FunctionPassManager.Run( function );

            if( definition.IsAnonymous )
            {
                function.AddAttribute( FunctionAttributeIndex.Function, AttributeKind.AlwaysInline )
                        .Linkage( Linkage.Private );

                AnonymousFunctions.Add( function );
            }

            return function;
        }
    }
    catch( CodeGeneratorException )
    {
        function.EraseFromParent( );
        throw;
    }
}

Driver changes

To support generating object files the "driver" application code needs some alterations. The changes fall into two general categories:

Command line argument handling
Generating the output files

Adding Command Line handling

To allow providing a file like a traditional compiler the driver app needs to have some basic command line argument handling. ("Basic" in this case means truly rudimentary 😁 ) Generally this just gets a viable file path to use for the source code.


// really simple command line handling, just loops through the input arguments
private static (string SourceFilePath, int ExitCode) ProcessArgs( string[ ] args )
{
    string sourceFilePath = string.Empty;
    foreach( string arg in args )
    {
        if( !string.IsNullOrWhiteSpace( sourceFilePath ) )
        {
            Console.Error.WriteLine( "Source path already provided, unrecognized option: '{0}'", arg );
        }

        sourceFilePath = Path.GetFullPath( arg );
    }

    if( string.IsNullOrWhiteSpace( sourceFilePath ) )
    {
        Console.Error.WriteLine( "Missing source file name!" );
        return (string.Empty, -1);
    }

    if( !File.Exists( sourceFilePath ) )
    {
        Console.Error.WriteLine( "Source file '{0}' - not found!", sourceFilePath );
        return (string.Empty, -2);
    }

    return (sourceFilePath, 0);
}

Update Main()

The real work comes in the Main application driver, though there isn't a lot of additional code here either. The general plan is:

Process the arguments to get the path to compile
Open the file for reading
Create a new target machine from the default triple of the host
Create the parser stack
Parse the input file
Generate the IR code from the parse tree
Once the parsing has completed, verify the module and emit the object file
For diagnostics use, also emit the LLVM IR textual form and assembly files


/// <summary>C# version of the LLVM Kaleidoscope language tutorial</summary>
/// <param name="args">Command line arguments to the application</param>
/// <returns>0 on success; non-zero on error</returns>
/// <remarks>
/// The command line options at present are just the source file name
/// </remarks>
[SuppressMessage( "Design", "CA1062:Validate arguments of public methods", Justification = "Provided by Platform" )]
public static int Main( string[ ] args )
{
    (string sourceFilePath, int exitCode) = ProcessArgs( args );
    if( exitCode != 0 )
    {
        return exitCode;
    }

    string objFilePath = Path.ChangeExtension( sourceFilePath, ".o" );
    string irFilePath = Path.ChangeExtension( sourceFilePath, ".ll" );
    string asmPath = Path.ChangeExtension( sourceFilePath, ".s" );

    using var rdr = File.OpenText( sourceFilePath );
    using var libLLVM = InitializeLLVM( );
    libLLVM.RegisterTarget( CodeGenTarget.Native );

    var machine = new TargetMachine( Triple.HostTriple );
    var parser = new Parser( LanguageLevel.MutableVariables );
    using var generator = new CodeGenerator( parser.GlobalState, machine );
    Console.WriteLine( "Ubiquity.NET.Llvm Kaleidoscope Compiler - {0}", parser.LanguageLevel );
    Console.WriteLine( "Compiling {0}", sourceFilePath );

    IParseErrorLogger errorLogger = new ColoredConsoleParseErrorLogger( );

    // time the parse and code generation
    var timer = System.Diagnostics.Stopwatch.StartNew( );
    var ast = parser.Parse( rdr );
    if( !errorLogger.CheckAndShowParseErrors( ast ) )
    {
        (bool hasValue, BitcodeModule? module) = generator.Generate( ast );
        if( !hasValue )
        {
            Console.Error.WriteLine( "No module generated" );
        }
        else if( !module!.Verify( out string errMsg ) )
        {
            Console.Error.WriteLine( errMsg );
        }
        else
        {
            machine.EmitToFile( module, objFilePath, CodeGenFileType.ObjectFile );
            timer.Stop( );

            Console.WriteLine( "Wrote {0}", objFilePath );
            if( !module.WriteToTextFile( irFilePath, out string msg ) )
            {
                Console.Error.WriteLine( msg );
                return -1;
            }

            machine.EmitToFile( module, asmPath, CodeGenFileType.AssemblySource );
            Console.WriteLine( "Compilation Time: {0}", timer.Elapsed );
        }
    }

    return 0;
}

Conclusion

That's it - seriously! Very little change was needed, mostly deleting code and adding the special handling of the anonymous expressions. Looking at the changes it should be clear that it is possible to support runtime choice between JIT and full native compilation instead of deleting the JIT code. (Implementing this feature is "left as an exercise for the reader" 😉)