CLI Back-End and Front-End

• GNU Project (original) (raw)

Table of Contents

• Latest news
• Introduction
• Contributing
• The CLI back end
• The CLI front end
• Readings

Latest News

2009-07

Update CLI back end to GCC 4.4, TAG added

2009-06

Add support for vector types (sizes 4, 8, 16 bytes) and some arithmetic operators (add, sub, or, and, xor).

Also support Mono.Simd library with flag -msimd=mono.

2009-04

Update CLI back end to GCC 4.3, TAG added

2009-03

Split branch in two, cli-be and cli-fe, the first contains only the modifications for the CLI Backend, the second instead contains the changes for the CLI Frontend

Update instructions to build a toolchain, with either DotGnu based binutils or the new ones based on Mono library Cecil

2008-09

First implementation of a set of new binutils based on Mono library Mono.Cecil

2008-06-13

Simplified build process of a CIL toolchain. Added binutils for cil as simple wrappers on DotGnu binutils

Added implementation of libc/libm libraries on top of mscorlib that allows most of c applications to be compiled and run on any CIL Virtual Machine

2007-07-10

Added CLI front end

2007-05-14

Roberto Costa steps down as a maintainer, replaced by Andrea Ornstein and Erven Rohou.

2007-01-09

Added documentation about the back-end internal structure.

2006-09-07

Creation of st/cli branch.

Introduction

CLI is a framework that defines a platform independent format for executables and a run-time environment for the execution of applications. The framework has been been standardized by the European Computer Manufacturers Association [1] and by the International Organization for Standardization (ISO/IEC 23271:2006). CLI executables are encoded in the Common Intermediate Language (CIL), a stack-based bytecode language. CLI framework is designed to support several programming languages with different abstraction levels, from object-oriented managed languages to low-level languages with no managed execution at all.

The purpose of this project is to develop a GCC back end that produces CLI-compliant binaries. The initial focus is on C language (more precisely, C99); C++ is likely to be considered in the future, as well as any other language for which there is an interest for a CLI back end.

STMicroelectronics started this project in 2006, as part of the European funded project ACOTES.

In 2007 to explore the potential of .NET as a deployment file format, in collaboration with HiPEAC, we developped also a CIL front end (always using GCC).

The maintainers of the branch areAndrea Ornstein andErven Rohou.

The implementation currently resides in the st/cli branch.

People currently involved in the development or that had worked on it in the past are:

Roberto Costa, Andrea Ornstein,Erven Rohou and Gabriele Svelto.

Contributing

Check out st/cli-be branch.

Being this a branch, the usual maintainer rules do not apply. The branch is being maintained byAndrea Ornstein andErven Rohou. Checking-in into the branch is free, provided that the action was coordinated with the branch maintainer and that the usual contribution and testing rules are followed.

There is a smallREADME file that explains how to build and install the GCC CLI back end and front end and the CLI binutils (both Mono based and DotGnu based) .

The CLI back end

Unlike a typical GCC back end, the CLI backend stops the compilation flow at the end of the middle-end passes and, without going through any RTL pass, it emits CIL bytecode from GIMPLE representation. As a matter of fact, RTL is not a convenient representation to emit CLI code, while GIMPLE is much more suited for this purpose.

CIL bytecode is much more high-level than a processor machine code. For instance, there is no such a concept of registers or of frame stack; instructions operate on an unbound set of local variables (which closely match the concept of local variables) and on elements on top of an evaluation stack. In addition, CIL bytecode is strongly typed and it requires high-level data type information that is not preserved across RTL.

Target machine model

Like existing GCC back ends, CLI is truly seen as a target machine and, as such, it follows GCC policy about the organization of the back-end specific files.

Unfortunately, it is not feasible to define a single CLI target machine. The reason is that, in dealing with languages with unmanaged datas like C and C++, the size of pointers of the target machine must be known at compile time. Therefore, separate 32-bit and 64-bit CLI targets are defined, namely cil32 and cil64. CLI binaries compiled for cil32 are not guaranteed to work on 64-bit machines and vice-versa. Current work is focusing on cil32target, but the differences between the two are minimal.

Being cil32 the target machine, the machine model description is located in files config/cil32/cil32.*. This is an overview of such a description:

