Arquitectura de Computadores

Notas de estudo

Alberto José Proença

1999/00

Índice geral

1. Organização e arquitectura dum computador
2. Análise do funcionamento do CPU dum computador
3. Mecanismos para execução de programas
4. Modelo de programação dum processador
5. Metodologia de construção de programas em assembly

1. Instruções para transferência de informação
2. Operações aritméticas e lógicas
3. Instruções para controlo de fluxo
4. Implementação de estruturas de controlo de HLL
5. Suporte à invocação de procedimentos/funções
6. Passos a seguir na construção de um programa em assembly
7. Sub-conjunto de instruções do MIPS

No capítulo anterior apresentou-se uma visão genérica do que deveria estar presente no instruction set dum processador central RISC; neste capítulo vai-se analisar com detalhe cada tipo de instruções numa dada arquitectura (MIPS): instruções para transferência de informação, operações aritméticas (apenas com inteiros), operações lógicas (incluindo as instruções de comparação e de deslocamento de bits), instruções para controlo de fluxo e instruções para de invocação e retorno de sub-rotinas.

Uma vez completada a análise detalhada do instruction set de uma arquitectura (RISC), apresentam-se algumas técnicas de implementação de estruturas de controlo de HLL e de suporte à invocação de procedimentos e/ou funções, completada posteriormente com a sequência dos passos a seguir na construção de um programa em assembly duma arquitectura com processador RISC de uso generalizado (general purpose).

A última página deste capítulo contém uma tabela com um sub-conjunto representativo de instruções do MIPS. O assunto deste capítulo é tratado com detalhe no texto de apoio (ver 3.1 a 3.6, 3.10 e A.10).

1. Instruções para transferência de informação

Este conjunto de instruções inclui as operações de transferência de informação entre registos e a memória e entre registos.

• Instruções de load/store

Este tipo de instruções permite transferir (copiar) o conteúdo duma posição da memória para um registo (load), ou vice-versa (store). Nestas operações há que atender:

- ao modo de endereçamento à memória; as arquitecturas RISC suportam um leque muito estreito de modos de endereçamento à memória para acesso a operandos e, no caso do MIPS, apenas um modo é suportado: a posição de memória que se pretende aceder é especificada na instrução por 2 componentes, sendo um o conteúdo dum registo (que se especifica) e o outro um valor de 16 bits (valor presente no formato de instrução, imediato); a posição da memória é calculada adicionando estes 2 valores;

- ao tamanho dos operandos; o MIPS suporta a transferência de operandos de 8 bits (byte - lb/sb), de meias-palavras de 16 bits (half-word - lh/sh), e de palavras de 32 bits (word - lw/sw); o assembler suporta ainda instruções para transferência de duplas-palavras, 64 bits (ld/sd) convertendo-as depois para um par de instruções que seleccionam o registo especificado e o registo seguinte;

- extensão que contemple o sinal do operando; na transferência de quantidades de 8 e de 16 bits para um registo (normalmente colocados nos bits menos significativos do registo) há que especificar ainda como preencher os restantes bits do registo: se os encher a zero, ou se se tentar preservar o sinal no caso de inteiros em complemento para 2 (isto é, preencher os restantes bits iguais ao bit do sinal do valor de 8 ou 16 bits); por defeto o MIPS considera a extensão ao sinal; se o programador pretender encher o resto do registo com zeros, deve indicar na instrução que a quantidade a transferir é um valor sem sinal (unsigned);

- a utilização de instruções com funções idênticas para manuseamento dos registos de até 4 co-processadores: lwcz/swcz, sendo z um valor entre 0 e 3.

