TD 7 - Produção de código

O objectivo desta prática laboratórial é estender a mini-linguagem Arith da prática TD 1 com funções. Pretendemos poder escrever programas da forma seguinte : 
  set f(x,y) = let z = x + 4 in x + y + z
  set g(x) = f(x,10) + 3
  print g(4)

Para ajudar-vos, é fornecido um esqueleto do compilador no qual certas partes estão por completar. Uma vez este arquivo descompactado, obtém-se um directório arithfun/ contendo os ficheiros seguintes :

ast.mli a sintaxe abstrata de Arith (completo)
lexer.mll o analisador léxico (completo)
parser.mly o analisador sintáctico (completo)
x86_64.ml para escrever código X86-64 (completo)
compile.ml a compilação propriamente dita (por completar)
main.ml o programa principal (completo)
Makefile para automatizar a compilação (completo)
test.exp um ficheiro de testes fichier de tests, utilizado quando se invoca make

O código compila, mas está incompleto : devem completar o ficheiro compile.ml.

Questão 1. Alocação das variáveis

Antes da produção de código X86-64, vamos determinar a localização de cada variável.

A variáveis globais introduzidas por set são alocadas no segmento de dados, et são identificadas pelos seus nomes. A tabela de dispersão Compile.genv contém as variáveis globais que foram introduzidas com set.

As variáveis locais, introduzidas com let ou argumentos de funções ficam alocadas na pilha. Nos dois casos, são referenciadas pelas suas posições relativas ao registo %rbp. Mais precisamente, adoptamos um esquema de compilação clássica : o caller passa os argumentos na pilha, em seguida o callee salvaguarda %rbp na pilha e aloca o espaço necessário para as variáveis locais. Assim, para uma função da forma set f(x,y) = let z = x+3 in z+y, teremos uma tabela de activação com a seguinte forma : 

         |   .......     |
         |       x       |   construído
         |       y       |   pelo caller
  ----------------------------------
         |ender. retorno |
  ----------------------------------
 %rbp--> |  saved %rbp   |   construído 
         |       z       |   pelo callee
         |   .......     |
isto é, offfset de 24 para x, de 16 para y e -8 para z.

O objectivo desta questão está na reconstrução de novas árvores de sintaxe abstracta nas quais as variáveis locais ficam representadas pelos inteiros que arquivam e testemunham estes offset. Para tal, deverá completar as duas funções seguintes de compile.ml : 

  val alloc_expr: local_env -> int -> Ast.pexpr -> Ast.expr * int
  val alloc_stmt: Ast.pstmt -> Ast.stmt
A função alloc_expr recebe em argumento O inteiro retornado por alloc_expr corresponde ao tamanho total ocupado pelas variáveis locais da expressão. Note que as novas árvores de sintaxe abstracta permitam a distinção entre as variáveis locais (LVar) e as variáveis globais (GVar). A função alloc_expr deve levantar a excepção VarUndef se esta se depara com uma variávelnão declarada.

A função alloc_stmt retorna instruções contendo um argumento suplementar que indica o espaço memória por reservar na pilha para variáveis locais às expressões consideradas. Note que o construtor Fun não contém mais os parâmetros formais da função, porque as ocorrências destas são agora representadas por inteiros. Mais, a função alloc_stmt preenche a tabela de dispersão Compile.genv com as variáveis.

Exemplo : sobre o programa seguinte 

set h =
  let x = 4 in
  let y = (let z = 10 * 10 in x + z) in
  x + y
obtemos a árvore seguinte à saída da analise sintáctica : 
Ast.PSet ("h",
    Ast.PLetin ("x", Ast.PCst 4,
     Ast.PLetin ("y",
      Ast.PLetin ("z", Ast.PBinop (Ast.Mul, Ast.PCst 10, Ast.PCst 10),
       Ast.PBinop (Ast.Add, Ast.PVar "x", Ast.PVar "z")),
      Ast.PBinop (Ast.Add, Ast.PVar "x", Ast.PVar "y"))))
As variáveis são por enquanto strings. Após a fase de alocação, no entanto, teremos a árvore seguinte 
Ast.Set ("h",
  Ast.Letin (-8, Ast.Cst 4,
   Ast.Letin (-16,
    Ast.Letin (-16, Ast.Binop (Ast.Mul, Ast.Cst 10, Ast.Cst 10),
     Ast.Binop (Ast.Add, Ast.LVar (-8), Ast.LVar (-16))),
    Ast.Binop (Ast.Add, Ast.LVar (-8), Ast.LVar (-16)))),
  16)
onde as variáveis x, y e z são agora representadas pelos inteiros -8, -16 et -16 (nota-se que as variáveis y e z estão alocadas no mesmo local) e onde o terceiro argumento de Set, ou seja 16, representa o número total de bytes que devem ser alocados para as variáveis desta construção.
solução

Questão 2. Produção de código

Completar as funções compile_expr e compile_stmt para produzir código X86-64. Um módulo OCaml X86-64 é fornecido para construir o código X86-64.

Testar com make, o que deve provocar a vizualização dos inteiros de 1 a 19, nesta ordem.

solução
voltar à pagina da UC