Turbo Pascal Internals

Do you still remember Borland Turbo Pascal? The most successful Pascal compiler ever? If the answer is yes then you probably remember that Turbo Pascal was indeed Turbo. A very fast compiler which generated quite fast executable code. It featured integrated development environment (IDE) where you could edit, run and debug your programs. Originally created as Blue Label Pascal by Anders Hejlsberg, it was licensed by Borland as Turbo Pascal in early 1980s. Last version for DOS was released in 1992 as Turbo Pascal 7.0. Borland also released similar compiler for Windows and later a brand new product Delphi--Rapid Application Development tool for Windows.

Have you ever wondered what makes Turbo Pascal a fast compiler? Well, if you are interested in Turbo Pascal internals here are described some basic units consisting this compiler. Turbo Pascal design is not conventional as taught in compiler design books. Its design is oriented toward speed. The parser is tightly connected with code generator. There is some low-level intermediate code, but most of the raw code is generated by the parser.

A great example of data structures and algorithms used in Turbo Pascal is TPC16. TPC16 is a Turbo Pascal compatible compiler. It generates unit and executable files compatible with Turbo Pascal 7.0 command line compiler. TPC16 is written in Turbo Pascal. It is consisted of many units described below.

Common Variables
Here are declared all global variables that are used by the compiler. Declarations are grouped into sections. Some sections declare variables which hold data for particular module which is compiled and these variables are saved (pushed) during processing of used units.

Reserved Words
This unit declares a symbol table holding all reserved words. It is separated from other units because the file includes also hash values for reserved words which are generated by a separate program.

Type Definitions
This unit defines data structures that define basic Pascal types (integer, real, extended, Boolean, char, string, file, set, array, object, etc). Unit also contains functions to test type compatibility, symbol table type storage and type processing.

I/O Utilities
Routines for reading and writing files are located in the I/O Utilities unit. This unit also contains procedures for error handling and error reporting.

Symbol Table Management
Symbol table management is one of the most important internal operations in every compiler. This unit contains procedures to create symbol table, insert identifiers into symbol table, search symbol table for some identifier, search unit, procedure or record scope for particular identifier, and all other operations with symbol tables.

Scanner
Here are located procedures that scan source file and generate a stream of tokens. Token is the smallest element of the source which is processed by the parser. Scanner processes source files, skips comments, processes compiler directives, and generates tokens.

Parser
This is the brain of the compiler. It reads tokens, checks language syntax and generates intermediate code. One of the reasons for fast compilation lies in parser. Since it generates code which is close to executable code, the next steps of compilation are pretty fast.

Statements
This unit processes Pascal statements (for, while, repeat, while, etc.), begin-end blocks and assembler blocks.

System Functions
This unit processes system functions like abs, arctan, chr, int, odd, ofs, etc. and generates code for them.

System procedures
This unit processes system procedures like exit, fillchar, writeln, inc, val, etc. and generates code for them.

Expressions
This is the biggest unit and contains functions and procedures to process expressions. Expression is anything that needs to be calculated--from a simple identifier to complex expression in multiple parentheses. There are many cases that need to be tested and processed. Procedures in this unit also generate the majority of the code.

Calculator
This unit contains procedures to process various calculations. Calculation is some operation with one or two expressions (addition, subtraction, multiplication, etc.)

Assembler
This is the inline assembler that processes instruction in an asm-end block.

Assembler Types
This unit declares data structures that are needed for inline assembler.

Code Generator
This unit processes intermediate code and generates executable code and reference data needed in linker. Code generator also performs code optimizations.

OMF Import
This unit imports OMF object files and processes OMF records.

Linker
This unit generates the final executable code and creates output files. Before the code is generated each referenced item is recursively processed and marked. Unmarked items are not executed and therefore not included in the final executable code.

There are many excellent books on compiler design and implementation. However, the best book on compiler design is the compiler itself. If you are interested in Turbo Pascal internals or just need a source code of some real compiler then you should examine the Turbo Pascal compiler source code - Turbo Pascal compiler written in Turbo Pascal. This source code shows all the beauty of the Pascal programming language and reveals all the tricks needed to build a fast and compact compiler for any language, not just Pascal.

Compiler Optimizations

The task of every compiler is to translate high-level language source code to machine code that will run on target processor. This may be achieved through assembly language file or by linking object files, the ultimate goal of every compiler is to generate code for the target processor. In principle this is a simple task. Every high level statement can be translated in a series of target instructions. However, without some optimizations this code would be very inefficient. Unoptimized code still works, but it is slower and the files are bigger.

The nature of high-level statements is to operate with variables. Loading and storing of variables can happen in any order. But transfers from and to memory are slower comparing to transfers between registers. And if some value is stored to memory location and immediately after it is needed again in a different calculation, then it doesn't make sense to load it again since it was already present in some register. With proper register loading we can save a lot of redundant loads and stores. There are many optimization algorithms to make the code as efficient as possible. In fact, the compiler optimization is a science. There are many books written on this subject.