• The size of pointers is set to 32 (this is cil32 target, it would similarly set to 64 for cil64). Natural modes for computations go up to 64 bits.
• Alignment rules specify that natural alignment is always followed (more precisely, in the absence of packed attribute).
• Properties exclusively needed by RTL passes are skipped. This is a mere consequence of the fact that the CLI back end starts from GIMPLE and it does not go through RTL at all.
• Though the CLI back end does not reach RTL passes, there is a minimum set of RTL-related description that must be present anyway. For instance, a few instruction selection patterns are mandatory, while others are used by some heuristics for cost estimation; there must be a definition of the register sets and a few peculiar registers have to be defined... As a rule of thumb, the machine model contains the simplest description for these properties, even if this makes little sense for CLI target.

The CIL intermediate representation

In our branch the traditional compilation flow of GCC has been altered to make CIL code emission more robust and to improve the quality of the emitted code. Instead of following the traditional compilation flow of GCC where GIMPLE code is turned back into generic when exiting the SSA-form and then into RTL for further processing (lower-level optimizations, instruction selection, register allocation, scheduling and assembly emission), we remove the RTL passes and translate generic right after the out-of-SSA phase into a specialized IR for further processing.

Our RTL-replacement IR is loosely modeled against GIMPLE tuples, between the two IR formats there are substantial differences but most of the philosophy behind GIMPLE tuples is retained. We kept an eye on the gimple-tuples branch because it will be the middle-end representation in the next release and we wanted to design an IR which would be immediately familiar to people who worked on GCC.

The CIL IR is closely based on the actual CIL instruction with an almost one-to-one relationship. Ideally a single CIL IR element encapsulates all the information and behavior of a single CIL instruction. This format allows us to make the stack-based nature of the CIL code visible in the following passes and greatly simplifies code emission.

GIMPLE to CIL translation pass

GIMPLE/generic code is lowered into CIL code by descending the original trees and expanding them one node at a time. Many GIMPLE statements can be translated into a single CIL statement making the code generation fairly straightforward with each node being translated and implicitly leaving its result on the stack (except for modify statements obviously). Some statements however require significantly more effort. Bit-field extractions and insertions are expanded to multiple CIL statements for example.

Temporary calculation results are usually left on the stack. This is a very natural process during expansion due to the tree-based nature of GCC IRs. However if the order of the operands of a statement has to be change temporaries are created as CIL does not offer any instruction for swapping the contents of two stack slots. Duplication is possible though.

To preserve the semantics of GCC built-in functions we turn into CIL built-ins during this phase and we provide implementations for them in the support library which ships with our back end so that virtual machines which do not recognize them can still execute the code correctly. Other built-ins which can be mapped efficiently on CIL code are expanded in this phase. For example__builtin_memcpy is turned into a cpblk instruction.

CIL-specific optimizations

The GIMPLE/generic conversion phase sometimes emits some fairly poor CIL code. The code quality actually depends much on the depth of the input trees. Very shallow trees like those produced when compiling with -O0 are translated into some very poor code making use of lots of temporaries for holding intermediate results. Under other conditions the pass creates some naive sequences which can be easily recognized and optimized out.

For the above reasons a few optimization passes have been introduced working directly on the CIL IR. Those passes are aware of the evaluation stack existance and try to maximize its usage. Here's a quick run down of those passes:

• Basic blocks reordering: basic blocks are reshuffled to minimize the number of branches in the output code
• Switch expressions break up: switches can be represented in a very compact way in CIL but only if they are dense. Sparse switches result in very large code so we turn them into if-then-else expressions when it is profitable to do so.
• Missing prototypes fix-up: not really an optimization but required nonetheless. C89 function calls without a prototype have their types automatically promoted. This doesn't happen in CIL which identifies functions by their name and exact signature. This phase 'fixes' the unprototyped functions using conversion stubs to undo the automatic type promotion while still reflecting its behavior
• Removal of redundant remporaries and stack promotion: scans the code and locally tries to identify temporary variables and remove them promoting them on the evaluation stack. To implement this phase properly a full DFA should be done but we didn't have time for it yet. Currently this is a sort of glorified peephole optimizer but still manages to obtain very good results with little effort
• Redundant conversions removal: the conversion pass examines a single statement at a time and thus may emit redundant conversions, this pass analyzes the types of the variables on the stack and removes all the redundant conversions it can find
• Peephole optimizations: this pass is used to clean up simple instruction patterns which are emitted by the conversion pass under certain conditions (mostly when dealing with variable argument functions)
• Branch condition replacement: couples of branches (one of which being conditional) are altered so that they can be turned into a single branch plus a fall through if possible.

Assembly emission

