TD 1 - Assembly X86-64

Esta Prática Laboratorial introduz a produção de código Asembly x86-64. Caso necessário, poderão utilizar Nemiver para executar passo a passo código assembly, ou ainda gdb.

Esta página de Andrew Tolmach agrupa um conjunto relevante de apontadores para escrever / depurar código assembly X86-64 e em particular as suas notas sobre o assembly X86-64.

1. Pequenos exercícios sobre o assembly X86-64

Relembramos que um pequeno programa assembly escreve-se num ficheiro com extensão .s e tema forma seguinte :
      .text
      .globl main
main:
      ...
      mov  $0, %rax       # código de saída
      ret
      .data
      ...
Pode compilar e executar este ficheiro de forma não-interactiva com o comando seguinte:
  gcc ficheiro.s && ./a.out

a. Expressões aritméticas

Implementar pequenos programas para avaliar e vizualizar o resultado das expressões aritméticas seguintes : O resultado esperado é
10
42
7
-9
Para vizualizar um inteiro, poderão utilizar a função seguinte :
print_int:
        mov     %rdi, %rsi
        mov     $message, %rdi  # argumentos para printf
        mov     $0, %rax
        call    printf
        ret
        .data
message:.string "%d\n"
solução com registos
solução com recurso à pilha

b. Expressões Booleanas

Usando a convenção de que o inteiro 0 representa o valor booleano falso e que qualquer outro inteiro codifica o valor verdade, escrever os programas em assembly que avaliam e vizualizam o resultado das expressões seguintes (deve mostrar true ou false no caso de um valor booleano) : O resultado esperado é
false
20
true
Poderá ter utilidade escrever uma função print_bool para mostrar um boleano.
solução

c. Variáveis globais

Escrever um programa em assembly que avalia as três instruções seguintes :
  let x = 2
  let y = x * x
  print (y + x)
Alocar-se-á as variáveis x e y no mesmo segmente de dados. O resultado esperado é 6.
solução

d. Variáveis locais

Escrever um programa em assembly que avalia o programa seguinte :
  print (let x = 3 in x * x)
  print (let x = 3 in (let y = x + x in x * y) + (let z = x + 3 in z / z))
Alocar-se-á as variáveis x, y e z na pilha. O resultado esperado é
9
19
solução

2. Compilação de uma mini linguagem

O objectivo deste exercício é a escrita de um pequeno compilador para uma mini-linguagem aritmética, designada de Arith, para a linguagem assembly X86-64. Um programa da linguagem Arith é composto por uma sequência de instruções que são, alternativamente, a introdução de uma variável global com a sintaxe
  set <ident> = <expr>
a vizualização do valor de uma expressão, com a sintaxe
  print <expr>
Aqui, <ident> designa o nome de uma variável e <expr> uma expressão aritmética. As expressões aritméticas podem ser construidas a partir de constantes inteiros, variáveis, da soma, da substracção, da multiplicação, da divisão, de parêntesis e de uma construção let in que introduz uma variável local. Mais formalmente a sintaxe das expressões aritméticas é a seguinte :
  <expr> ::= <constante inteira>
           | <ident>
           | ( <expr> )
           | <expr> + <expr>
           | <expr> - <expr>
           | <expr> * <expr>
           | <expr> / <expr>
           | - <expr>
           | let <ident> = <expr> in <expr>
Um exemplo de programa Arith pode ser :
set x = 1 + 2 + 3*4
print (let y = 10 in x + y)
Os identificadores das variáveis são formados de letras e de algarismos mas não podem começar por um algarismo. As palavras set, print, let et in são palavras reservadas, i.e. não podem ser utilizados como identificadores de variáveis. A prioridade dos operadors aritméticos é a usual e a construção let in tem a prioridade mais baixa.

Para ajudar à construção deste compilador, é-vos dado a sua estrutura de base (na forma de um conjunto de ficheiro OCaml e de um Makefile) qque pode ser descarregado aqui : arithc.zip. Uma vez este arquivo descomprimido obtém-se um directório arithc/ que contém os ficheiros seguintes :

ast.mli a sintaxe abstracta de Arith (completo)
lexer.mll o lexer (completo)
parser.mly o parser (completo)
x86_64.mli, x86_64.ml para gerar código X86-64 (completo)
compile.ml o processo de compilação em si (por completar)
main.ml o programa principal (completo)
Makefile para automatizar a compilação (completo)

O código fornecido compila ; para iniciar o processo de compilação, basta executar make num terminal, ou melhor, compilar dentro do Emacs com M-x compile ou ainda C-c C-c. O código fornecido é no entento incompleto : o código assembly produzido é vazio. Deve completar o ficheiro compile.ml. Quando o processo de compilação falha, pode colocar o cursor do editor no local de erro com o comando Emacs M-x next-error ou ainda Ctrl-x `.

O executável produzido chama-se arithc e pode ser invocado com qualquer ficheiro Arith com a extenção .exp. Assim

  ./arithc fichiero.exp
tem por efeito produzir um ficheiro ficheiro.s que contém o código assembly resultante. Deve poder executar este ficheiro assembly de forma não-interactiva com o comando
  gcc fichier.s && ./a.out
Para depurar, poderá utilizar por exemplo Nemiver com o comando nemiver a.out, e executar passo a passo com F7.

Esquema de compilação

Realizar-se-á um processo compilação simples utilizando a pilha para arquivar os valores intermédios (i.e. os valores das sub-expressões). Relembra-se que um valor inteiro ocupa 8 bytes em memória. Pode alocar-se 8 bytes na pilha substraindo 8 ao valor de %rsp ou então utilizando a instrução pushq.

Os valores globais são alocados no segmento de dados (diretiva .data do assembly ; corresponde aqui ao campo data do tipo X8_64.program).

As variáveis locais são alocadas no fundo da pilha. O espaço necessário para o conjunto das variáveis locais será alocado no início da execução do programa (via uma substracção adequada sobre %rsp). O registo %rbp é posicionado por forma a apontar para o fundo da pilha ; assim toda a referência a uma variável local poderá ser feita com base em %rbp.

Tarefas por realizar

Deve ler CUIDADOSAMENTE o código que está em compile.ml. As partes por completar que estão assinaladas por (* POR COMPLETAR*), são as seguintes :
  1. a função compile_expr que compila uma expressão aritmética e numa sequência de instruções X86-64 cujo efeito é de colocar o valor de e no topo da pilha. Esta função está definida com recurso a função recursiva local comprec que toma como argumentos :

  2. a função compile_instr que compila uma instrução de Arith numa sequência de instruções X86-64. Nos dois casos (set x = e ou print e), deve-se começar por compilar e, para depois encontrar o valor de e nop topo da pilha (não se esqueça de desempilhar).

  3. A função compile_program que aplica compile_instr a todas as instruções do programa e junta o código :

Indicações : poder-se-á proceder elemento (da linguagem) por elemento, testando de cada vez, na ordem seguinte :

  1. expressões constantes Cst, instrução Print e saída com ret ;
  2. operações aritméticas (constructor Binop) ;
  3. variáveis globais (constructores Var e Set) ;
  4. variáveis locais (constructores Letin e Var).

Testar-se-á no final com o ficheiro test.exp (igualmente fornecido), e cujo resultado deverá ser :

60
50
0
10
55
60
20
43
solução

Desafio opcional

Para utilizar um poco menos de espaço na pilha, podemos melhorar um pouco o esquema de compilação para que o resultado de compile_expr se encontre no registo %rax no lugar do topo da pilha. Assim só os resultados das sub-expressões esquerdas precisam de serem empilhadas.
solução

retornar para a página da UC