Luca Veraldi
Dept. of Computer Science, University of Pisa
veraldidi.unipi.it
CCompilerSuite has been thought to be an experimental solution, providing skilled users with a basic as well as complete compiler suite, able to be easly extended with more more advanced features, starting from intermediate code optimizations.
The project has been developed in C++; data structures and visitors come directly from the C++ Standard Template Library.
The project employs a pure RISC-like assembly, with a register-register architecture and few instructions holding the responsibility for memory accessing and modification. This chosen RISC language, we named CIL, does not have any known real implementation and is only intended to satisfy didactic purposes.
The project is clearly divised into the following tools:
They complete as a whole the compiler suite. The rest of this Manual is organized as follows: Section 2 deals with the specific characteristics and advanced features of the Compiler, describing command-line arguments, structure of intermediate files and analyzing source syntax recongnized by the parser. It also deals with the optmizations the Compiler takes on the Abstract Syntax Tree and with the partial evaluator for constant expressions. Section 3 deals with the interface of the CIL Assembler and describes its input parameters.
Section 4 introduces a simple implementation of the CIL language and describes the interpretation of assembly instructions; finally, Section 5 shows the Debugger interface and describes its commands. Notes about project compiling and licencing eventually end up the documentation.
Equavalent to gcc option;
This is an experimental feature not yet available, at the current developing status of the project;
This option will also enable lots of warning regarding extensions to usual ANSI-C syntax, like return type defaulting to int for functions declarations.
Several warnings, considered particularly dangerous, are always enabled, no matter the option is given or not: these warnings are most related to the partial evaluator engine, to mismatching parameter number for functions or const qualifier discarding in assignments.
Equavalent to gcc options ;
Equivalent to gcc option;
Equivalent to gcc option;
|
instead of |
|
|
instead of |
|
Pruning actions are taken while parsing the source code and are always related to C declaration, expressions or statements which would have no effects for the semantics of the program. Empty declarations; forward type or variable declarations, that are required for correct source parsing but will not end up into the final AST; useless cast expressions; goto statements pointing to the immediately following statement; empty case or default statements in switch blocks and similiar things are typical pruning subjects.
Moreover, pruning is also related to source code rewriting: the Compiler supports several semantics-invariant reconstructions of the original source tree, in a more compact or efficient representation, that always result in better intermediate code performances. Such rewriting rules mostly regard the partial evaluator for algebraic expressions and the C selection statements, e.g. if and switch C constructs. The partial evaluator replaces algebric expressions involving constant operands directly with their constant result, on-the-fly.
If statement rewriting rules regard constructs with a constant predicate: If statements with false predicate are directly replaced with the else branch, if any; when the predicate appears to be always true, the if construct is replaced with the then branch, if any, instead.
Analogous considerations apply to switch blocks: if predicate appears to be constant expression, the switch statement is passed through a partial evaluator which eliminates typical sequence of jumps with the code corresponding to the correct case block, if one exists, of with the default label, preserving semantics of original code. Moreover, switch statements with only a single case or default label are rewritten as simple if statements, preserving original semantics.
Finally, rewriting takes place whenever postfix side effects are present in algebraic expressions; in these cases, the expression will be rewritten in a semantically equivalent way, with all side effects removed (really, postponed). The side effect-related statements will get inserted by the Compiler in an artificial way, at the end of the expression evaluation, in the form of simple increment/decrement statements, preserving standard C evaluation rules.
Actually, the register memory is used by the Compiler as a pure associative cache, with a simple LRU-based eviction algorithm. During low level instruction generation, the Compiler will therefore keep track of which symbolic values are stored in which register, within the Virtual Machine.
Whenever a temporary value needs to get reused, the register cache is queried for the requested value: if a register with that value is still available and did not already get evicted, it is used for further expression evaluation. Only in the case the value is not already present in current register snapshot, the corresponding expression requires evaluation and low-level assemble code will be consequently generated. Clearly, this saves the need for additional recomputation of shared sub-expressions in the code.
To grant semantic correctness, the virtual snapshot of Virtual Machine register memory kept by the Compiler is refreshed after every function call and function body compilation.
The instruction format is composed by 32 bits, so as to fit a memory word, with no other payloads. The bits are organized as follows (Figure 3):
Instructions requiring less that three arguments obey to a sligthly different format. Test instructions (e.g. IFEQ, IFSLT) take only two arguments and a virtual address, or relative offeset, of the jump target. This constant can use all the remaining bits (therefore, up to 12 bits). The MOV instruction can move a constant to one of the Virtual Machine general-purpose registers. This constant can use all the remaining bits (therefore, up to 18 bits). Finally, the unconditional jump instruction (GOTO), apart from the Operative Code and control bits, uses all the remaining bits (therefore, 24 bits) to express the virtual address of jump target or relative offset. Figure 3 explains the different instruction layouts.
We identify the following instruction categories:
For instructions with less than three arguments, the Operative Code bits assume a quite special meaning, as reported in Figure 3: bits number 0 and 1 are always set to 1; bits number 2 and 3 represent the number of arguments the instruction will take (00 for no arguments at all, 01 for only one argument and 1- for more arguments); remaining bits simply distinguish instructions inside their category.
Additional control bits specify the interpretation of arguments inside Virtual Machine: specifically, they identify arguments as being either constant values or indexes for general-purpose registers.
For instruction taking three arguments, second and third arguments can be either a signed integer constant or a register index. So, constants which can be expressed as payload arguments in such instructions range from to .
Test instructions can jump to either a relative, signed offset constant, therefore ranging from to , or to the relative signed offset stored in one of the Virtual Machine general-purpose registers.
Moreover, we can move integer constants into Virtual Machine registers with the MOV instruction, if constants range from to . Otherwise, register-to-regsiter copy is required.
Finally, the unconditional jump instruction can jump to a relative, signed offset constant, therefore ranging from to , or to the relative signed offset stored in one of the Virtual Machine general-purpose registers. Moreover, bare goto statements in source can be translated as CIL absolute jump instructions, i.e. relative to the 0 initial virtual address generated by the Compiler.
Category | Code Mask | Instructions | ||||||||||||
Short math | 000 -- | ADD SUB SHL SHR | ||||||||||||
Long math | 001 -- | MUL DIV MOD SQRT POW LOG | ||||||||||||
Comparison | 010 -- |
|
||||||||||||
Bit-to-bit | 011 -- | IFEQ IFNE AND OR XOR | ||||||||||||
Memory | 100 -- | LOAD LOADS LOADB STORE STORES STOREB | ||||||||||||
Trigonometry | 101 -- | SIN COS TAN ASN ACS ATN | ||||||||||||
Others |
|
|
These considerations raise problems, when backpatching jumps: whenever an unknown address need to be used in a earlier place in code, we remember the place the instruction occurred at and the target address it depends on. As soon as this address will be generated by the Compiler, e.g. because we eventually encounter the function implementation we previously called, all instructions depending on this address need to get backpatched with the actual constant. The constant has to be either the absolute virtual address of the required instruction or a relative offset from the referring one in code.
If such constant does not fit the instruction format, it needs to be obtained by some arithmetic manipulations upon registers.
Backpatch is not a novel concept, in compiler theory: here we introduce a backpatching algorithm for our pure RISC-like assembly language. The algorithm clearly shows two phases: in the first one, a least fixed-point is computed, upon constant jump values; in the second one, instructions requiring backpatching are actually fixed with the correct constant, if it fits the instruction format, or required code is properly added before it, to obtain the constant as well.
Figure 4 shows involed data structures. During intermediate code generation, in the Compiler back-end, we collect a list of instructions requiring backpatching, i.e referring to not-yet-generated virtual addresses, and also collect for each instruction the virtual address it appeared at (required to compute the relative offset in code, as required).
|
At the end of the intermediate code generation phase, the backpatched algorithm is run: for each collected instruction in the list, we compute source address (the address it appeared at) and destination one (i.e. the address of the required jump target). Then we compute the jump constant, depending on the instruction type and decide weather or not the constant fit the instruction format, w.r.t. the limits exposed previously. If constant does not, we have to obtain it in an alternative way. Usually, a MOV instruction will resolve the problem, allowing to cope with constants in a wider range, than the one allowed for conditional jumps. Otherwise, elementary arithmetic on constant and registers is used.
If the constant does not fit the instruction format, additional instructions need to be added before the one being backpatched: either a single MOV instruction, or several arithmetic instructions. Therefore, while executing the algorithm, we simulate the code completion and take into account additional instructions to be generated.
With special reference to loop constructs, the addition of one or more instructions to the generated code may invalidate previously computed jump constants. Moreover, the same activity will shift down virtual addresses for functions and labeled statements, influencing call instructions and forced GOTO, as well. For this reason, a least fixed-point computation is involved.
To take into account the addition of new instructions to the one already prepared at the end of Compiler back-end phase, we use an AVL binary search tree, i.e. an automatically rebalancing tree, where each node contains the accumulated number of instructions added up to that point in code. This values are used when computing relative offsets and absolute virtual addresses for jumps, being the original ones plus the accumulated displacement found in the correct position of the AVL tree.
At the end of the least fixed-point computation, the second phase of the algorithm starts, where binary instruction formats actually get backpatched and required additional instructions added to the code, in the correct place.
Either way, if successful, the binary file produced can be directly executed by the CIL Virtual Machine, which represents an implementation of the assembly dialect and can, therefore, interpret the binary instruction formats.
Binary files have the following layout:
On function return, it is at the caller's reponsibility to restore the stack pointer to its correct position in virtual memory, eventually popping function result, as needed, and assigning the stack frame pointer the original value it had before the call took place.
The intermediate assembly language provide for two instructions, directly managing the stack: PUSH and POP. An reserved integer Virtual Machine register, RG[stack], is always allocated to contain the current pointer to the first free byte in the stack. These instructions are actually only mnemonic shortcuts for STORE and LOAD, respectively, being the only memory-register class instructions. The different operative codes for stack-related instructions allow for fewer parameters, in instruction format (address of the stack is fixed and implicitly obtained by the value of the RG[stack] register).
Moreover, the interpreted program can directly modify the stack pointer, with usual register manipulation instructions, therefore reserving or releasing byte blocks of stack memory with simple ADD or SUB instructions. The Virtual Machine will treat the interpreted program's stack a a vector of byte, being the value of RG[stack] simply the pointer of &stack[0]. An initial default stack size is reserved, upon program interpretation startup.
On the top of the stack, it is logically positioned the heap allocation area, managed through conventional call to malloc and free runtime support functions. The interpreted program and its Virtual Machine actually share their virtual address space: therefore, the heap of the interpreted program is shared with the one of the Virtual Machine itself.
The provided Makefile allows to build two different configurations of the project: release and debug. Debugging configuration has been useful, during feature implementation phase, and maybe it is of any interest for final users, any more.
The release option, instead, is the configuration which enables all solution code optimizations and produces highly lightweight and efficient executables for the suite tools. Compiling in release configuration may take a while, due to the heavy employment of inlining features in solution codes, and to the compiling options, which include several expensive assembly-level optimizations.
To compile the suite, just type the following command at the command prompt: make release install. The generation of this project documentation is achieved through make doc, instead.
After the compiling phase successful termination, in the bin/ directory under the project root will appear three links to the suite tool binaries: CCompiler for the Compiler, CilVM for the CIL Virtual Machine and CilDbg for the CIL assembly-level Debugger.
Make sure to have all the tools and libraries required correctly installed, before compiling the suite.
under the terms of the GNU General Public License as published
by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.
but WITHOUT ANY WARRANTY; without even the implied warranty
of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the GNU General Public License for more details.
along with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html CCompilerSuiteDoc.tex -split 2 -nonavigation -notop_navigation -nobottom_navigation -noauto_navigation -noindex_in_navigation -antialias_text -transparent -white -show_section_numbers -show_init
The translation was initiated by Luca Veraldi on 2006-04-16