The following is documentation I created after reverse engineering the Turbo Pascal 3.01A compiler. While many features, e.g. units and objects, have been added, today's compiler is still related to the old code.
Before you flame me about stuff that has been fixed, remember that this is about an OLD version of the compiler.
NEW: This file will generate disassembled, commented source from YOUR 3.01A compiler -> SCG.ZIP
Compiler Structure
Compilers usually consist of the following functional groups:
Lexical analysis
Syntactical analysis (parser)
Optimizer
Code generator
Symbol table manager
Error handler
TURBO Pascal isn't your usual compiler... The parser is interspersed with portions of the code generator, and there is no optimizer. Most compilers need multiple passes to do their work, but TURBO is a (faster) single pass compiler.
Fortunately, programming languages of the Pascal type are designed with simple compilation in one pass in mind. All symbols must be defined before they are used. The compiler can easily determine the type of a constant without looking ahead:
symbol
$7FFF
12345
12345.5 - This is an exception. TURBO first verifies whether a numeric constant is an integer or a real constant. Actually, a standard Pascal compiler doesn't have to do this - standard Pascal requires that the integer section of a real constant be a valid integer number !
09CFH - This notation (used by many assemblers and languages) is a negative example. Compilers - like people - read from left to right. To read a number in this notation, it has to be read into a buffer to recognize its type, then it can be converted. Guess why TURBO uses $ for hex numbers... I wonder why Niklaus Wirth chose this notation for Modula-2.
Lexical Analysis
The task of the lexical analysis is to read the source code from memory or from an include file, to eliminate comments and to recognize compiler directives, symbols and keywords.
It is called by the parser. On each call a language element (keyword, symbol, constant...) is read. The starting position is stored. If an error is recognized the editor will be started and the cursor will point to this position.
Parsing Program Structures
The task of this part of the compiler is to analyze the structure of the program to be compiled and to check the syntax. Like most Pascal compilers, TURBO uses a recursive descent parser. The code generation is included in the parser.
The compilation of program structures is quite simple. Usually the syntax is described in Backus-Naur form or by a "railway diagram". As an example the IF statement will be covered.
IF cond THEN stat1 { ELSE stat2 }
___________________
____ ______ ______ ___________ / \
->_IF_->_expr_->_THEN_->_statement_-<> -->
\______ ___________/
_ELSE_->_statement__
After reading an element, the parser takes the applicable track. If there isn't any the syntax is incorrect, and an error is reported.
It is possible to have a parser generated automatically by a so called compiler-compiler, if the Backus-Naur form of the syntax is given. Unfortunately this doesn't help very much: The really difficult parts of a compiler - code generation and optimization - must still be written manually.
How is the IF statement translated ? (The corresponding section in the compiler is at offset 6C12). The statement procedure reads an IF and calls the IF procedure. First the condition - actually an arithmetic expression of type boolean - is evaluated. This is done by calling the expression procedure. The expression is read until an illegal symbol (THEN) is found. This terminates the expression, which is checked for type boolean. The IF procedure inserts a conditional jump to the end of statement 1 here. The displacement is inserted later - it is not yet known. If the expression has been terminated by something else than a THEN, an error is reported. Now the first statement (stat1) is translated. Actually, this is a RECURSIVE call of the statement procedure (That's why this is a recursive descent parser). Please note that the syntax definition is recursive, too ! Because of possible nested IF statements the variables of the IF procedure are saved on the stack. After this statement, an ELSE may follow. If it does, a jump to the end of stat2 is emitted and the jump from the beginning of stat1 is patched, then the second statement is translated and the second jump patched.
The code produced looks like this:
(IF..THEN) (IF..THEN..ELSE)
cond cond
JNZ l1 JNZ l1
JMP l2 JMP l2
l1: stat 1 l1: stat 1
l2: ... JMP l3
l2: stat 2
l3: ...
The long jump at the beginning isn't always necessary. Unfortunately, the compiler cannot predict how long the statement will be. To improve this, the jump would have to be replaced by a short one and the subsequent code moved, which would complicate the compiler quite a bit.
All other program structures are translated in a similar way.
Parsing Arithmetic Expressions
The evaluation of expressions is somewhat more complex, as the precedence of the operations has to be taken into account. The solution in TURBO is, however, quite simple (code starting at 7A70).
Expressions are usually translated to reverse polish notation (as used on Hewlett-Packard calculators and in the programming language FORTH).
There are five groups of operations:
negation (highest precedence)
NOT
multiplication, division, ...
addition, subtraction, ...
comparisons, IN (lowest precedence)
This translates into the following program structure:
PROCEDURE atom; { element }
BEGIN
CASE op OF
CONST:read constant
VAR :read variable { indexing -> recursive }
'(' :read expression { recursive }
')' must follow
func :read parameters { recursive }
emit function call
TYPE :'(' must follow { type conversion, e.g. Integer(TRUE) }
read expression { recursive }
')' must follow
convert type -> type wanted
ELSE syntax error;
END;
END;
PROCEDURE neg; { negation - }
VAR negflag:BOOLEAN;
BEGIN
negflag:=(op=neg);
atom;
IF negflag THEN emit negation;
END;
PROCEDURE NOT; { NOT }
VAR notflag:BOOLEAN;
BEGIN
notflag:=(op=NOT);
neg;
IF notflag THEN emit NOT;
END;
PROCEDURE mult_level; { multiplication ... }
VAR mult_op:operation;
BEGIN
NOT;
WHILE op IN mult_ops DO BEGIN
save the result;
mult_op:=op;
NOT;
emit operation(mult_op);
END;
END;
PROCEDURE add_level; { addition ... }
VAR add_op:operation;
BEGIN
mult_level;
WHILE op IN add_ops DO BEGIN
save the result;
add_op:=op;
mult_level;
emit operation(add_op);
END;
END;
PROCEDURE expression; { comparisons, IN }
VAR cmp_op:operation;
BEGIN
add_level;
IF op IN cmp_ops THEN BEGIN
save the result;
cmp_op:=op;
add_level;
emit operation(cmp_op);
END;
END;
Example 1: Translation of (a+b)=c -> RPN = a , b + c =
curr. char, stack (active procedure), code produced
---
(:expression add_level mult_level not neg atom
a:... expression add_level mult_level not neg atom
+:... expression add_level -> MOV AX,a
b:... expression add_level mult_level not neg atom
):... expression add_level -> ADD AX,b
):expression add_level mult_level not neg atom
=:expression
c:expression add_level mult_level not neg atom
:expression -> CMP AX,c
Please note:
The parentheses trigger a recursive call of the expression procedure.
The code production always lags behind the analysis. This improves the code produced (e.g. ADD AX,b).
Example 2: Translation of a+b*c -> RPN = a , b , c * +
curr. char, stack (active procedure), code produced
---
a:expression add_level mult_level not neg atom
+:expression add_level -> MOV AX,a
b:expression add_level mult_level not neg atom
*:expression add_level mult_level -> PUSH AX
-> MOV AX,b
c:expression add_level mult_level not neg atom
:expression add_level mult_level -> IMUL c
:expression add_level -> POP CX
-> ADD AX,CX
Please note:
The content of a must be stacked, as the AX register is needed for the multiplication. This is recognized by setting the flag push_ax. If subsequent code uses the AX register (destroying its content), it has to emit PUSH AX. Finally, if this has happened, the register must be restored by POP CX.
The code produced is rather simple-minded. By transforming the expression to b*c+a better code could be produced:
MOV AX,b
IMUL c
ADD AX,a
During evaluation, type checking and type conversion (Integer -> Real...) is also done.
The 8088 instruction set is often not used well. a:=a+1 yields this code (INC a would be better):
MOV AX,a
ADD AX,#1
MOV a,AX
Expressions usually account for the bulk of the code produced, so their translation is very important.
Optimization
The goal of code optimization is reducing the size and/or execution time of the code produced. It is usually impossible to find an optimal solution, as a space-time tradeoff has to be made. TURBO Pascal doesn't have an optimizer. However, to improve the efficiency of your programs by manual optimizations or by add-on optimizers, it is good to know how common optimizations work.
Optimizations can be local or global: They can cover a single statement or an entire program. Global optimization is much more difficult and can cause problems. GOTO's and function or procedure calls can keep the optimizer from working efficiently.
Side effects can cause errors that are hard to find. Try it - you'll get what you deserve... An example:
FUNCTION funny:INTEGER;
BEGIN
side_effect:=side_effect+1;
funny:=5;
END;
...
a:=side_effect+funny+side_effect;
The evaluation sequence and thus the result depends on the compiler used.
Variables don't necessarily stay constant between assignments. Consider this:
wait_int:=FALSE;
REPEAT UNTIL wait_int;
This might wait for an interrupt procedure to set a flag. An optimizing compiler would convert this to an endless loop... Modern C compilers use the volatile keyword to avoid this.
Use of Register Variables
Many load and store operations can be eliminated by using register variables. On the 8088 this is rather difficult, as there are few registers, often with special uses.
Common Subexpressions
c:=(a+b)*d;
e:=g-(a+b);
The subexpression (a+b) can be used twice. Expressions of the form a[i]:=a[i]+ 1 also are a good target for optimizations.
Array Indexing
References with constant indices (a[5]) or indices with a constant offset (a[i+1]) can be optimized. Array indexing in loops can often be improved considerably, too.
Constant Folding
Programs can be more readable if constants expressions can be written in a symbolic form. The compiler can evaluate these expressions at compilation time. Later versions of the compiler do this.
Strength Reduction
This means replacing operations by "cheaper" equivalents, e.g. x*0.2 instead of x/5 (multiplications are faster than divisions).
Loop Optimization
FOR i:=1 TO 100 DO dest[i]:=a+b;
The subexpression a+b can be evaluated outside the loop, as a and b don't change in the loop.
Dead Code Elimination
CONST debug=FALSE;
IF debug THEN writeln('Debug');
The IF statement can be left out - the condition is never met. The same thing can be done with procedures which are never used. There are optimizers that eliminate all unused procedures from the run-time library of programs translated by TURBO Pascal. Later versions of the compiler do this.
Evaluation of Boolean Expressions
IF (a=5) AND (b=6) THEN ... can be changed into
IF (a=5) THEN
IF (b=6) THEN ...
The same thing can be done with OR and NOT. Never expect boolean expressions to be executed completely ! Later versions of the compiler do this.
Variable Alignment
Variables in the data segment and on the stack should be aligned to even offsets to improve performance on 16 bit PC's.
Code Generation
The code generator has the difficult task of translating the elements recognized by the parser into executable code. If it gets difficult to tell whether the code has been generated by a human programmer or by a compiler then it is indeed a good one... Don't expect too much of this from TURBO.
In the following sections the code produced by TURBO will be explained.
Program
run-time library, if not chain file
CALL initmem ;set segments
W mainflag ;see source code
W turbocs,turbods
W cssize,dssize
w heapsize,maxhpsz
w maxfile,stdinsz,stdoutsz
MOV BP,SP ;stack frame
CALL uncrunch ;expand overlays
W link,*+2
definition part
program part = main program
XOR AX,AX ;Halt
CALL progend
Definition Part
The definition part may contain code, therefore it must be skipped over by:
JMP l1
l1:Structured Constants
Structured constants are stored in the same format as normal variables.
Overlays
The space needed for overlays is not stored in the COM file. It is freed by the uncrunch procedure. This means moving up the subsequent code. This is executed at the beginning of program execution and after loading an overlay procedure.
CALL rdover ;read overlay file
W $ffff ;overlay procedure now in memory = invalid
B 'over.001' ;name of overlay file
In the section read from the overlay file:
CALL uncrunch ;expand overlay
W link,*+2 ;link for uncrunching
overlay procedure / function
W link,* ;for uncrunching
Forward Definitions
For forward definitions a jump to the final definition is produced. The displacement is inserted when the real definition is made.
JMP defined_proc
External Procedures
The code read from an external file is not changed.
Procedure Definitions
Local variables of procedures and functions are always stored on the stack. This means that only active procedures take up space on the stack. This also enables recursive calls. The transfer of parameters and the allocation of stack space can be quite complicated, thus slowing down procedure calls.
For every procedure a data structure called stack frame or activation record is built on the stack. The pointer to the stack frame is always stored in the BP register (the 8088 can't use the stack pointer SP as index register). The structure of the stack frame is as follows:
BP+.:function result (space allocated by caller)
BP+.:first parameter
BP+4:last parameter
BP+2:return address
BP+0:pointer to caller's stack frame
BP-2:new stack frame
BP-4:local variables
BP-.:stack top
The code for a standard procedure entry looks like this:
PUSH BP ;save old pointer
MOV BP,SP ;set new pointer
PUSH BP ;save new pointer (for display)
definition part ;constants, local procedures
SUB SP,#size ;allocate space for local variables
;1..2 bytes: DEC SP
program part ;the actual procedure
MOV SP,BP ;forget local variables
POP BP ;restore old pointer
RET prmsize ;return, remove parameters from stack
;no parameters: RET
How function results are passed depends on their type. Scalars (integer...) are returned in AX, for boolean results the flags are set with OR AX,AX. Reals are on the stack anyway. Strings must be moved such that they occupy only their effective length:
MOV DX,#pos_on_stack
MOV CL,#max_len
MOV SP,BP
POP BP
JMP retstr ;the normal end is omitted
Unfortunately, things aren't that simple. Consider nested procedure definitions:
PROCEDURE level1;
VAR
i:INTEGER;
PROCEDURE level2;
BEGIN
i:=0;
level2;
END;
BEGIN
level2;
END;
The inner procedure level2 uses a local variable of level1, but also calls itself recursively. The stack offset of i depends on the calling order. TURBO Pascal uses a so called display to resolve this. The display contains pointers to the stack frames of calling procedures. Each procedure also adds its own pointer to the display. The display is an extension of the stack frame.
BP+0:old pointer
BP-2:display outermost procedure
BP-.:display
BP-.:display current procedure
BP-.:local variables
BP-.:stack top
This is maintained by the following code:
PUSH BP ;save old pointer
MOV AX,SP ;set new pointer - keep BP
PUSH [BP-nest*2] ;build display
.. ;once for each nesting level
MOV BP,AX ;set new pointer
PUSH BP ;add own pointer to display
definition part
Newer CPU's (186, 286...) have special commands for these operations (ENTER, LEAVE). Please note that referencing variables via the display is slower than normal references. If speed is important don't nest procedure definitions.
Program Structures
Program Part
statements
l1: JMP l2 ;jump to the end
POP AX ;GOTO, EXIT: clean up the stack
JMP l1
l2:
GOTO's and EXIT's aren't really that simple. Sometimes stack variables (FOR, WITH) must be removed, which is done at the end of the procedure.
Statement
If the user interrupt directive is set, an INT 3 is emitted for each statement. This calls a routine which checks for user interrupts. This feature can be "misused" to trace a program or to profile its execution time. If this isn't used anywhere in the program, you can also insert breakpoints as INLINE statements for debugging with DEBUG.
IF
This has been covered above.
WHILE
l1: condition ;evaluate condition
J.. l2 ;:condition met
JMP l3
l2: statement
JMP l1 ;try again
l3: ;end of loop
REPEAT
l1: statement
condition ;evaluate condition
J.. l2 ;condition met: end
JMP l1 ;not met: repeat
l2:
REPEAT loops are faster than WHILE loops.
FOR
The counter (stored on stack) and the control variable are independent: assignments to the control variable don't change the number of loop executions.
starting value -> AX
PUSH AX
ending value -> AX
POP CX
XCHG CX,AX
SUB CX,AX ;calculate difference
JGE l1 ;(DOWNTO: JNG)
JMP l3 ;don't execute
l1: INC CX ;(DEC CX)
l2: PUSH CX ;save counter
POP CX ;restore counter
DEC CX ;(INC CX)
JZ l3 ;0: done
INC loop_var ;(DEC) update control variable
JMP l2 ;loop
l3: ;end
CASE
CASE .. OF
2,5 : .. ;
7..9: .. ;
ELSE .. ;
END;
;evaluate selection
CMP AX,#2 ;compare
JZ ok1 ;:yes
CMP AX,#5
JZ ok1 ;:yes
JMP test2 ;try next case
ok1: ;ok - execute
JMP endcase ;jump to end
test2: CMP AX,#7 ;check subrange
JL test2no ;:no
CMP AX,#9
JLE ok2 ;:yes
test2no: JMP else ;no: execute ELSE part
ok2: ;ok - execute
JMP endcase
else: ;ELSE part
endcase:
Complicated CASE statements can exceed the range of short jumps. In this case so called "hips" are emitted:
JMP hip2 ;skip hip
hip: JMP ok ;jump to statement part
hip2: ;normal continuation
Some compilers also use this technique for IF and other statements.
GOTO
A jump is emitted. If the GOTO leaves a WITH or a FOR block, the stack must be cleaned up. This is recognized and fixed at the end of the program part.
WITH
The compiler has an internal WITH stack. The pointers for indexed WITH's are stored on the stack:
set pointer to variable
PUSH ES ;store pointer on stack
PUSH DI
statement
ADD SP,#4 ;remove pointer from stack
If the address is known at compilation time this is not necessary.
Procedure Calls
If the directive K+ is set, a stack check is executed:
MOV CX,#space_needed
CALL xchkstk
Then parameters are evaluated and passed:
Normal parameter: