Difference between revisions of "Code Generation"

From Wiki**3

(New page: == Topics == * Interpretation: syntax-directed and based on abstract syntax tree. * Code generation: syntax-directed and based on abstract syntax tree. == The Postfix Machine == SL0 - si...)
 
(→‎Accessing global (permanent) variables)
 
(65 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{NAVCompiladores}}
 +
{{TOCright}}
 
== Topics ==
 
== Topics ==
 
* Interpretation: syntax-directed and based on abstract syntax tree.
 
* Interpretation: syntax-directed and based on abstract syntax tree.
 
* Code generation: syntax-directed and based on abstract syntax tree.
 
* Code generation: syntax-directed and based on abstract syntax tree.
 +
 +
The approach described here is based on generation from the intermediate representation in the form of an abstract syntax tree formed by the nodes created during the parsing process.
 +
 +
The target machine is the Postfix engine described below.
  
 
== The Postfix Machine ==
 
== The Postfix Machine ==
  
−
SL0 - single stack, large stack, 0 (data) register machine.
+
The Postfix machine is a stack machine possessing a single large stack and 0-operand instructions (SL0).
  
−
Three special purpose registers: IP (instruction pointer), for jumps and function calls; FP (frame pointer), the basis of the frame pointer for each function; SP (stack pointer), keeps track of the top of the stack.
+
Three special purpose registers: IP (instruction pointer, a.k.a, program counter), for jumps and function calls; FP (frame pointer, a.k.a. base pointer), the basis of the frame pointer for each function; SP (stack pointer), keeps track of the top of the stack.
  
 
The stack grows in the direction of lower addresses.
 
The stack grows in the direction of lower addresses.
  
−
Almost all operations use the stack as input and output (exceptions are PUSH and POP, for returning values from functions in accordance with CDecl), and instructions that use either immediate arguments or arguments in global memory (i.e., with explicit named addressing).
+
Almost all operations use the stack as input and output (exceptions are instructions for returning values from functions in accordance with CDecl), and instructions that use either immediate arguments or arguments in global memory (i.e., with explicit named addressing).
 +
 
 +
The [[Postfix Reference Guide|Postfix reference guide]] contains further details about the Postfix machine and its operations.
  
 
== Basic Structures (code) ==
 
== Basic Structures (code) ==
  
−
=== While Cycles ===
+
The mnemonics are those of the Postfix language. Comments indicate missing parts.
 +
 
 +
=== Cycles ===
 +
 
 +
Basic structure of a '''while''' cycle:
 +
 
 +
<source lang="asm">
 +
LABEL condition
 +
;; evaluate condition expression
 +
JZ endcycle
 +
;; evaluate block
 +
JMP condition
 +
LABEL endcycle
 +
</source>
 +
 
 +
Basic structure of a '''do-while''' cycle:
 +
 
 +
<source lang="asm">
 +
LABEL startcycle
 +
;; evaluate block
 +
LABEL condition
 +
;; evaluate condition expression
 +
JNZ startcycle
 +
LABEL endcycle
 +
</source>
 +
 
 +
Basic structure of a C-style '''for''' cycle:
 +
 
 +
<source lang="asm">
 +
;; evaluate initializer
 +
LABEL condition
 +
;; evaluate condition expression
 +
JZ endfor
 +
;; evaluate block
 +
LABEL increment
 +
;; evaluate increment expression
 +
JMP condition
 +
LABEL endfor
 +
</source>
  
 
=== "Break" and "Continue" Instructions ===
 
=== "Break" and "Continue" Instructions ===
 +
 +
The C-style '''break''' and '''continue''' instructions must jump, respectively, to the end of the cycle or to its condition (for deciding on whether to execute the next iteration). In the case of '''for''' cycles, the jump to the condition is not direct, but rather via a jump to the increment label.
 +
 +
If there are multiple nested cycles, the code generator must keep track of the innermost one, so that it can generate the appropriate jumps. This can be achieved through the use of address stacks (one for '''break''' labels and another for '''continue''' labels).
  
 
=== If-Then and If-Then-Else Instructions ===
 
=== If-Then and If-Then-Else Instructions ===
 +
 +
Basic structure of an "if-then" instruction:
 +
 +
<source lang="asm">
 +
;; evaluate condition expression
 +
JZ endif
 +
;; evaluate then block
 +
LABEL endif
 +
</source>
 +
 +
Basic structure of an "if-then-else" instruction:
 +
 +
<source lang="asm">
 +
;; evaluate condition expression
 +
JZ else
 +
;; evaluate then block
 +
JMP endif
 +