Most optimization algorithms are based on control and data flow analysis. There are many optimization approaches: to reduce jumps, to remove dead, redundant or common code, to remove redundant loads and stores, to use registers efficiently, to replace slow instructions with faster ones, to replace specific arithmetic calculations with short instructions, etc. Each optimization is based on some code or data properties. Some of the common optimizations include: constant folding, integer arithmetic optimizations, dead code elimination, branch elimination, code-block reordering, loop-invariant code motion, loop inversion, induction variable elimination, Instruction selection, instruction combining, register allocation, common sub-expression elimination, peephole optimizations, etc.

The basic rule of every optimization is that the original functionality of the program should not be changed. All optimization algorithms are based on the assumption that the program under analysis is the only one who changes memory locations. In reality interrupts or hardware ports can break this rule. Therefore proper actions must be taken to prevent optimizations on memory locations which might be modified outside the code we are trying to optimize. An additional programming technique that complicates optimizations is using pointers. But with proper analysis it is possible to apply safe optimizations on most parts of the code.

You can optimize the code for speed or for code size. In each case the program runs faster or occupies less memory. The later is extremely important in embedded programming where the memory of microcontrollers is limited. Compiler optimizations are an important part of every compiler. Unoptimized code is a waste of memory and time on any target system.

A practical example of  compiler optimizations in action is the Pascal compiler for 8051 microcontrollers which uses Turbo Pascal syntax and generates optimized code. If you are interested in practical compiler construction you can examine the Turbo Pascal internals. This is Turbo Pascal compiler written in Turbo Pascal which can be used as an excellent book on compiler design.

Compiler Design - Practical Compiler Construction

Good optimizing compiler is a must for any computer platform. The availability and quality of compilers will determine the success of the platform. Compiler design is a science. There are numerous books written about compiler principles, compiler design, compiler construction, optimizing compilers, etc. Usually compilers are part of the integrated development environment (IDE). You write a program in some high-level language, click compile and a moment later you get executable code, assembler listing, map file and a detailed report on memory usage.

As a programmer and IDE user you expect fast compilation and optimized generated code. Usually you are not interested in compiler internals. However, to build your own compiler you need a lot of knowledge, skills and experience. Compiler construction is a science. Compilation is a symphony of data structures and algorithms. Storing compiler data in proper structures and using smart algorithms will determine the quality of the compiler. Compilers usually have no user interface, they process source files and generate output files: executable code, object file, assembler source, or any other needed file.

Why are compiler data structures so important?

Compiler needs to store identifiers in symbol tables. Each identifier has some attributes like type, size, value, scope, visibility, etc. Compiler must be able to quickly search the symbol table for particular identifier, store new identifier into symbol table with minimum changes to it, etc. To satisfy all these requirements it is mandatory to carefully design symbol table structure. Usually hash tables are used for quick search and linked lists for simple addition or deletion of elements. Symbol table management is one of the critical elements of any compiler. Another important internal data structure is intermediate code representation. It is a code that is generated from the source language and from which the target code is generated. Intermediate code is usually used to apply optimizations, so right form of intermediate code with general syntax and detailed information is crucial for successful code optimizations.

To convert source code to target instructions is not a big deal. A limited set of registers can sometimes require some smart register saving techniques, but in general each source language statement can be translated into a set of target instructions to perform required effect. If you do not take actions to optimize the generated code you will have a very inefficient code with many redundant loads and register transfers. Excellent optimizations are the shinning jewel of any compiler. With some average optimizations you can easily reduce generated code size for 10% or more. Code size reduction in loops means also increased execution speed. There are many algorithms for compiler optimizations. Most are based on control flow and data flow analysis. Optimizations like constant folding, integer arithmetic optimizations, dead code elimination, branch elimination, code-block reordering, loop-invariant code motion, loop inversion, induction variable elimination, instruction selection, instruction combining, register allocation, common sub-expression elimination, peephole optimization and many others can make initially generated code almost perfect.

If you have ever tried to write a compiler then you probably already know that this is not a simple task. You can use some compiler generators, or write the compiler from scratch. Compiler construction kits, parser generators, lexical analyzer generators (lexers), optimizer generators and similar tools provide the environment where you define your language and enable the compiler construction tools to generate the source code for your compiler. However, to make a fast and compact compiler you need to design your own compiler building blocks, from architecture of symbol tables and scanner to code generator and linker. Before you start reinventing the wheel it is a good idea to read some books about compiler design and examine the source code of some existing compiler. Writing your own compiler can be a great fun.

There are many excellent books on compiler design and implementation. However, the best book on compiler design is the compiler itself. Take a look at Turbo Pascal compiler written in Turbo Pascal. This source code shows all the beauty of the Pascal programming language. It reveals all the tricks needed to build a fast and compact compiler for any language, not just Pascal.