1
Download transparencias
Document related concepts
no text concepts found
Transcript
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Compiladores: Generación de
código
Francisco J Ballesteros
LSUB, URJC
http://127.0.0.1:3999/s11.gen.slide#1
Page 1 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
Una vez tenemos un AST decorado con todo lo necesario
podemos generar código
O generamos un código intermedio
y luego lo volvemos a traducir para una máquina
O generamos código objeto (o ensamblador) directamente
O traducimos a otro lenguaje
que podemos compilar on otro compilador
o que es interpretable por otro programa
http://127.0.0.1:3999/s11.gen.slide#1
Page 2 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Objetivo
Necesitamos saber cómo es la máquina target
Generar código para ella
es en realidad imprimir texto
con instrucciones para esa máquina
pensando en un entorno de ejecución en ella (run-time)
http://127.0.0.1:3999/s11.gen.slide#1
Page 3 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM
Picky Abstract Machine
es la máquina (virtual) que ejecuta binarios de Picky
Tiene
algunos registros
memoria para el código
memoria para la pila
memoria dinámica (heap)
descriptores de procedimiento, tipo, variable
tabla de contadores de programa a fichero-línea
http://127.0.0.1:3999/s11.gen.slide#1
Page 4 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Registros
PC Contador de programa. Apunta a instrucciones.
FP Frame Pointer. Apunta a una posición en la pila.
para localizar el record que activa una llamada a procedimiento
SP Stack Pointer. Apunta a una posición en la pila.
VP (Local) variable Pointer. Localiza variables locales
apunta a la zona de variables locales dentro del frame
AP Argument Pointer. Localiza direcciones de argumentos en el frame
PID Procedure Identifier. Apunta a un descriptor de procedimiento o función.
http://127.0.0.1:3999/s11.gen.slide#1
Page 5 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Memoria de Texto
Contiene el programa.
Cada instrucción es un código de byte almacenado en una palabra
Las que tienen argumentos usan una palabra extra por argumento
El PC apunta a una de estas palabras (no bytes).
La primera dirección es 0
http://127.0.0.1:3999/s11.gen.slide#1
Page 6 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Pila
Direccionada byte a byte
En la parte baja de la pila están las variables globales
Luego hay registros de activación para cada llamada a procedimiento
SP, FP, VP y AP apuntan a la pila
http://127.0.0.1:3999/s11.gen.slide#1
Page 7 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Heap
Contiene las variables dinámicas
Cada una identificada por un puntero o descriptor
http://127.0.0.1:3999/s11.gen.slide#1
Page 8 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Descriptores
De procedimiento:
indican los metadatos de cada procedimiento o función
Ej. cuántos argumentos y dónde está su código
De tipo:
información de depuración y metadatos para los tipos
De variable
idem
http://127.0.0.1:3999/s11.gen.slide#1
Page 9 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Instrucciones (1)
ICnop = 0,
ICle,
ICge,
ICpow,
IClt,
ICgt,
ICmul,
ICdiv,
ICmod,
ICadd,
ICsub,
ICminus,
ICnot,
ICor,
ICand,
ICeq,
ICne,
ICptr,
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
nop */
le|r -sp -sp +sp */
ge|r -sp -sp +sp */
pow -sp -sp +sp */
lt|r -sp -sp +sp */
gt|r -sp -sp +sp */
mul|r -sp -sp +sp */
div|r -sp -sp +sp */
mod|r -sp -sp +sp */
add|r -sp -sp +sp */
sub|r -sp -sp +sp */
minus|r -sp +sp */
not -sp +sp */
or -sp -sp +sp */
and -sp -sp +sp */
eq|r|a -sp -sp +sp */
ne|r|a -sp -sp +sp */
ptr -sp +sp */
obtain address for ptr in stack */
http://127.0.0.1:3999/s11.gen.slide#1
Page 10 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Instrucciones (2)
ICpush=ICargs,
ICindir,
ICjmp,
ICjmpt,
ICjmpf,
ICidx,
ICfld,
ICdaddr,
ICdata,
ICeqm,
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
push|r n +sp */
push n in the stack */
indir|a n -sp +sp */
replace address with referenced bytes */
jmp addr */
jmpt addr */
jmpf addr */
idx tid -sp -sp +sp */
replace address[index] with elem. addr. */
fld n -sp +sp */
replace obj addr with field (at n) addr. */
daddr n +sp */
push address for data at n */
data n +sp */
push n bytes of data following instruction */
eqm n -sp -sp +sp */
compare data pointed to by addresses */
http://127.0.0.1:3999/s11.gen.slide#1
Page 11 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Instrucciones (3)
ICnem,
ICcall,
ICret,
ICarg,
IClvar,
ICstom,
ICsto,
ICcast,
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
/*
nem n -sp -sp +sp */
compare data pointed to by addresses */
call pid */
ret pid */
arg n +sp */
push address for arg object at n */
lvar n +sp*/
push address for lvar object at n */
stom tid -sp -sp */
cp tid's sz bytes from address to address */
sto tid -sp -sp */
cp tid's sz bytes to address from stack */
cast|r tid -sp +sp */
convert int (or real |r) to type tid */
http://127.0.0.1:3999/s11.gen.slide#1
Page 12 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
PAM: Binarios
Para
src/lang/f.p (src/lang/f.p)
El ensamblador generado podría ser
src/lang/f.pam (src/lang/f.pam)
Ver la descripción de PAM en
The Picky Programming Language (http://lsub.org/ls/export/picky.pdf)
http://127.0.0.1:3999/s11.gen.slide#1
Page 13 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
Hay que recorrerse los AST de las declaraciones del programa
Y generar el trozo correspondiente del objeto para cada una
Pero sólo si no hay errores
ni sintácticos
ni semánticos
http://127.0.0.1:3999/s11.gen.slide#1
Page 14 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
func main() {
os.Args[0] = "pick"
flag.Usage = usage
flag.Parse()
args := flag.Args()
if len(args) != 1 {
usage()
}
l, err := newFileLex(args[0])
if err != nil {
Fatal("%s: %s", args[0], err)
}
yyParse(l)
if nerrors == 0 {
gen(os.Stdout)
}
os.Exit(nerrors)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 15 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
Hay que recorrer los entornos y generar código para todos
los símbolos definidos
Luego emitir el código generado en el orden apropiado
func gen(w io.Writer) {
forall(func (s *Sym) {
gtypes = append(gtypes, s)
}, Stype)
forall(func (s *Sym) {
gvars = append(gvars, s)
}, Sconst, Svar)
forall(func (s *Sym) {
gprocs = append(gprocs, s)
genproc(s)
}, Sproc, Sfunc)
emitentry(w)
emittypes(w)
emitvars(w)
emitprocs(w)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 16 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
type Gen func(sym *Sym);
func forall(g Gen, kinds ...Skind) {
for _, e := range envs {
for _, s := range e.order {
for _, k := range kinds {
if s.kind == k {
if debugGen {
fmt.Printf("gen %s\n", s)
}
g(s)
break
}
}
}
}
}
Con una función que imprime el nombre del símbolo
tenemos esta salida (src/lang/f.outa)
http://127.0.0.1:3999/s11.gen.slide#1
Page 17 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
Declaramos globales para lo que tenemos que emitir
var gtypes, gvars, gprocs []*Sym
var entry int
Y lo usaremos luego como en
func emitentry(w io.Writer) {
fmt.Fprintf(w, "#!/bin/pam\n")
fmt.Fprintf(w, "entry %d\n", entry)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 18 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Atributos para generación de código
En cada símbolo vamos a guardar un buffer para
el trozo de código a emitir, y luego lo emitiremos.
type Icode int
type Inst struct {
comment string
op Icode
arg int
}
type Sym struct {
....
code []Inst
pc int
...
}
Y conforme veamos que necesitamos más información de
un símbolo, creamos nuevos atributos si no los tenemos.
http://127.0.0.1:3999/s11.gen.slide#1
Page 19 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Atributos para generación de código
Usaremos esto para generar instrucciones y comentarios
func genComment(prog []Inst, s string) []Inst {
i := Inst{comment: s}
return append(prog, i)
}
func genInst(pc int, prog []Inst, ic Icode, arg int) (int, []Inst) {
i := Inst{op: ic, arg: arg}
pc++
if ic.hasArg() {
pc++
}
return pc, append(prog, i)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 20 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Datos
Para generar constantes y variables globales
hay que asignar una dirección a cada una
func gen(w io.Writer) {
...
forall(func (s *Sym) {
genvar(s)
gvars = append(gvars, s)
}, Sconst, Svar)
...
emitvars(w)
}
var daddr int
func genvar(s *Sym) {
if s.val == nil {
return
}
s.addr = daddr
daddr += s.val.typ.Len()
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 21 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Datos
Luego incluimos addr como nuevo atributo en Sym
Ojo, hay expresiones que requiren inventar `variables'
Por ejemplo el Nd para "hola"
var tmpid int
func genTemp(nd *Nd) {
name := fmt.Sprintf("tmp%d", tmpid)
tmpid++
s := &Sym{name: name, kind: Sconst, id: ID, typ: nd.typ, val: nd}
gvars = append(gvars, s)
nd.sym = s
genvar(s)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 22 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Código
PAM require asignar un id a cada procedimiento o función
Basta generar código para la sentencia BLOCK del cuerpo
var procid int
func genproc(s *Sym) {
if s.val == nil {
fmt.Printf("no body for %s\n", s)
return
}
bdy := s.val.args[len(s.val.args)-1]
if bdy.op != BLOCK {
panic("genproc: bug")
}
s.procid = procid
s.code = genComment(nil, s.String())
s.pc, s.code = genstmt(pc, s.code, bdy)
pc = s.pc
procid++
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 23 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Sentencias
Para generar un bloque, generamos sentencia tras sentencia
func genstmt(pc int, prog []Inst, nd *Nd) (int, []Inst) {
prog = genComment(prog, nd.String())
switch nd.op {
case NOP:
case BLOCK:
for i := range nd.args {
pc, prog = genstmt(pc, prog, nd.args[i])
}
...
}
return pc, prog
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 24 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Sentencias
Para generar un return
generamos el código que calcula el valor retornado (en la pila)
generamos el código de la instrucción de retorno
func genstmt(pc int, prog []Inst, nd *Nd) (int, []Inst) {
prog = genComment(prog, nd.String())
switch nd.op {
...
case RETURN:
pc, prog = genExpr(pc, prog, nd.args[0])
pc, prog = genInst(pc, prog, ICret, procid)
...
}
return pc, prog
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 25 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Expresiones
Para generar el código para evaluar una expresión
Generamos instrucciones que usan la pila para evaluarla
Por ej., para constantes básicas:
func genExpr(pc int, prog []Inst, nd *Nd) (int, []Inst) {
prog = genComment(prog, nd.String())
switch nd.op {
case INT:
pc, prog = genInst(pc, prog, ICpush, nd.ival)
case FLOAT:
i := math.Float32bits(float32(nd.rval))
pc, prog = genInst(pc, prog, ICpush, int(i))
case CHAR:
pc, prog = genInst(pc, prog, ICpush, int(nd.cval))
...
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 26 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Parámetros y variables locales
La forma de direccionar parámetros y variables locales
depende de la arquitectura objeto
normalmente utiliza el frame pointer para localizarlos
require asignar una dirección (relativa en el frame) a cada uno
Pero en PAM hay instrucciones para direccionar
el parámetro n
la variable local n
Tan sólo tenemos que darle un índice único a cada una
Los parámetros por referencia requiren una indirección
http://127.0.0.1:3999/s11.gen.slide#1
Page 27 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Parámetros y variables locales
Luego necesitamos definir isref, isparm y islvar
func defparms(proc *Sym, parms []*Nd) {
addr := 0
for i := range parms {
if parms[i].op != PARM {
panic("defparms: bug: not a parm")
}
defvar(parms[i].sym, parms[i].sym.tnd)
parms[i].sym.addr = addr
if parms[i].bval {
parms[i].sym.isref = true
} else {
parms[i].sym.isparm = true
}
addr++
proc.parms = append(proc.parms, parms[i].sym)
}
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 28 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Expresiones
Podemos entonces
func genExpr(pc int, prog []Inst, nd *Nd) (int, []Inst) {
switch nd.op {
case ID:
if nd.sym.isref {
pc, prog = genInst(pc, prog, ICarg, nd.sym.addr)
pc, prog = genInst(pc, prog, ICindir, 8)
break
}
if nd.sym.isparm {
pc, prog = genInst(pc, prog, ICarg, nd.sym.addr)
break
}
if nd.sym.islvar {
pc, prog = genInst(pc, prog, IClvar, nd.sym.addr)
break
}
pc, prog = genInst(pc, prog, ICdaddr, nd.sym.addr)
...
http://127.0.0.1:3999/s11.gen.slide#1
Page 29 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Expresiones
Para operadores evaluamos los argumentos
Y luego la instrucción del operador
func genExpr(pc int, prog []Inst, nd *Nd) (int, []Inst) {
switch nd.op {
case '-':
pc, prog = genExpr(pc, prog, nd.args[0])
if len(nd.args) == 1 {
pc, prog = genInst(pc, prog, ICminus, nd.sym.addr)
return pc, prog
}
pc, prog = genExpr(pc, prog, nd.args[1])
pc, prog = genInst(pc, prog, ICsub, nd.sym.addr)
...
Ojo a operadores unarios y binarios
http://127.0.0.1:3999/s11.gen.slide#1
Page 30 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Estructuras de control
Para
while(expr) {
stmt
}
Queremos
loop:
eval expr
jump if false to end
stmt
jump to loop
end:
http://127.0.0.1:3999/s11.gen.slide#1
Page 31 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Estructuras de control
Problema
loop:
eval expr
jump if false to end
stmt
jump to loop
end:
No sabemos que PC corresponde a end antes de generar el código
http://127.0.0.1:3999/s11.gen.slide#1
Page 32 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Back-patching
No sabemos que PC corresponde a end antes de generar el código
Solución:
utilizamos una variable libre para la dirección del salto
nos la inventamos cuando la necesitamos
ya le daremos un valor (antes de escribir el código!)
Dicho de otro modo:
usamos un puntero a un entero en lugar de un entero para la etiqueta
y más adelante le daremos el valor
http://127.0.0.1:3999/s11.gen.slide#1
Page 33 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Back-patching
No sabemos que PC corresponde a end antes de generar el código
Otra solución:
Creamos una etiqueta
que apunta a la instrucción del salto
y más adelante actualizamos la instrucción del salto
cuando le demos un valor a la etiqueta.
http://127.0.0.1:3999/s11.gen.slide#1
Page 34 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Estructuras de control
type Label struct{pc, usedat int}
func genstmt(pc int, prog []Inst, nd *Nd) (int, []Inst) {
...
case WHILE:
loop := Label{pc: pc}
end := Label{}
pc, prog = genExpr(pc, prog, nd.args[0])
end.usedat = pc
pc, prog = genInst(pc, prog, ICjmpf, 0)
genstmt(pc, prog, nd.args[1])
pc, prog = genInst(pc, prog, ICjmp, loop.pc)
end.pc = pc
prog[end.usedat].arg = end.pc
...
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 35 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
Una vez hemos generado el código, lo emitimos
func emitprocs(w io.Writer) {
for _, prg := range gprocs {
emitProg(w, prg.code, prg.pc)
}
}
func emitProg(w io.Writer, prg []Inst, pc int) {
for i := range prg {
if prg[i].comment != "" {
fmt.Fprintf(w, "# %s\n", prg[i].comment)
} else {
fmt.Fprintf(w, "%05d\t%s\n", pc, prg[i])
pc++
if prg[i].op.hasArg() {pc++}
}
}
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 36 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Generación de código
func (i Inst) String() string {
if i.op.hasArg() {
return fmt.Sprintf("%s\t%#x", i.op, i.arg)
}
return fmt.Sprintf("%s\t%s", i.op)
}
http://127.0.0.1:3999/s11.gen.slide#1
Page 37 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
¿Ahora qué?
Tenemos un prototipo del compilador
Hay que usarlo con cuantos más programas mejor
tanto correctos
como erróneos
Los usuarios escriben programas que nunca imaginarías
Seguramente hay bugs por
falta de comprobaciones semánticas
y otras meteduras de pata
http://127.0.0.1:3999/s11.gen.slide#1
Page 38 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
¿Ahora qué?
Si quieres ver cómo quedaría un compilador para Picky
Mira el que hay en archivo (tar comprimido, .tgz) que hay en
la página de picky (http://lsub.org/fdp/picky.html)
Ese está hecho en C
pero ahora debería ser fácil de entender
y cientos de estudiantes (miles?) lo han usado
por lo que debería tener no demasiados bugs
Mira también otros compiladores para otros lenguajes
Y programa alguno tú mismo
http://127.0.0.1:3999/s11.gen.slide#1
Page 39 of 40
Compiladores: Generación de código - (c)2014 LSUB
1/25/16, 2:54 PM
Questions?
Francisco J Ballesteros
LSUB, URJC
http://lsub.org (http://lsub.org)
http://127.0.0.1:3999/s11.gen.slide#1
Page 40 of 40
