CLI Back-End
Table of Contents
- 2007-01-09
Added documentation about the back-end internal structure.
- 2006-09-07
Creation of st/cli branch.
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
(ECMA-335)
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.
The implementation currently resides in the st/cli branch.
Check out st/cli branch following the instructions found in the
SVN documentation.
Being this a branch, the usual maintainer rules do not apply.
The branch is being maintained by
Roberto Costa.
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.
The branch is still in heavy development and check ins into the mainline
are not planned yet.
Unlike a typical GCC back-end, CLI back-end 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.
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 cil32
target, 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 CLI back-end starts
from GIMPLE and it does not go through RTL at all.
- Though 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.
Though most GIMPLE tree codes closely match what is representable
in CIL, some simply do not.
Those codes could still be expressed in CIL bytecodes by a
CIL-emission pass; however, it would be much more difficult and
complicated to perform the required transformations at CIL
emission time (i.e.: those that involve generating new local temporary
variables, modifications in the control-flow graph or in types...),
than directly on GIMPLE expressions.
Pass simpcil (file
config/cil32/tree-simp-cil.c) is in charge of performing
such transformations.
The input is any code in GIMPLE form; the outcome is still valid
GIMPLE, it just contains only constructs for which CIL emission is
straightforward.
Such a constrained GIMPLE format is referred as "CIL simplified"
GIMPLE throughout this documentation.
The pass is currently performed just once, after leaving SSA form and
immediately before the CIL emission.
This is not a constraint; the only requirement is that the
CIL emission is immediately preceded by a run of simpcil.
simpcil pass is designed to be idempotent and it is perfectly
fine to insert additional previous runs in the compilation flow.
Given its current position in the list of passes,
simpcil does not yet support SSA form (though planned).
This is a non-exhaustive list of simpcil transformations:
- Removal of
RESULT_DECL nodes.
CIL doesn't treat the value
returned by a function in any special way: if it has to be
temporarily stored, this must happen in a local.
A new local variable is generated and each RESULT_DECL
node is transformed into a VAR_DECL of that variable.
- Expansion of
LROTATE_EXPR and
RROTATE_EXPR nodes.
In CIL there no are opcodes for rotation and they have
to be emulated through shifts and bit operations.
A previous expansion may generate better code (i.e.:
it may fold constants) or trigger further optimizations.
- Expansion of
ABS_EXPR nodes (in case of
-mexpand-abs option), of MAX_EXPR and
MIN_EXPR nodes (in case of -mexpand-minmax
option) and of COND_EXPR nodes used as expressions
(not statements).
The expansion requires changes to the control-flow graph.
- Expansion of
LTGT_EXPR, UNEQ_EXPR,
UNLE_EXPR and UNGE_EXPR nodes.
CIL instruction set has some support for comparisons,
but it is not orthogonal. Whenever a comparison is difficult to be
translated in CIL, it is expanded.
- Expansion of
SWITCH_EXPR, when it is not profitable
to have a switch table (heuristic decision is based on case density).
CIL emission pass always emits a SWITCH_EXPR to a
CIL switch opcode. When a low case density makes compare trees
preferable, the SWITCH_EXPR is expanded; otherwise the
SWITCH_EXPR is not modified.
The expansion requires changes to the control-flow graph.
- Expansion of
COMPONENT_REF nodes operating on
bit-fields and of BIT_FIELD_REF nodes.
CIL has no direct support for bit-field access; hence,
equivalent code that extracts the bit pattern and applies the
appropriate bit mask is generated.
Memory access is performed by using INDIRECT_REF nodes.
Beware that such nodes on the left-hand side of an
assignment also requires a load from memory; from the memory
access point of view, the operation cannot be made atomic.
- Expansion of
TARGET_MEM_REF nodes.
Emission of such nodes is not difficult;
however, a previous expansion may trigger further optimizations
(since there is no similar construct in CIL bytecodes).
- Expansion of
ARRAY_REF nodes with non-zero indexes
into ARRAY_REF with zero indexes.
CIL emission of such nodes is not difficult;
however, a previous expansion may generate better code (i.e.:
it may fold constants) or trigger further optimizations
(CIL arrays cannot be used for C-style arrays).
Remark that such a simplification must keep ARRAY_REFs,
they cannot be replaced by INDIRECT_REF nodes in order
not to break strict aliasing.
- Expansion of
CONSTRUCTOR nodes used as right-hand
sides of INIT_EXPR and MODIFY_EXPR nodes.
Such CONSTRUCTOR nodes must be implemented in CIL
bytecode through a sequence of finer grain initializations.
Hence, initializer statements containing CONSTRUCTOR nodes
are expanded into an equivalent list of initializer statements,
with no more CONSTRUCTOR nodes.
- Rename of inlined variables to unique names.
Emitted variables keep the original name.
In case of variables declared within inlined functions,
renaming them is needed to avoid clashes.
- Globalization of function static variables.
CIL locals can be used for function non-static variables;
there is no CIL feature to do the same with function static
variables. Therefore, those variables have their scope changed
(they become global), and their name as well, to avoid clashes.
- Expansion of initializers of local variables.
In order to simplify the emission pass, the initialization of local
variables (for those that have it) is expanded into the body
of the entry basic block of the function.
Pass cil (file config/cil32/gen-cil.c)
receives a CIL-simplified GIMPLE form as input and it produces
a CLI assembly file as output.
It is the final pass of the compilation flow.
Before the proper emission, cil currently merges GIMPLE
expressions in the attempt to eliminate local variables.
The elimination of such variables has positive effects on the
generated code, both on performance and code size (each of such an
useless local variable ends up in an avoidable pair of
stloc and ldloc CIL opcodes).
The resulting code is no longer in valid GIMPLE form; this is fine
because the code stays in this form only within the pass.
This is conceptually (perhaps not only conceptually) similar to what
done by the out-of-ssa pass; out-of-ssa may
even be more powerful in doing this, since it operates in SSA form.
It may be interesting to move simpcil pass before
out-of-ssa and to avoid any variable elimination in
cil.
To be evaluated.
Here is an overview of how cil pass handles some of
GIMPLE constructs. Many of them are omitted, for which the emission is
straightforward.
- GIMPLE functions are emitted as CIL static methods of
<Module>.
- Local-scope
VAR_DECL nodes are emitted as CIL
locals, global-scope VAR_DECL nodes as static fields of
<Module>.
INTEGER_TYPEs and REAL_TYPEs are
translated into their obvious equivalent CIL scalar types.
BOOLEAN_TYPEs are translated as CIL
int8.
POINTER_TYPEs are translated as CIL native
int.- Data structures of type
RECORD_TYPE,
UNION_TYPE, ARRAY_TYPE and
ENUMERAL_TYPE are emitted as valuetypes with explicit
layout.
Remark that GIMPLE ARRAY_TYPE nodes cannot be emitted
as CIL arrays (which are managed arrays, a specific kind of objects).
Explicit layout is necessary because layout of structures and unions
is already done when code is in GIMPLE form; CIL declarations have to
match the size of such data structures.
- Expressions with
INDIRECT_REF and
ARRAY_REF nodes are emitted as indirect memory
accesses.
Remark that CIL-simplified GIMPLE only allows ARRAY_REF
nodes with zero offset.
- Expressions with
COMPONENT_REF
nodes are emitted as field accesses.
- [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.
Please send FSF & GNU inquiries & questions to
gnu@gnu.org.
There are also other ways
to contact the FSF.
These pages are maintained by
the GCC team.
For questions related to the use of GCC, please consult these web
pages and the GCC manuals. If
that fails, the gcc-help@gcc.gnu.org
mailing list might help.
Please send comments on these web pages and the development of GCC to our
developer mailing list at gcc@gnu.org
or gcc@gcc.gnu.org. All of our lists
have public archives.
Copyright (C) Free Software Foundation, Inc.,
51 Franklin St, Fifth Floor, Boston, MA 02110, USA.
Verbatim copying and distribution of this entire article is
permitted in any medium, provided this notice is preserved.
|
Last modified 2007-01-10
|
|