compiladores: generación de códigolsub.org/comp/slides/s11.gen.pdf · o generamos un código...
TRANSCRIPT
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 1 of 40http://127.0.0.1:3999/s11.gen.slide#1
Compiladores: Generación decódigoFrancisco J BallesterosLSUB, URJC
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 2 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 3 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 4 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 5 of 40http://127.0.0.1:3999/s11.gen.slide#1
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.
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 6 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 7 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 8 of 40http://127.0.0.1:3999/s11.gen.slide#1
PAM: Heap
Contiene las variables dinámicas
Cada una identificada por un puntero o descriptor
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 9 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 10 of 40http://127.0.0.1:3999/s11.gen.slide#1
PAM: Instrucciones (1)
ICnop = 0, /* nop */ICle, /* le|r -sp -sp +sp */ICge, /* ge|r -sp -sp +sp */ICpow, /* pow -sp -sp +sp */IClt, /* lt|r -sp -sp +sp */ICgt, /* gt|r -sp -sp +sp */ICmul, /* mul|r -sp -sp +sp */ICdiv, /* div|r -sp -sp +sp */ICmod, /* mod|r -sp -sp +sp */ICadd, /* add|r -sp -sp +sp */ICsub, /* sub|r -sp -sp +sp */ICminus, /* minus|r -sp +sp */ICnot, /* not -sp +sp */ICor, /* or -sp -sp +sp */ICand, /* and -sp -sp +sp */ICeq, /* eq|r|a -sp -sp +sp */ICne, /* ne|r|a -sp -sp +sp */ICptr, /* ptr -sp +sp */ /* obtain address for ptr in stack */
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 11 of 40http://127.0.0.1:3999/s11.gen.slide#1
PAM: Instrucciones (2)
ICpush=ICargs, /* push|r n +sp */ /* push n in the stack */ICindir, /* indir|a n -sp +sp */ /* replace address with referenced bytes */ICjmp, /* jmp addr */ICjmpt, /* jmpt addr */ICjmpf, /* jmpf addr */ICidx, /* idx tid -sp -sp +sp */ /* replace address[index] with elem. addr. */ICfld, /* fld n -sp +sp */ /* replace obj addr with field (at n) addr. */ICdaddr, /* daddr n +sp */ /* push address for data at n */ICdata, /* data n +sp */ /* push n bytes of data following instruction */ICeqm, /* eqm n -sp -sp +sp */ /* compare data pointed to by addresses */
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 12 of 40http://127.0.0.1:3999/s11.gen.slide#1
PAM: Instrucciones (3)
ICnem, /* nem n -sp -sp +sp */ /* compare data pointed to by addresses */ICcall, /* call pid */ICret, /* ret pid */ICarg, /* arg n +sp */ /* push address for arg object at n */IClvar, /* lvar n +sp*/ /* push address for lvar object at n */ICstom, /* stom tid -sp -sp */ /* cp tid's sz bytes from address to address */ICsto, /* sto tid -sp -sp */ /* cp tid's sz bytes to address from stack */ICcast, /* cast|r tid -sp +sp */ /* convert int (or real |r) to type tid */
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 13 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 14 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 15 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 16 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 17 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 18 of 40http://127.0.0.1:3999/s11.gen.slide#1
Generación de código
Declaramos globales para lo que tenemos que emitir
var gtypes, gvars, gprocs []*Symvar 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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 19 of 40http://127.0.0.1:3999/s11.gen.slide#1
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 inttype 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.
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 20 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 21 of 40http://127.0.0.1:3999/s11.gen.slide#1
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 intfunc genvar(s *Sym) { if s.val == nil { return } s.addr = daddr daddr += s.val.typ.Len()}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 22 of 40http://127.0.0.1:3999/s11.gen.slide#1
Datos
Luego incluimos addr como nuevo atributo en Sym
Ojo, hay expresiones que requiren inventar `variables'
Por ejemplo el Nd para "hola"
var tmpid intfunc 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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 23 of 40http://127.0.0.1:3999/s11.gen.slide#1
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 intfunc 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++}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 24 of 40http://127.0.0.1:3999/s11.gen.slide#1
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}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 25 of 40http://127.0.0.1:3999/s11.gen.slide#1
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}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 26 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)) ...}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 27 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 28 of 40http://127.0.0.1:3999/s11.gen.slide#1
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) }}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 29 of 40http://127.0.0.1:3999/s11.gen.slide#1
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) ...
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 30 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 31 of 40http://127.0.0.1:3999/s11.gen.slide#1
Estructuras de control
Para
while(expr) { stmt}
Queremos
loop: eval expr jump if false to end stmt jump to loopend:
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 32 of 40http://127.0.0.1:3999/s11.gen.slide#1
Estructuras de control
Problema
loop: eval expr jump if false to end stmt jump to loopend:
No sabemos que PC corresponde a end antes de generar el código
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 33 of 40http://127.0.0.1:3999/s11.gen.slide#1
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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 34 of 40http://127.0.0.1:3999/s11.gen.slide#1
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.
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 35 of 40http://127.0.0.1:3999/s11.gen.slide#1
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 ...}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 36 of 40http://127.0.0.1:3999/s11.gen.slide#1
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++} } }}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 37 of 40http://127.0.0.1:3999/s11.gen.slide#1
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)}
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 38 of 40http://127.0.0.1:3999/s11.gen.slide#1
¿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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 39 of 40http://127.0.0.1:3999/s11.gen.slide#1
¿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
1/25/16, 2:54 PMCompiladores: Generación de código - (c)2014 LSUB
Page 40 of 40http://127.0.0.1:3999/s11.gen.slide#1
Questions?
Francisco J BallesterosLSUB, URJChttp://lsub.org (http://lsub.org)