Code Generation (Compiler)

In computing, code generation is part of the process chain of a compiler and converts intermediate representation of source code into a form (e.g., machine code) that can be readily executed by the target system.

11/10 Warm-up Problem: Define using our shorthand, code(term1 → term2 STAR factor)

- code(term2)
+ push($3)
+ code(factor)
+ pop($5)
+ mult $5, $3
+ mflo $3

lvalue

No better solutions for lvalues.

Generating Code for Print Statement

WLP4 rule: statement → PRINTLN LPAREN expr RPAREN SEMI

Code reuse A compiler mixes the code it outputs with code from runtime environment.

MERL for linking purposes. gcc is only a compiler drivers.

Using print

.import print in prologue to use it. Think of it as a label. Just like any other procedure, call print using the jalr instruction which overwrites register 31.

code(println(expr);) = 
push($1)
+ code(expr)
+ add $1, $3, $0
+ push($31)
+ lis $5 + .word print
+ jalr $5 + pop($31)
+ pop($1)

Control-Flow Statements

Convention: Store 1 inside $11 (For true and false purposes) Now prologue is even longer…

; Prologue
.import print
lis $4
.word 4
lis $10
.word print
list $11
.word 1
sub $29, $30, $4
; end Prologue and begin body
; space for variables
; translated WLP4 code
; end body and begin epilogue
add $30, $29, $4
jr $31

If Statements

Rule: statement → IF (test) (stmts1) ELSE (stmts2) Use labels

11/15 Lecture 18 Warm up Problem Informally how would we generate code for a switch statement?

code(switch (expr){…})

int wain(int *a, int b){
int *c = NULL;
int ret = 0;
c = new int[b];
 
if(c < a){
ret = a - c;
}else{
ret = c - a;
}
return ret;
}

Code generation:

;Prologue
 
; code(c = new int[b])
; code(new int[b])
; code(b)
lw $3, -4($29)
add $1, $3, $0
lis $5
.word new
jalr $5
bne $3, $0, 2
add $3, $11, $0
sw $3, -8($29)
; code(if(T){S1} else {S2})
; code(c - a)
; code(c)
lw $3, -8($29)
; push($3)
sw $3, -4($30)
sub $30, $30, $4 //decrement stack pointer
; code(g)
lw $3, 0($29)
; pop($5)
add $30, $30, $4
lw $5, -4($30)
sltu $3, $5, $3
; if(T) {S1} else {S2}
; code(T)
beq $3, $0, else1
	; code(ret = a -c)
		; code(a - c)
			;code(a)
				lw $3, 0($29)
			;push($3)
				sw $3, -4($30)
				sub $30, $40, $4
			; code(c)
				lw $3, -8($29)
			; pop($5)
				add $30, $30, $4
				lw $5, -4($30)
			sub $3, $5, $3
			div $3, $4
			mflo $3
		sw $3, -12($29)
		beq $0, $0, endIf1
else1:
	; code(ret = c - a)
	lw $3, -8($29)
	sw $3, -4($30)
	sub $30, $30, $4
	lw $3, $3, 0($29)
	add $30, $30, $4
	lw $5, -4($30)
	sub $3, $5, $3
	div $3, $4
	mflo $3
	sw $3, -12($29) 
endIf1:
 
;code(ret)
lw $3, -12($29) 
 
;epilogue

Could optimize when we sw what’s in $3 in t o - 12 ($ 29) and lw from -12( $29) t o$ 3. Print which production rule we are in when debugging.

Procedures

Warm up Problem

11/17/22 Given that NULL is 1 in WLP4, how can we using only WLP4 code cheat and get a pointer to 0 anyways?

int *a = NULL;
int *b = NULL;
int c = 0;
b = 8c;
b = b-(b-a)-1;
*b = 0 + ...;

saving registers and restoring

beq $0, $0, wain
 
Fadd:
;int add(int a, int b){
sub $29, $30, $4 //getting $29
; int c = 0;
; code (int c = 0)
	lis $3
	.word 0
	sw $3, -4($30)
	sub $30, $30, $4
;push registers
; c = a * b;
;code(c = a * b)
	; code (a)
		lw $3, 8($29)
	;push($3)
		sw $3, -4($30)
		sub $30, $30, $4
	;code(b)
		lw $3, 4($29)
	;pop($5)
		add $30, $30, $4
		lw $5, -4($30)
	add $3, $5, $3
sw $3, 0($29)
 
;return c;
;code(c)
	lw $3, 0($29)
;)
;retor registers 
add $30, $29, $4
jr $31
}
 
wain:
;int wain(int a, intb){
sub $29, $30, $4
;prologue: init $4, $10, $11; call init; savge arguments
;	return add(a, b);
; code(add(a,b))
	; push ($29), push($31)
	sw $29, -4($30)
	sub $30, $30, $4
	sw $31, -4($30)
	sub $30, $30, $4
	; code (expr1 -> a)
	lw $3, 0($29)
	; push ($3)
	sw $3, ;04($30)
	sub $30, $30, $4
	;code(expr2 -> b)
	lw $3, -4($29)
	; push($3)
	sw $3, -4($30)
	sub $30, $30, $4
	;...
	lis $5
	.word Fadd
	jalr $5
	; pop arguments
	add $30, $30, $4
	add $30, $30, $4
	;pop($31)
	add $30, $30, $4
	lw $31, -4($30)
	;pop($29)
	add $30, $30, $4
	lw $29, -4($30)
;}
;epilogue unchanged...
jr $31

🪴 Avril Chen

Explorer