Incluem-se ainda nesta categoria as instruções que permitem introduzir uma constante (valor imediato) num registo ou numa posição de memória. Nem o MIPS nem o seu assembler suportam este tipo de instruções em que o destino é a memória; esta acção consegue-se carregando primeiro para um registo o valor e depois transferindo o conteúdo desse registo para a posição de memória pretendida. Quanto a introduzir uma constante num registo, o MIPS tem ainda uma limitação resultante dos formatos de instrução suportados: apenas suporta valores de 16 bits. Embora o assembler do MIPS suporte uma instrução que coloca num registo um endereço de 32 bits (la), o instruction set do MIPS não inclui tal instrução. Assim para carregar um valor de 32 bits é preciso fazê-lo em 2 passos: primeiro carrega o valor superior (upper) para um registo (lui), colocando a zero os 16 bits menos significativos; depois carrega os restantes bits (o MIPS não possui instrução específica para esta tarefa; usa-se normalmente ori, pois esta instrução opera com os 16 bits do campo imediato, estendendo para 32 bits com zeros, o que nem sempre acontece com a operação aparentemente equivalente de addui).

• Instruções de move

Este tipo de instruções de instruções designa normalmente a transferência entre registos. No caso do MIPS há a considerar os seguintes tipos de registos:

- registos genéricos: o assembler suporta uma instrução de move que transfere a informação do registo fonte para o destino, mas o instructions set não contém tal instrução; ela é implementada no MIPS usando uma adição do registo fonte com o registo zero (só de leitura, contendo sempre o valor 0) e colocando o resultado no registo destino;

- entre registos genéricos e os registos hi e lo: instruções para transferir de (from) - mfhi, mflo - e para transferir para (to) - mthi, mtlo;

- entre registos genéricos e registos dos co-processadores: instruções para transferir de/para - mfcz, mtcz.

• Resumo das instruções mais relevantes desta secção

2. Operações aritméticas e lógicas

Nesta secção apenas serão apresentados os aspectos indispensáveis à utilização destas instruções. Mais adiante se verão outros aspectos relacionados com a computação aritmética.

• Instruções de add, sub, mul, div

As instruções aritméticas no MIPS incluem a soma, subtracção, multiplicação e divisão. À semelhança do que acontece em qualquer outra arquitectura RISC, os operandos deverão estar sempre em registos e os resultados deverão ser armazenados de novo em registos. Como registos fonte poderão ser seleccionados quaisquer dos 32 registos genéricos ou ainda os 16 bits menos significativos do registo de instrução (valor imediato, a especificar explicitamente no formato de instrução, com o bit do sinal estendido aos 32 bits).

A multiplicação e divisão ainda usam implicitamente os registos hi e lo: o resultado duma multiplicação (64 bits) é colocado nos registos hi (32 bits mais significativos) e lo (32 bits menos significativos), enquanto numa divisão o resto é colocado em hi e o quociente em lo.

• Instruções de and, or, nor, xor

Tal como as instruções aritméticas, também estas operações lógicas têm os operandos e resultados em registos (incluindo o valor imediato, de 16 bits, no registo de instrução, estendido a zero; excepção: nor).

• Instruções de comparação

O MIPS disponibiliza um conjunto de instruções que permitem comparar 2 valores - quer em 2 registos especificados, quer num registo especificado e um valor imediato de 16 bits - e que coloca o resultado da comparação num outro registo, também especificado na instrução. Apenas um tipo de comparação é suportado pelo MIPS: menor do que, less than. Se o resultado da comparação for verdadeiro, o MIPS coloca a 1 (set) o registo destino; caso contrário, coloca a zero. A comparação pode ainda ser feita considerando os conteúdos como sendo inteiros com sinal, ou simplesmente binários sem sinal (unsigned).

As 4 instruções resultantes destas combinações são: slt, sltu, slti, slti.Todos os outros tipos de comparação poderão ser implementados à custa destas 4 instruções, e o assembler suporta alguns desses tipos: seq, sne, sgt, sge, sle.

• Instruções de deslocamento de bits

O instruction set do MIPS inclui ainda um conjunto de instruções que permitem deslocar para a esquerda ou direita o conteúdo dum registo de vários bits, tratando esse conteúdo como se fosse apenas um valor binário (deslocamento lógico, sll, srl) ou um valor aritmético com sinal (deslocamento aritmético, sra). Se o nº de bits a deslocar não for conhecido durante a compilação, i.e., se for um valor variável, então é possível especificar um registo que contenha essa variável (sllv, srlv, srav). Este tema será tratado de novo quando se tratar da computação aritmética.