LABEL else
 +
;; evaluate else block
 +
LABEL endif
 +
</source>
 +
 +
=== Functions ===
 +
 +
The function structure presented here assumes a "void" return. If a return were desired, the use of STFVAL32 or STFVAL64 would be required before the LEAVE instruction.
 +
 +
"sizeoflocalvars" is the number of bytes needed to store all of the function's local variables. If this value is 0 (zero), START may be used instead of ENTER.
 +
 +
If the function is not global (e.g. C-style "static" function), then GLOBAL should not be used.
 +
<source lang="asm">
 +
GLOBAL functionname,FUNC
 +
LABEL functionname
 +
ENTER sizeoflocalvars
 +
;; evaluate function body
 +
LEAVE
 +
RET
 +
</source>
  
 
== Basic Structures (data) ==
 
== Basic Structures (data) ==
  
−
=== Functions ===
+
=== Defining global (permanent) variables ===
 +
 
 +
We include in this category C-like "static" function variables (the only difference is that they are not defined with their explicit names, but rather with a name that reflects their being visible only inside their functions). Note, however, that "static" variables, even though they exist in globally accessible memory spaces, do not have public names and, hence, are not declared GLOBAL.
 +
 
 +
Addressing of these variables is by name, thus, they have memory labels:
 +
 
 +
<source lang="asm">
 +
;; int a
 +
BSS            ; select segment for uninitialized variables
 +
ALIGN          ; align memory
 +
GLOBAL a, OBJ  ; declare a global symbol (linker)
 +
LABEL  a        ; define the label
 +
SALLOC 4          ; allocate space (sizeof(int) == 4)
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; int a = 3
 +
DATA            ; select segment for initialized variables
 +
ALIGN          ; align memory
 +
GLOBAL a, OBJ  ; declare a global symbol (linker)
 +
LABEL  a        ; define the label
 +
SINT 3        ; allocate space by defining initial value
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; const int a = 3
 +
RODATA          ; select segment for constant objects
 +
ALIGN          ; align memory
 +
GLOBAL a, OBJ  ; declare a global symbol (linker)
 +
LABEL  a        ; define the label
 +
SINT 3        ; allocate space by defining initial value
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; char *s = "abcdef"
 +
RODATA          ; select segment for constant objects (string literal)
 +
ALIGN          ; align memory
 +
LABEL  _L123    ; define the label
 +
SSTRING "abcdef"    ; allocate space by defining initial value (string literal)
 +
DATA            ; select segment for initialized variables
 +
ALIGN          ; align memory
 +
GLOBAL s, OBJ  ; declare a global symbol (linker)
 +
LABEL  s        ; define the label
 +
SADDR _L123        ; allocate space by defining initial value (address of literal)
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; L22 example
 +
;; var f = (int i) -> int:
 +
;;    return i
 +
TEXT _F123          ; select segment for this (anonymous) function
 +
ALIGN          ; align memory
 +
LABEL  _F123    ; define the label
 +
ENTER 0
 +
LOCAL +8 ; &i
 +
LDINT ; i
 +
STFVAL32
 +
LEAVE
 +
RET
 +
DATA            ; select segment for initialized variables
 +
ALIGN          ; align memory
 +
GLOBAL f, OBJ  ; declare a global symbol (linker)
 +
LABEL  f        ; define the label
 +
SADDR _F123        ; allocate space by defining initial value (address of function)
 +
</source>
  
−
=== Global (permanent) variables ===
+
=== Accessing global (permanent) variables ===
  
 
We include in this category C-like "static" function variables (the only difference is that they are not accessed with their explicit names, but rather with a automatic symbol table-based name).
 
We include in this category C-like "static" function variables (the only difference is that they are not accessed with their explicit names, but rather with a automatic symbol table-based name).
  
−
=== Local variables ===
+
Addressing of these variables is by name, as shown in the following examples.
 +
 
 +
<source lang="asm">
 +
;; a = 1
 +
INT 1    ; put 1 on the stack
 +
DUP32      ; duplicate value
 +
ADDR a  ; put address of "a" on the stack
 +
STINT    ; write the value on the given address
 +
</source>
 +
If the resulting value is not needed, throw it away:
 +
 
 +
<source lang="asm">
 +
;; a = 1;  // expression as instruction
 +
INT 1    ; put 1 on the stack
 +
DUP32      ; duplicate value
 +
ADDR a  ; put address of "a" on the stack
 +
STINT    ; write the value on the given address
 +
TRASH 4
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; a = b (both global)
 +
ADDR b  ; put address of "b" on the stack
 +
LDINT    ; read the value at the given address
 +
DUP32      ; duplicate value (= is an expression)
 +
ADDR a  ; put address of "a" on the stack
 +
STINT    ; write the value on the given address
 +
</source>
 +
 
 +
If ADDR is immediately followed by LDINT, then the two instructions may be replaced by a single one with the same effect: ADDRV. Similarly, ADDR+STINT = ADDRA. Note that this, in most cases, will correspond to an optimization and its use by the code generator will be impossible or very limited.
 +
 
 +
<source lang="asm">
 +
;; a = 1
 +
INT 1    ; put 1 on the stack
 +
DUP32      ; duplicate value (= is an expression)
 +
ADDRA a ; write the value in the address corresponding to "a"
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; a = b (both global)
 +
ADDRV b ; read value in the address of "b" and put it on the stack
 +
DUP32      ; duplicate value (= is an expression)
 +
ADDRA a ; write the value in the address corresponding to "a"
 +
</source>
 +
 
 +
=== Accessing local variables ===
 +
 
 +
In the following examples, we assume that both '''a''' and '''b''' are local variables (thus having negative offsets relative to the framepointer). If they were function arguments, the offsets would be positive.
 +
 
 +
<source lang="asm">
 +
;; a = 1
 +
INT 1    ; put 1 on the stack
 +
DUP32      ; duplicate value (= is an expression)
 +
LOCAL -4 ; put address of "a" (assuming offset -4) on the stack
 +
STINT    ; write the value on the given address
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; a = b (both local)
 +
LOCAL -8 ; put address of "b" (assuming offset -8) on the stack
 +
LDINT    ; read the value at the given address
 +
DUP32      ; duplicate value (= is an expression)
 +
LOCAL -4 ; put address of "a" (assuming offset -4) on the stack
 +
STINT    ; write the value on the given address
 +
</source>
 +
 
 +
If LOCAL is immediately followed by LDINT, then the two instructions may be replaced by a single one with the same effect: LOCV. Similarly, LOCAL+STINT = LOCA. Note that this, in most cases, will correspond to an optimization and its use by the code generator will be impossible or very limited.
 +
 
 +
<source lang="asm">
 +
;; a = 1
 +
INT 1  ; put 1 on the stack
 +
DUP32      ; duplicate value (= is an expression)
 +
LOCA -4 ; write the value on the address of "a" (assuming offset -4)
 +
</source>
 +
 
 +
<source lang="asm">
 +
;; a = b (both local)
 +
LOCV -8 ; read value in the address of "b" (assuming offset -8) and put it on the stack
 +
DUP32      ; duplicate value (= is an expression)
 +
LOCA -4 ; write the value on the address of "a" (assuming offset -4)
 +
</source>
 +
 
 +
== Examples ==
 +
 
 +
* [[Code Generation/Example 1|Example 1]] - translating a C function to Postfix
 +
* [[Code Generation/Example 2|Example 2]] - simple program printing a global string
 +
* [[Code Generation/Example 3|Example 3]] - C function with pointer arithmetic to Postfix
 +
* [[Code Generation/Example 4|Example 4]] - C while cycle
 +
 
 +
A simple pure-Postfix example to illustrate duplication of stack values for double-precision floating point numbers.<br>
 +
 
 +
* [[Code Generation/Duplication of Floating Point Numbers on the Stack|Duplication of Floating Point Numbers on the Stack]]
 +
 
 +
== Exercises ==
 +
 
 +
* [[Code Generation/Exercise 5|Exercise 5]] - "gcd"
 +
* [[Code Generation/Exercise 6|Exercise 6]] - "powmod"
 +
* [[Code Generation/Exercise 7|Exercise 7]] - "traverse"
 +
* [[Code Generation/Exercise 8|Exercise 8]] - set of small exercises and questions
 +
* [[Code Generation/Exercise 9|Exercise 9]] - "mkvec" and "compute", Test 2, 2012/06/06
 +
* [[Code Generation/Exercise 10|Exercise 10]] - "forall" (version 1), Test 2, 2015/06/29
 +
* [[Code Generation/Exercise 11|Exercise 11]] - "forall" (version 2), Test 2, 2015/06/29
 +
* [[Code Generation/Exercise 12|Exercise 12]] - finding elements in vector, Test 2, 2016/06/17
 +
* [[Code Generation/Exercise 13|Exercise 13]] - '''repeat'''
 +
* [[Code Generation/Exercise 14|Exercise 14]] - '''mop'''
 +
* [[Code Generation/Exercise 15|Exercise 15]] - '''gcd''' (take 2)
 +
