terça-feira, fevereiro 27, 2007

Construindo um Compilador - Parte 1

Esta série de posts foi instigada por uma mensagem no grupo C++ Brasil.

Minha primeira experiência em construir um compilador foi na faculdade. Lembro vagamente que era um compilador que gerava um programa para uma calculadora Texas a partir de uma linguagem parecida com Basic.

Recem formado, tive a oportunidade de participar de uma série de cursos na Scopus, não relacionados diretamente a projetos. Um deles foi A Construção de Um Compilador, lecionado pelo professor Valdemar Setzer. O material para este curso foi uma versão preliminar de um livro do próprio Setzer (em conjunto com Inês S Homem de Melo), que posteriormente viria a ser publicado pela Editora Campus.

Vários anos depois, tive a oportunidade de utilizar na prática estes conhecimentos, ao participar da definição e desenvolvimento de uma linguagem de script para o programa de comunicação Zapt da Humana Informática.

A forma de implementar um compilador que vou apresentar nestes posts se baseia diretamente no livro do Setzer. Obviamente vou ser bastante superficial nestes posts (o livro tem mais de 300 páginas).



O Que é Um Compilador?

Podemos dizer que um compilador é um programa que traduz um programa escrito em uma linguagem (linguagem fonte) para uma outra linguagem (linguagem objeto). Tipicamente a linguagem fonte é uma linguagem de alto nível e a linguagem objeto é o código de máquina.

Um parente próximo do compilador é o interpretador, que ao invés de gerar o programa em linguagem objeto ele o executa.

Um compilador pode não converter diretamente a linguagem fonte na linguagem objeto, ele pode ser composto de vários passos utilizando linguagens intermediárias. Um exemplo típico são compiladores que usam linguagem Assembly como uma linguagem intermediária.

Definindo Uma Linguagem

Tipicamente a definição de uma linguagem começa com os itens básicos para a escrita de programas: palavras reservadas, símbolos especiais, constantes e identificadores. Estes itens são denominados itens léxicos.

A forma como estes itens léxicos são combinados para gerar declarações, expressões e comandos em geral de uma linguagem é definida pela gramática da linguagem. Existem várias formas de se definir uma linguagem, algumas mais formais (como a notação BNF) e outras menso. Nestes posts vou usar os grafos sintáticos para descrever a gramática.

A definição da linguagem pode facilitar ou complicar a sua compilação. O método que será abordado é mais adequado para lingugens "bem comportadas".

Estrutura de Um Compilador

Tradicionalmente se divide o compilador em três grandes partes:
  • Analisador Léxico: reconhece no fonte os itens léxicos
  • Analisador Sintático: verifica se a sequência de itens léxicos contida no fonte está de acordo com a gramática da linguagem e reconhece as várias construções.
  • Analisador Semântico: Gera o código objeto para as construções reconhecidas pala analisador sintático.
No próximo post veremos como fazer um analisador léxico.

quarta-feira, fevereiro 21, 2007

Programação Assembly no ARM - Parte IV

Nesta parte vamos ver as instruções de acesso à memória. Como vimos na parte anterior, as instruções lógicas e aritméticas do ARM trabalham com operandos nos registradores. As instruções de acesso à memória no ARM são primordialmente a carga de um registrador em uma posição de memória e o armazenamento do conteúdo do registrador em uma posição da memória, conforme dita a filosofia RISC.

Estas instruções, denominadas de Single Data Transfer, são codificadas conforme a figura abaixo:

Note que embora sejam apenas duas instruções assembly, LDR e STR, existem uma grande quantidade de opções. Como sempre, o opcode contém uma condição. O bit L diferencia a instrução de Load (carga do registrador a partir da memória) da instrução de Store (armazenamento na memória do conteudo do registrador). Rd indica o registrador que receberá o valor lido (LDR) ou que contém o valor a ser armazenado (STR). O bit B indica se estamos manipulando um word (32 bits) ou byte (8 bits); existem instruções separadas para manipular valores de 16 bits (half-words). O resto dos campos do opcode determinam o endereço da posição de memória a ser manipulada.