• Resumo das instruções mais relevantes desta secção

3. Instruções para controlo de fluxo

De acordo com o modelo de execução de instruções de um computador, o CPU vai buscar a instrução à memória colocando-a no registo de instrução, incrementa o PC de modo a ficar a apontar para a próxima instrução, e descodifica e executa a instrução. Se a instrução não afectar o registo PC, então o programa é executado sequencialmente, isto é, instrução após instrução em endereços consecutivos de memória. A alteração desta execução sequencial de instruções pode ser feita alterando o registo de PC, quer de modo incondicional, quer após o teste com sucesso de uma condição definida.

• Instruções de salto incondicional

As instruções de salto incondicional no MIPS têm o mesmo tamanho que as outras, i.e., 32 bits; a especificação do endereço duma célula no MIPS também requer 32 bits. Dado que é necessário especificar no formato da instrução a operação que o CPU vai executar, as instruções (no MIPS) de salto incondicional para um endereço definido de modo absoluto (j ), usam o formato J de instrução: os 6 bits mais à esquerda especificam a operação, e os restantes 26 bits são parte dum endereço. Ficam por definir 6 bits!

As instruções de salto no MIPS são para um endereço de memória contendo uma instrução. Uma vez que estas ocupam sempre 4 células (4 bytes, 32 bits), é conveniente alinhar na memória as instruções, com endereços múltiplos de 4; assim os 2 bits menos significativos do endereço serão sempre 0, não havendo necessidade de os especificar no formato de instrução. Ficam ainda por definir 4 bits!

No MIPS, os 4 bits mais significativos do endereço de salto incondicional coincidem com os 4 bits mais significativos do registo de PC. Isto significa que se torna necessário ter cuidado sempre que existem saltos que passem a fronteira dos 256M (isto é, 2 levantado a 28), e substituí-los por outra instrução que ultrapasse esta limitação: a instrução que salta para o endereço especificado num registo (jr ).

• Instruções de salto condicional

No caso das instruções condicionais, o MIPS apenas suporta instruções que saltem para um endereço especificado de modo relativo ao valor existente no PC: o endereço final vem dado pela soma do valor existente no PC - que está a apontar para a próxima instrução a ser executada - com o valor especificado na instrução - positivo ou negativo, consoante se trate de uma salto para trás ou para diante - e adaptado à dimensão da célula - isto é, o valor especificado indica a distância de salto em nº de instruções, e não em nº de células de memória, sendo este valor 4 vezes maior.

As instruções de salto condicional são normalmente constituídas por 3 partes: começam por efectuar uma comparação, seleccionam uma condição e, consoante a condição se verifica ou não, saltam para o endereço especificado.

O MIPS suporta 2 tipos de comparação: entre dois registos especificados na instrução, ou entre um registo especificado na instrução e o valor 0.

Quando a comparação é feita entre 2 registos, as 2 únicas condições que o instruction set suporta é o serem iguais ou diferentes: beq, bne. Caso haja necessidade de se testarem outras condições, estas situações são implementadas no MIPS com a ajuda da operação lógica slt.

Quando a comparação é entre um registo e o valor 0, o MIPS suporta as 4 condições "<", "<=", ">", ">=": bltz, blez, bgtz, bgez.

A especificação da nova localização de memória para onde a execução do programa vai continuar caso a condição seja satisfeita, é feita indicando a distância de salto em nº de instruções. Dado que é comum escrever-se programas em assembly usando pseudo-instruções, não se aconselha a utilização de valores numéricos na especificação destas distâncias de salto. É de toda a conveniência a utilização de etiquetas (labels) a anteceder a instrução destino para os saltos, e usar essas etiquetas nas instruções de salto; assim o assembler tomará em consideração as eventuais alterações nessa distância, devido às trocas de algumas pseudo-instruções por 2 ou mais instruções de linguagem máquina.

• Instruções de salto com atraso na execução