The last pass which emits CIL code is fairly straightforward as the intermediate representation maps one-to-one with the CIL code. This phase however contains a few extra functionalities which are not usually required by an assembler emission pass.

After all the functions have been emitted this pass proceeds by emitting the type declarations, as well as the global variables, static variables (including function-static ones) and the string constants.

Finally the pass also supports the emission of extra custom attributes used for representing compiler/JIT hints which cannot be expressed in plain CIL. Those hints are emitted by using the custom attributes mechanism that the CIL standard provides. The additional information includes const and restrict qualifiers for pointers and optionally the basic block frequencies as well as the branch probabilities.

The CLI front end

The objective of the project was to create a new GCC front end able to take a .NET executable as input, and produce optimized native code as output.

This front end, called gcccil, would allow us to achieve two goals:

• The new front end would provide a validation of a complete static compilation path from C to native code using CIL as intermediate format. This would allow using CIL as a distribution format for executables. In this model, the CIL image could be shipped to customers instead of a native executable and each customer could recompile said image for the native platform that he prefers using GCC.
• The front end would provide a way of producing native executables from CIL images.

Gcccil targets primarily assemblies produced by the GCC CIL back end since this is more convenient for achieving the first of the goals mentioned above.

Implemented functionality

Since the time available for the project was limited, it was not possible to produce a complete implementation of the standard. However, the subset implemented is enough to correctly compile some medium sized CIL programs produced by the GCC CIL back end. Basically, everything required to compile assemblies produced by the GCC CIL back end has been implemented and tested.

In particular, the following features have been implemented:

• most base instructions (most of chapter 3 and some opcodes from chapter 4, partition II of ECMA-335),
• calls to static methods (direct and indirect),
• most CIL types (integers, reals, enums, structs, classes) can be parsed and used,
• structs with explicit layout and size,
• constant initializers,
• limited platform invoke (pInvoke) support,
• and other minor things like the volatile prefix, localloc, etc.

Missing functionality

On the other hand, almost every feature which is not required to compile assemblies produced by the GCC CIL back end has not been implemented yet.

This includes:

• object model related functionality (including strings and arrays),
• exceptions,
• garbage collection,
• reflection and support for .NET 2.0 generics.

The main obstacle impeding the implementation of these features is the lack of a runtime library (similar to libgcj) which is necessary to implement virtual machine services like garbage collection and reflection. Also, the standard class library (CORLIB) needs to be ported for this environment.

Implementation overview

Gcccil does not implement its own CLR metadata parser. Instead, it uses Monoto "parse" the input assembly. That is, Mono is used to load the assembly and parse the metadata and types. The front end only has to parse the actual CIL code of each method. Mono provides a comprehensive API to allow this.

Once gcccil has loaded the assembly (or assemblies) to be compiled, it builds GCC types for the all the types declared or referenced in the assembly. For this, the assemblies declaring the referenced types may need to be loaded too.

CIL basic types (int32, intptr, float...) are translated to their obvious GCC equivalent. To translate classes and value types, the GCC_RECORD_TYPE tree node is used. There is some support for class inheritance, although it cannot be tested yet.

Generating types with explicit layout and size requires some additional effort. There is already one language supported by GCC which supports types with explicit layout (ADA), however CIL allows the definition of some types which are not directly translatable using the current GCC infrastructure. In particular, CIL allows to define types with "holes". That is, types of a given size that don't have fields defined for part of their storage (or that don't have fields at all). However, the contents of that storage can be accessed using pointer arithmetic and must be preserved. GCC4NET produces these kind of types very frequently. Some optimization passes of GCC don't expect these types, so a different representation has to be used in these cases.

Once the types have been parsed, gcccil parses the CIL code stream for the methods defined in the assembly in order to build GCC GENERIC trees for them. Translating from CIL opcodes to GENERIC trees should be straightforward once the types are built since CIL opcodes are simple instructions that almost always have a direct translation to GENERIC. The hardest part is using the correct type conversions to get the correct CIL semantics in presence of all the optimizations of GCC.

Gcccil cannot compile some methods if they use some unsupported feature. In those cases, those methods can be skipped, allowing the user to provide a native implementation if necessary.

Readings

[1]

ECMA, Common Language Infrastructure (CLI), 4th edition, June 2006.

[2]

John Gough, Compiling for the .NET Common Language Runtime (CLR), Prentice Hall, ISBN 0-13-062296-6.

[3]

Serge Liden, Inside Microsoft .NET IL Assembler, Microsoft Press, ISBN 073561547.