* [[Code Generation/Exercise 16|Exercise 16]] - '''heapSort''', etc.
 +
* [[Code Generation/Exercise 17|Exercise 17]] - '''find'''
 +
* [[Code Generation/Exercise 18|Exercise 18]] - fragmentos com variações
  
−
[[category:Compilers]]
+
[[category:Compiladores]]
−
[[actegory:Teaching]]
+
[[category:Ensino]]

Latest revision as of 17:16, 1 June 2023

Compiladores
Introdução ao Desenvolvimento de Compiladores
Aspectos Teóricos de Análise Lexical
A Ferramenta Flex
Introdução à Sintaxe
Análise Sintáctica Descendente
Gramáticas Atributivas
A Ferramenta YACC
Análise Sintáctica Ascendente
Análise Semântica
Geração de Código
Tópicos de Optimização

Topics

  • Interpretation: syntax-directed and based on abstract syntax tree.
  • Code generation: syntax-directed and based on abstract syntax tree.

The approach described here is based on generation from the intermediate representation in the form of an abstract syntax tree formed by the nodes created during the parsing process.

The target machine is the Postfix engine described below.

The Postfix Machine

The Postfix machine is a stack machine possessing a single large stack and 0-operand instructions (SL0).

Three special purpose registers: IP (instruction pointer, a.k.a, program counter), for jumps and function calls; FP (frame pointer, a.k.a. base pointer), the basis of the frame pointer for each function; SP (stack pointer), keeps track of the top of the stack.

The stack grows in the direction of lower addresses.

Almost all operations use the stack as input and output (exceptions are instructions for returning values from functions in accordance with CDecl), and instructions that use either immediate arguments or arguments in global memory (i.e., with explicit named addressing).

The Postfix reference guide contains further details about the Postfix machine and its operations.

Basic Structures (code)

The mnemonics are those of the Postfix language. Comments indicate missing parts.

Cycles

Basic structure of a while cycle: 

LABEL condition
;; evaluate condition expression
JZ endcycle
;; evaluate block
JMP condition
LABEL endcycle

Basic structure of a do-while cycle: 

LABEL startcycle
;; evaluate block
LABEL condition
;; evaluate condition expression
JNZ startcycle
LABEL endcycle

Basic structure of a C-style for cycle: 

;; evaluate initializer
LABEL condition
;; evaluate condition expression
JZ endfor
;; evaluate block
LABEL increment
;; evaluate increment expression
JMP condition
LABEL endfor

"Break" and "Continue" Instructions

The C-style break and continue instructions must jump, respectively, to the end of the cycle or to its condition (for deciding on whether to execute the next iteration). In the case of for cycles, the jump to the condition is not direct, but rather via a jump to the increment label.

If there are multiple nested cycles, the code generator must keep track of the innermost one, so that it can generate the appropriate jumps. This can be achieved through the use of address stacks (one for break labels and another for continue labels).

If-Then and If-Then-Else Instructions

Basic structure of an "if-then" instruction: 

;; evaluate condition expression
JZ endif
;; evaluate then block
LABEL endif

Basic structure of an "if-then-else" instruction: 

;; evaluate condition expression
JZ else
;; evaluate then block
JMP endif
LABEL else
;; evaluate else block
LABEL endif

Functions

The function structure presented here assumes a "void" return. If a return were desired, the use of STFVAL32 or STFVAL64 would be required before the LEAVE instruction.

"sizeoflocalvars" is the number of bytes needed to store all of the function's local variables. If this value is 0 (zero), START may be used instead of ENTER.

If the function is not global (e.g. C-style "static" function), then GLOBAL should not be used. 

GLOBAL functionname,FUNC
LABEL functionname
ENTER sizeoflocalvars
;; evaluate function body
LEAVE
RET

Basic Structures (data)

Defining global (permanent) variables

We include in this category C-like "static" function variables (the only difference is that they are not defined with their explicit names, but rather with a name that reflects their being visible only inside their functions). Note, however, that "static" variables, even though they exist in globally accessible memory spaces, do not have public names and, hence, are not declared GLOBAL.

Addressing of these variables is by name, thus, they have memory labels: 

;; int a
BSS             ; select segment for uninitialized variables
ALIGN           ; align memory
GLOBAL a, OBJ   ; declare a global symbol (linker)
LABEL  a        ; define the label
SALLOC 4          ; allocate space (sizeof(int) == 4)

;; int a = 3
DATA            ; select segment for initialized variables
ALIGN           ; align memory
GLOBAL a, OBJ   ; declare a global symbol (linker)
LABEL  a        ; define the label
SINT 3         ; allocate space by defining initial value