Uma das características presentes em todas as implementações de arquitecturas RISC é a sua estrutura interna de funcionamento trabalhar de modo encadeado, i.e. em pipeline. Para minimizar o impacto negativo das instruções de salto neste tipo de organização interna, a maioria das arquitecturas executa sempre a instrução que se encontra na posição de memória logo a seguir à instrução de salto, e só depois é que o salto é executado. Nestas arquitecturas é também comum ser o próprio assembler a encarregar-se de colocar nesse local uma instrução apropriada, libertando o programador em assembly de tal preocupação. É o que se passa também com o MIPS.

• Instruções para invocação/retorno de rotinas

Todas as instruções de salto que foram já analisadas eram instruções apenas "de ida", isto é, não salvaguardavam o conteúdo do registo PC, de modo que não era possível regressar ao ponto de partida. Este tipo de situação apenas ocorre quando se invoca um procedimento ou função (também designado por rotina ou sub-rotina, em assembly), onde é necessário guardar o valor do PC para que, no fim da rotina, se possa regressar ao ponto do programa onde se invocou a rotina.

Todos os processadores dispõem de instruções de salto "de ida e volta", normalmente designados de instruções de chamada de sub-rotinas: nestas, para além de se alterar o conteúdo do registo PC como qualquer instrução de salto, primeiro guarda-se o endereço da instrução que segue a instrução de salto (e que se encontra no PC); nas arquitecturas CISC este valor é normalmente guardado na stack; nas arquitecturas RISC esse valor é normalmente guardado num registo.

A instrução que no MIPS implementa este "salto e ligação" é o jal, a qual guarda o endereço de retorno no registo 31 ($ra) e salta para o endereço especificado de modo absoluto (equivalente ao salto incondicional). À semelhança do que já acontecia com os saltos incondicionais, o MIPS também suporta uma instrução de "salto e ligação" para um endereço de salto especificado num registo, jalr, podendo ainda nesta instrução especificar-se qual o registo onde será salvaguardado o endereço de retorno (se não for indicado nenhum, o registo $ra será seleccionado por defeito).

O MIPS suporta ainda 2 instruções condicionais (comparação com 0) para a invocação de uma sub-rotina: seleccionando a condição "<" (bltzal) ou a condição "<=" (bgezal).

Para a instrução de retorno da rotina, basta fazer um salto para o endereço especificado em $ra (jr).

• Resumo das instruções mais relevantes desta secção

* especificado no campo rt

• Formatos das instruções e exemplos

4. Implementação de estruturas de controlo de HLL

As instruções de salto disponíveis em linguagem máquina foram concebidas tendo em vista um suporte eficiente às estruturas de controlo presentes nas linguagens HLL, e o MIPS não foge à regra. A secção 3.5 do texto de apoio, cheia de exemplos, descreve com clareza estes casos, em complemento dos exemplos apresentados na aula: estruturas de if <cond> then ... else..., ciclos for, ciclos while.

5. Suporte à invocação de procedimentos/funções

 Na invocação de procedimentos e funções existem 3 aspectos que são relevantes: as instruções para a invocação e retorno de rotinas (analisadas no capítulo anterior), o método de passar os parâmetros, e a alocação de registos a variáveis locais, preservando o valor das variáveis que lá tinham sido previamente alocadas.

• Passagem de parâmetros

O método mais eficiente de se passarem parâmetros para uma sub-rotina é utilizando registos. A mesma norma que se convencionou usar para a utilização dos registos do MIPS contempla esta situação:

- $a0 a $a3: os primeiros 4 argumentos (parâmetros) a passar para uma sub-rotina; os restantes são passados pela stack; correspondem (por convenção) aos registos $4 a $7;

- $v0 e $v1: valor de retorno de funções (podem ainda ser usados no cálculo de expressões); correspondem (por convenção) aos registos $2 e $3.

• Preservação do conteúdo dos registos

Numa arquitectura com apenas um banco de registos (caso do MIPS), quando uma rotina - com variáveis ou outros valores armazenados em registos - invoca outra - que também vai precisar de registos para o código que vai executar - torna-se necessário salvaguardar o conteúdo desses registos em memória (na stack), e recuperá-los posteriormente. A responsabilidade dessas tarefas poderá estar com a rotina que invoca ou com a rotina invocada.