Este endereço é determinado por duas partes: a base (que fica no registrador Rn) e o offset (que, conforme o bit I, pode ser um valor imediato de 12 bits ou o conteúdo de um registrador deslocado). O deslocamento do registrador usado para o offset é determinado de forma semelhante ao usado para o valor imediato nas instruções lógicas e aritméticas. O bit U indica se o offset deve ser somado ou subtraído da base.

O bit P determina se a combinação da base com o offset deve ser feita antes (pré-indexação) ou depois (pós-indexação) do acesso à memória. O bit W permite atualizar o registrador base com o valor final do endereço. Quando se especifica a pós-indexação, o ARM atualiza sempre o registrador base, para não alterá-lo deve-se colocar um offset de zero. Na prática, isto significa:
  • P = 0, W = 0: normalmente tratado pelo ARM como P = 0, W = 1. (para ser preciso, no modo privelegiado em um processador com hardware de gerenciamento de memória esta combinação faz com que o endereço seja tratado como um endereço de usuário ao invés de endereço de sistema).
  • P = 1, W = 0: combina base e offset para determinar o endereço, o registrador base fica inalterado. Útil, por exemplo, para acessar um item de um vetor (base é o endereço inicial e o offset é o deslocamento em relação ao início).
  • P = 0, W = 1: usa somente a base para determinar o endereço, após o acesso à memória a base é atualizada com a combinação da base com o offset. Permite implementar em uma única instrução a construção *p++ do C (acessa a posição apontada pelo registrador base e o avança para o próximo item).
  • P = 1, W = 1: combina base e offset para determinar o endereço, o registrador base é atualizado para o endereço usado. Permite implementar em uma única instrução a construção *++p do C (avança o registrador base para o próximo item e o acessa).
A codificação da instrução em Assembly é a seguinte:

LDR{cond}{B} Rd,<endereço>
STR{cond}{B} Rd,<endereço>

Onde B indica que é um acesso a byte.