;; const int a = 3
RODATA          ; select segment for constant objects
ALIGN           ; align memory
GLOBAL a, OBJ   ; declare a global symbol (linker)
LABEL  a        ; define the label
SINT 3         ; allocate space by defining initial value

;; char *s = "abcdef"
RODATA          ; select segment for constant objects (string literal)
ALIGN           ; align memory
LABEL  _L123    ; define the label
SSTRING "abcdef"    ; allocate space by defining initial value (string literal)
DATA            ; select segment for initialized variables
ALIGN           ; align memory
GLOBAL s, OBJ   ; declare a global symbol (linker)
LABEL  s        ; define the label
SADDR _L123        ; allocate space by defining initial value (address of literal)

;; L22 example
;; var f = (int i) -> int:
;;    return i
TEXT _F123          ; select segment for this (anonymous) function
ALIGN           ; align memory
LABEL  _F123    ; define the label
ENTER 0
LOCAL +8 ; &i
LDINT ; i
STFVAL32
LEAVE 
RET
DATA            ; select segment for initialized variables
ALIGN           ; align memory
GLOBAL f, OBJ   ; declare a global symbol (linker)
LABEL  f        ; define the label
SADDR _F123        ; allocate space by defining initial value (address of function)

Accessing global (permanent) variables

We include in this category C-like "static" function variables (the only difference is that they are not accessed with their explicit names, but rather with a automatic symbol table-based name).

Addressing of these variables is by name, as shown in the following examples. 

;; a = 1
INT 1    ; put 1 on the stack
DUP32      ; duplicate value
ADDR a   ; put address of "a" on the stack
STINT    ; write the value on the given address

If the resulting value is not needed, throw it away: 

;; a = 1;  // expression as instruction
INT 1    ; put 1 on the stack
DUP32      ; duplicate value
ADDR a   ; put address of "a" on the stack
STINT    ; write the value on the given address
TRASH 4

;; a = b (both global)
ADDR b   ; put address of "b" on the stack
LDINT     ; read the value at the given address
DUP32      ; duplicate value (= is an expression)
ADDR a   ; put address of "a" on the stack
STINT    ; write the value on the given address

If ADDR is immediately followed by LDINT, then the two instructions may be replaced by a single one with the same effect: ADDRV. Similarly, ADDR+STINT = ADDRA. Note that this, in most cases, will correspond to an optimization and its use by the code generator will be impossible or very limited. 

;; a = 1
INT 1     ; put 1 on the stack
DUP32       ; duplicate value (= is an expression)
ADDRA a ; write the value in the address corresponding to "a"

;; a = b (both global)
ADDRV b ; read value in the address of "b" and put it on the stack
DUP32       ; duplicate value (= is an expression)
ADDRA a ; write the value in the address corresponding to "a"

Accessing local variables

In the following examples, we assume that both a and b are local variables (thus having negative offsets relative to the framepointer). If they were function arguments, the offsets would be positive. 

;; a = 1
INT 1    ; put 1 on the stack
DUP32       ; duplicate value (= is an expression)
LOCAL -4 ; put address of "a" (assuming offset -4) on the stack
STINT    ; write the value on the given address

;; a = b (both local)
LOCAL -8 ; put address of "b" (assuming offset -8) on the stack
LDINT     ; read the value at the given address
DUP32       ; duplicate value (= is an expression)
LOCAL -4 ; put address of "a" (assuming offset -4) on the stack
STINT    ; write the value on the given address

If LOCAL is immediately followed by LDINT, then the two instructions may be replaced by a single one with the same effect: LOCV. Similarly, LOCAL+STINT = LOCA. Note that this, in most cases, will correspond to an optimization and its use by the code generator will be impossible or very limited. 

;; a = 1
INT 1   ; put 1 on the stack
DUP32       ; duplicate value (= is an expression)
LOCA -4 ; write the value on the address of "a" (assuming offset -4)

;; a = b (both local)
LOCV -8 ; read value in the address of "b" (assuming offset -8) and put it on the stack
DUP32       ; duplicate value (= is an expression)
LOCA -4 ; write the value on the address of "a" (assuming offset -4)

Examples

  • Example 1 - translating a C function to Postfix
  • Example 2 - simple program printing a global string
  • Example 3 - C function with pointer arithmetic to Postfix
  • Example 4 - C while cycle

A simple pure-Postfix example to illustrate duplication of stack values for double-precision floating point numbers.

Exercises

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Code_Generation&oldid=15761"