Quando a responsabilidade está com a rotina que invoca, ela vai salvaguardar todos os registos que contêm valores que poderão ser precisos posteriormente, mesmo que a rotina invocada não os altere, recuperando-os depois do regresso da rotina. Situação de idêntico desperdício irá ocorrer se essa responsabilidade estiver toda a cargo da rotina invocada: ela irá salvaguardar previamente todos os registos que usar, mesmo que eles não estejam a ser utilizados pela rotina que a invocou, e recuperá-los no fim antes do retorno.

Para minimizar estes desperdícios, a convenção adoptada para a utilização dos registos do MIPS aloca 8 registos cuja responsabilidade de salvaguarda e recuperação pertence à rotina que invoca - são os registos temporários, $tn - e outros 8 registos cuja responsabilidade de salvaguarda e recuperação pertence à rotina invocada - são os registos seguros, $sn.

Para além destes registos, há ainda a eventual necessidade de uma rotina invocada salvaguardar/ recuperar o registo de retorno de sub-rotina ($ra) e registos de argumentos: sempre que a rotina invocada possa chamar outra rotina, quer por aninhamento, quer por recursividade.

6. Passos a seguir na construção de um programa em assembly

A construção de programas em assembly é uma acção a tomar só em último recurso! Com a evolução da arquitectura interna dos actuais processadores (com vários níveis de paralelismo interno) e dos respectivos compiladores, é já muito difícil escrever código máquina mais eficiente que o gerado por um bom compilador.

Contudo, para uma melhor compreensão do funcionamento dum computador, é conveniente que qualquer programador em ambiente de HLL tenha consciência de como o seu programa irá ser executado pelo processador. Esta compreensão vai permitir-lhe tomar as decisões mais adequadas em termos de optimização da performance; mas para isso terá que fazer um pouco de "compilação à mão". Esta aprendizagem irá também auxiliá-lo a construir as melhores especificações dos problemas a resolver, recorrendo a linguagens de mais alto nível sempre que possível.

No processo de conversão de uma especificação de alto nível (usando por exemplo uma linguagem HLL, como o C), um compilador toma normalmente os seguintes passos:

- alocação de registos às variáveis do programa: de acordo com a convenção de utilização dos registos do MIPS (descrito em aulas anteriores, e representado na fig. A.9), os primeiros 4 argumentos (parâmetros) são passados pelos registos $a0 a $a3, o valor de retorno das funções usa os registos $v0 e $v1, as variáveis locais vão usar os registos $s0 a $s7, e os registos usados em cálculos temporários vão usar os registos $t0 a $t9; as variáveis que não puderem ser alocadas a registos irão ocupar uma área definida na memória (e cujo endereço do início o compilador irá colocar em $gp);

- codificação do corpo do procedimento: uma vez feita a alocação das variáveis do programa constrói-se então o código em assembly ou em linguagem máquina que implemente o conjunto de acções a executar pelo programa;

- preservação dos registos: a convenção de utilização dos registos do MIPS prevê qual o conjunto de regisots que deverão ser preservados pelo procedimento que invoca e pelo procedimento invocado; em qualquer dos casos os registos são normalmente salvaguardados no início do código do procedimento - quer os registos contendo variáveis, quer ainda os relacionados com a invocação do procedimento, contendo os argumentos e o endereço de retorno - e o seu valor é posteriormente recuperado antes de abandonar o procedimento.

O exemplo apresentado no texto de apoio (swap, ver 3.10) introduz gradualmente estes passos, e a 2ª edição do livro usa já a convenção de utilização dos registos do MIPS (em vez da usar a designação numérica dos registos, conforme era apresentado na 1ª edição do livro, que tinhacomo consequência código mais extenso, i.e., com mais 4 instruções). O código resultante com a utilização da convenção está na fig. 3.24.

Um exemplo mais complexo é detalhado no resto desta secção do texto de apoio (sort, ver 3.10), contendo 2 ciclos aninhados e uma invocação do procedimento swap, já visto anteriormente. Este exemplo vai requerer maior cuidado na preservação de registos, por conter uma invocação dum outro procedimento.

7. Sub-conjunto de instruções do MIPS

* especificado no campo rt