<endereço> pode ser
  • uma expressão, que resulta em um endereço. O Assembler tenta montar uma instrução que combine um offset ao PC para obter este endereço, se não conseguir gerará um erro. Esta forma é útil para carregar em registradores constantes que estão armazenadas junto ao código.

  • uma especificação de endereçamento pré-indexado (combina base e offset antes de acessar a memória):

    • [Rn]

    • [Rn,#expressão] {!}

    • [Rn,{+/-}Rm{,<shift>}] {!}

    • A presença de ! indica que o registrador base deve ser atualizado (W = 1).

  • uma especificação de endereçamento pós-indexado (combina base e offset depois de acessar a memória):
    • [Rn],#expressão

    • [Rn],{+/-}Rm{,}

    • nestes casos o registrador base é sempre atualizado.
Alguns exemplos

; coloca valores conhecidos em R1 e R2
MOV R1,#0
MOV R2,#4

; coloca em R0 o conteúdo da posição 0 da memória
LDR R0,[R1]

; coloca em R0 o conteúdo da posição 4 da memória
LDR R0,[R1,R2]

; coloca em R0 o conteúdo da posição 32 da memória
LDR R0,[R1,R2,LSL #3]

; idem
LDR R0,[R1+#32]

; coloca em R0 o conteúdo da posição 4 da memória
; R1 passa a ser 4
LDR R0,[R1,R2]!
; coloca em R0 o conteúdo da posição 4 da memória
; R1 passa a ser 8
LDR R0,[R1],R2

Reparar que não é possível especificar diretamente um endereço qualquer da memória, pois o offset imediato tem 12 bits e um endereço tem 32 bits. Além disso, já vimos que as instruções lógicas e aritméticas são limitadas quanto aos valores imediatos que podem ser usados. Para carregar em um registrador um endereço ou constante qualquer, é preciso armazená-lo em memória em uma posição que possa ser acessada por um LDR. Isto torna frequente a presença de constantes no meio do código:

...
LDR Rd,X ; usa endereçamento relativo ao PC
...
X .long valor ; em algum lugar próximo

Para facilitar isto, o Assembler permite a seguinte construção:

LDR Rd,=valor

Se possível, o assembler gera uma instrução MOV ou MVN para carregar o valor no registrador. Se isto não for possível, o assembler coloca a constante em um trecho próximo e gera uma instrução LDR usando endereçamento relativo ao PC.

Outras Instruções de Acesso à Memória

As instruções LDRH, LDRSH e STRH permitem carregar e armazenar valores de 16 bits (half word). A instrução LDRSH faz a "extensão do sinal", isto é, preenche os 16 bits mais significativos do registrador com o bit mais significativo do valor de 16 bits, de forma a manter o sinal do valor. O mesmo opcode permite também carregar em um registrador um valor de 8 bits com extensão de sinal (LDRSB). Estas instruções oferecem os mesmos recursos de endereçamento que LDR e STR.

As instruções LDM e STM (Block Data Transfer) permitem carregar ou armazenar um conjunto de registradores em posições contiguas de memória. A codificação destas instruções é apresentada abaixo:


Register list possui 16 bits, um para cada registrador. Os bits com 1 indicam os registradores a serem transferidos. O endereço inicial é obtido a partir de um registrador, que será automaticamente incrementado ou decrementado, antes ou depois de transferir cada registrador. O registrador utilizado pode ou não ser atualizado ao final da transferência.

A codificação em assembly destas instruções é:

LDM{cond}<fd|ed|fa|ea|ia|ib|da|db> Rn{!},<rlist>
STM{cond}<fd|ed|fa|ea|ia|ib|da|db> Rn{!},<rlist>

Onde
  • {cond} é a condição em que a instrução será executada.

  • FD, ED,..DB determinam os bits P e U. FD, ED, FA e EA são (respectivamente) idênticos a IA, IB, DA e DB; os primeiros são utilizados para documentar quando os registradores estão sendo transferidos para uma pilha.

  • ! indica que o registrador Rn deve ser atualizado ao final
Alguns exemplos:

; salva todos os registradores em posições
; consecutivas a partir da apontada por R0
STMIA R0,{R0-R15}

; empilha os registradores (exceto R15/PC)
STMFD SP!,{R0-R15}

; Salva na pilha os registradores R1, R3 e R5
STMFD SP!,{R1, R3, R5}

; desempilha os registradores
LDMED SP!,{R0-R14}

terça-feira, fevereiro 06, 2007

Programação Assembly no ARM - Parte III

Continuando o nosso estudo das instruções, vamos examinar com mais detalhes o grupo de instruções de Data Processing. Este grupo contém as instruções aritméticas, lógicas e de movimentação. Estas instruções realizam uma operação sobre um ou dois operandos (Op1 e Op2) e colocam o resultado em um registrador (Rd) ou nos flags.

A figura abaixo mostra os vários campos do opcode destas instruções:

Na parte II nós já vimos os campos Cond e S. O campo Opcode determina a operação que será executada:

Opcode mne ação
0000 AND Rd := Op1 AND Op2
0001 EOR Rd := Op1 XOR Op2
0010 SUB Rd := Op1 - Op2
0011 RSB Rd := Op2 - Op1
0100 ADD Rd := Op1 + Op2
0101 ADC Rd := Op1 + Op2 + C
0110 SBC Rd := Op1 - Op2 + C - 1
0111 RSC Rd := Op2 - Op1 + C - 1
1000 TST posiciona flags conforme Op1 AND Op2
1001 TEQ posiciona flags conforme Op1 XOR Op2
1010 CMP posiciona flags conforme Op1 - Op2
1011 CMN posiciona flags conforme Op1 + Op2
1100 ORR Rd := Op1 OR Op2
1101 MOV Rd := Op2
1110 BIC Rd := Op1 AND NOT Op2
1111 MVN Rd := NOT Op2

Portanto o campo Rd determina o registrador (R0 a R15) que será o destino do resultado da operação. As instruções TST, TEQ, CMP e CMN ignoram este campo. Como o único resultado destas operações é o posicionamento dos flags, o bit S é sempre forçado pelos assemblers.

Op1 é sempre um registrador e é definido por Rn; as instruções MOV e MVN ignoram o campo Rn.

Existem duas opções para a codificação do campo Operand 2.

1. Se I for 0, o segundo operando é um registrador, cujo conteúdo pode ser deslocado:

Este deslocamento pode de quatro formas:
  • Lógico para a esquerda (LSL): desloca para a esquerda introduzindo zeros à direita
  • Lógico para a direita (LSR): desloca para a direita introduzindo zeros à esquerda
  • Aritmético para a direita (ASR): desloca para a direita repetindo o bit mais significativo na esquerda
  • Rotação para a direita (ROR): desloca para a direita, introduzindo na esquerda os bits que 'saem' à direita
Além disso, o número de bits a deslocar pode ser especificado diretamente no opcode (0 a 15) ou ser obtido de um outro registrador (neste caso é considerado o byte meno significativo do registrador, permitindo deslocamentos de 0 a 255 bits).

2. Se I for 1, o segundo operando é um valor imediato (codificado na própria instrução):
O valor de 8 bits (Imm) contido na instrução é expandido para 32 bits colocando-se zeros à esquerda e em seguida rodado para a direita o dobro de vezes do especificado em Rotate. Como Rotate tem 4 bits, isto significa que o valor pode ser rodado 0, 2, 4, 8 .. 30 bits para a direita. Embora esta codificação permita colocar um grande variedade de constantes na instrução, uma quantidade ainda maior não tem como ser codificada. Neste caso o valor precisa ser armazenado em uma posição da memória e carregado para um registrador antes de executar a operação. Por exemplo, as constantes 0, 1, 0x100 e 0x110 podem ser codificadas mas 0x101 não.

Vejamos agora como escrever estas instruções na linguagem Assembly.

MOV e MVN
{cond}{S} Rd,

CMP,CMN,TEQ,TST
{cond} Rn,

AND,EOR,SUB,RSB,ADD,ADC,SBC,RSC,ORR,BIC
{cond}{S} Rd,Rn,

onde

é o mnemônico da instrução
{cond} é a condição (opcional)
{S} indica que pode ser acrescentado S para a instrução afetar os flags
pode ser Rm{,} ou <#expressão>
pode ser Rs ou #expressão
é ASL, LSL, LSR, ASR ou ROR
Rd, Rn, Rm e Rs são os registradores R0 a R15

Quando Op2 for especificado com #expressão, o assembler tentará codificá-lo em um valor imediato. Se não conseguir, acusará erro.

Vejamos se alguns exemplos esclarecem um pouco:

MOV R1,#100 ; coloca 100 em R1
MOVS R1,R0 ; coloca o conteúdo de R0 em R1, atualiza os flags
MOV R1,R0 ASL 5 ; coloca R0 * 32 em R1
MOV R1, R0 ROR R2 ; coloca em R1 o valor de R0 rodado para a direita de R2 bits
ADD R2,R1,R0 ; soma R1 a R0 e coloca o resultado em R2
ADD R1,R1,#1 ; incrementa R1
CMP R1,R2 ; compara R1 a R2, flags posicionados cf R1-R2
TST R1,#0x80000000 ; testa o bit mais significativo de R1
BIC R1,R1,#1 ; zera o bit menos significativo de R1

No próximo post da série vamos ver como acessar dados na memória. Até lá!

sexta-feira, fevereiro 02, 2007

Programação Assembly no ARM - Parte II

Nesta segunda parte vamos começar a falar sobre as instruções do ARM. Todas as instruções do ARM ocupam exatamente um word de 32 bits:

O primeiro ponto a reparar é como a codificação é uniforme em todas as instruções. Isto visa simplificar o hardware de decodificação das instruções e faz parte da filosofia RISC.

Um segundo ponto interessante é o campo Cond que aparece em todas as instruções. Este campo determina como devem estar os flags para a instrução ser executada. Na maioria dos processadores apenas as instruções de desvio dependem dos flags, no ARM todas as instruções são condicionais! A tabela abaixo mostra as condições disponíveis:

O sufixo na tabela acima deve ser acrescentado ao mnemônico da instrução a ser afetada; o sufixo AL pode ser omnitido (e normalmente é). Este sufixo fica obvio no caso de uma instrução de desvio: B (ou BAL) é um desvio incondicional, BEQ é um desvio se igual. As coisas ficam um pouco mais confusas com outras instruções, por exemplo LDREQ é uma instrução de Load Register que só é executado quando o flag Z estiver ligado.

Ainda na codificação das instruções, repare no bit S nas três primeiras linhas. Estas linhas codificam as instruções aritméticas, lógicas e de movimentação. O bit S indica se a instrução vai ou não afetar os flags. No Assembly, isto é feito acrescentando o sufixo S no mnemônico quando se deseja afetar os flags. Por exemplo, uma instrução AND não afeta os flags, mas ANDS afeta (é claro de ANDEQS afeta os flags somente quando for executada, o que só ocorre quando o flag Z está ligado).

E quais são as instruções disponíveis? A figura abaixo tem a lista completa:

Para podermos entender estas instruções é necessário conhecer primeiro como são codificados os operandos, o que veremos no próximo post.

quinta-feira, fevereiro 01, 2007

Programação Assembly no ARM - Parte I

Atualmente é bastante raro eu programar em Assembly. Entretanto, pela segunda vez estou tendo que alterar um módulo de iniciação para um sistema embarcado utilizando um processador com arquitetura ARM. Não sei se é a falta de prática ou as pecularidades do ARM, mas nos dois casos suei muito para fazer as poucas linhas necessárias. Para tentar consolidar o meu aprendizado, resolvi fazer uma pequena serie de posts sobre o assunto.

O que é a arquitetura ARM?

Eu diria que a arquitetura ARM (que já foi chamadado de "Advanced RISC Machine" e "Acorn RISC Machine") é uma especificação dos registradores e instruções de máquina de um processador de 32 bits baseado na filosofia RISC (a Wikipedia tem uma definição mais longa).

Na verdade existem várias versões desta especificação, a que vou tratar aqui é chamada de ARM7TDMI. Esta especificação inclui um modo com instruções de 16 bits (Thumb) que vou ignorar nestes posts. A empresa responsável pelo ARM7TDMI licencia a sua implemantação para inclusão em vários microcontroladores, como os da Atmel e ST Microeletronics.

A descrição do ARM7DMI em formato pdf pode ser encontrada aqui.

São características RISC do ARM:
  • As instruções são todas codificadas da mesma forma, ocupando sempre 32 bits
  • Existem vários registradores e as instruções aceitam qualquer um deles como operando
  • A memória é usada como operando somente para movimentação; operações aritméticas e lógicas usam registradores e constantes como operando
  • A maioria das instruções são executadas em um único ciclo
Uma vez que RISC quer dizer "Computador com Conjunto de Instruções Restrito", muitos esperam que um processador RISC tenha poucas instruções. Na verdade, depende de como se conta as instruções. Existem 34 instruções básicas, porém elas podem ser condicionais e a maioria suporta diversos tipos de operando e modos de endereçamento, gerando um número grande de operações possíveis.

Existem inúmeros Assemblers disponíveis para o ARM, utilizando diversas sintaxes. A sintaxe que eu uso aqui é compatível com o GNU Arm Toolchain.

Os registradores do ARM

O ARM possui 16 registradores de 32 bits, denominados simplesmente de R0 a R15. O registrador R15 é sempre usado como ponteiro para a próxima instrução a executar e pode ser referenciado no Assembly como PC.

A função de chamada de subrotina salva o endereço de retorno no registrador R14, também chamado de link register (LR no Assembly).

O registrador R13 é normalmente usado como ponteiro de pilha (SP no Assembly). Entretanto, ao contrário de outros processadores, este uso é apenas convenção.

Por último, existe um registrador de status e flags, o CPSR, que é acessível apenas por instruções especiais.

No próximo post começaremos a ver as instruções.

Comemoração

Já decidi como vou comemorar o meu aniversário de casamento este ano: lendo o último livro do Harry Potter. Comprei os dois últimos livros na Livraria Cultura, que entregou no dia do lançamento e por preço compatível com o da Amazon. Vamos ver se eles mantem esta tradição.

Agora só falta acertar com a "patroa"...