Máquinas de Pilha - Introdução
As pilhas LIFO (Last In First Out) são a forma mais simples de guardar temporariamente a informação para tarefas computacionais tão comuns como avaliação de expressões matemáticas e chamada recursiva de subrotinas.
As pilhas LIFO podem ser programadas nos computadores convencionais de várias formas. A mais simples de é reservar um vector em memória e manter uma variável com o índice que indica o topo da pilha.
Existem outras técnicas para criar pilhas em software para além da utilização dum vector. Uma delas é reservar um bloco de posições de memória e manter um ponteiro para o endereço actual do elemento de topo da pilha. Em qualquer um destes casos, efectuar um PUSH de um elemento da pilha corresponde a reservar novo espaço na pilha e colocar um determinado valor nesse novo espaço. Um POP refere-se ao acto de retirar o elemento de topo da pilha e retornar o valor dos dados.
As pilhas são normalmente colocadas nos espaços de endereçamento mais altos da máquina. Normalmente crescem da localização mais alta da memória para a localização mais baixa, permitindo a maior flexibilidade no uso da memória entre o fim da memória do programa e o topo da pilha.
As pilhas são excelentes mecanismos para armazenamento temporário de informação dentro de procedimentos. Permitem invocações recursivas de procedimentos sem o risco de destruir dados de invocações anteriores dessa rotina. Podem, também, ser usadas para passar parâmetros entre procedimentos e, finalmente, permitem poupar espaço de memória possibilitando que diferentes procedimentos usem o mesmo espaço de memória repetidamente para alocação temporária de variáveis, em vez de reservar espaço dentro da memória de cada procedimento para variáveis temporárias.
Uma implementação em hardware duma pilha tem a vantagem óbvia da velocidade em relação à gestão por software. Em máquinas que utilizam pilhas numa larga percentagem de instruções esta superior eficiência é vital para uma melhoria da performance do sistema.
A forma mais comum de implementação em hardware é reservar localizações contíguas de memória com um apontador para essa memória. Normalmente esse ponteiro é um registo de hardware dedicado que pode ser incrementado e decrementado conforme a necessidade de adicionar ou retirar elementos da pilha. Por vezes existe a capacidade de adicionar um deslocamento ao ponteiro da pilha para de uma forma não destrutiva aceder aos primeiros elementos da pilha sem a necessidade de efectuar POPs sucessivos.
A pilha pode estar nos mesmos dispositivos de memória em que se encontra a memória do programa ou num dispositivo dedicado. Uma outra estratégia para a implementação de pilhas em hardware é usar um conjunto de registos, cada um deles constituído por uma longa cadeia de bits, sendo uma das pontas da cadeia visível como um único bit no topo da pilha. 32 destes registos com n bits cada podem ser colocados em paralelo para formar uma pilha de 32 bits. As máquinas de pilha VLSI encontram nesta estratégia uma alternativa viável à forma convencional de um apontador para a memória.
As pilhas, em hardware e software, têm sido usadas para suportar quatro áreas principais na computação: avaliação de expressões matemáticas, armazenamento do endereço de retorno de subrotinas, armazenamento de variáveis locais alocadas dinamicamente e passagem de parâmetros entre subrotinas.
As pilhas de avaliação de expressões foram o primeiro tipo de pilhas a ser largamente suportado por hardware. À medida que um compilador interpreta uma expressão aritmética tem de manter informação sobre os estágios intermédios e precedência de operações. O compilador mantém informação sobre as operações pendentes durante a geração das instruções e o hardware usa apenas uma única pilha de avaliação de expressões para armazenar os resultados temporários. No caso de linguagens interpretadas são mantidas duas pilhas, uma contendo as operações pendentes que aguardam a finalização de operações de maior prioridade e outra contendo os valores de entrada associados a essas operações pendentes.
Para ver como as pilhas se adaptam perfeitamente à avaliação de expressões, consideremos o seguinte exemplo:
X = (A+B) * (C+D)
Em primeiro lugar A e B são somados. Este resultado intermédio tem de ser guardado na pilha de avaliação de expressões. Em seguida C e D são somados e o resultado é também guardado na pilha. Finalmente os dois elementos do topo da pilha, (A+B) e (C+D), são multiplicados e o resultado é armazenado em X. A pilha de avaliação de expressões proporciona uma gestão automática de resultados intermédios e expressões, permitindo tantos níveis de precedência quantos os elementos da pilha. Quem já usou as calculadoras da HP já experimentou directamente uma pilha de avaliação de expressões.
O uso de uma pilha para avaliação de expressões é tão básico que mesmo os compiladores de máquinas baseadas em registos muitas vezes alocam os registos como se formassem uma pilha de avaliação de expressões.
Com a introdução da recursividade como uma característica das linguagens de programação surgiu a necessidade de guardar o endereço de retorno duma subrotina, de forma a que uma rotina se pudesse chamar a ela própria ou invocar outras rotinas. Uma possível solução para este problema é usar uma pilha para armazenar o endereço de retorno. À medida que cada subrotina é chamada é guardado o endereço de retorno do programa que chamou essa subrotina numa pilha. Isto assegura que os retornos das subrotinas são processados pela ordem inversa das chamadas às subrotinas. Como os novos elementos são colocados na pilha a cada chamada, rotinas recursivas podem chamar-se a elas próprias sem nenhum problema.
Outro problema que surge quando se usa recursividade, e especialmente reentrância (a possibilidade de usos múltiplos do mesmo código por diferentes linhas de controlo), é a gestão de variáveis locais.
Ao permitir que uma rotina seja usada por diferentes linhas de controlo simultânea ou recursivamente é praticamente impossível gerir com eficácia variáveis locais definidas estaticamente dentro dos procedimentos. Os valores de variáveis de uma linha de execução podem corromper facilmente os valores de outra linha de execução concorrente.
A solução normalmente usada é reservar o espaço numa pilha de variáveis locais. Novos blocos de memória são alocados nesta pilha a cada chamada de uma subrotina, criando espaço de armazenamento para a subrotina. Mesmo que sejam apenas usados registos para armazenar valores temporários dentro de uma subrotina, um qualquer tipo de pilha de variáveis locais é necessário para guardar os valores dos registos da rotina que chama, antes de serem destruídos com a chamada de uma nova rotina.
A pilha de variáveis locais permite também poupar memória. Em subrotinas com variáveis locais alocadas estaticamente, as variáveis ocupam espaço quer a subrotina esteja ou não activa. Com uma pilha de variáveis locais o espaço na pilha é reaproveitado à medida que as subrotinas são chamadas e a profundidade da pilha aumenta e diminui conforme o necessário.
Quando uma subrotina é chamada precisa normalmente de um conjunto de valores de entrada. Esses valores podem ser passados através de registos, com a desvantagem de limitar o número de parâmetros possíveis. Estes parâmetros também podem ser passados por cópia ou usando um ponteiro para esses elementos numa lista na memória da rotina que chama.
O método mais flexível é copiar os valores para uma pilha de parâmetros antes de efectuar uma chamada a um procedimento. Esta pilha permite reentrância e recursividade nos programas.
Os tipos de pilhas descritos acima são combinados nos processadores. É comum ver numa máquina baseada em registos a pilha de variáveis locais, pilha de parâmetros e pilha de endereços de retorno combinadas numa única pilha. Nestas máquinas as pilhas de avaliação de expressões são eliminadas pelo compilador, usando registos para efectuar a avaliação das expressões.
A abordagem seguida pelas máquinas de pilha consiste em ter hardware separado de avaliação de expressões e endereços de retorno. A pilha de avaliação de expressões também é usada para passagem de parâmetros e armazenamento de variáveis locais.
As máquinas de pilha podem ser caracterizadas pelo número de pilhas suportadas pelo hardware, pelo tamanho do buffer dedicado aos elementos da pilha e pelo número de operandos permitidos pelo formato das instruções.
Cada um destes factores pode tomar os seguintes valores:
Quando existe apenas uma única pilha esta é normalmente usada para guardar o estado actual nas chamadas a subrotinas e interrupções. Também pode ser usada para avaliação de expressões. Em qualquer dos casos é provavelmente usada para passagem de parâmetros entre subrotinas pelos compiladores de algumas linguagens. Normalmente uma única pilha leva a hardware simples mas com o custo de misturar dados com endereços de retorno.
Uma vantagem de ter apenas uma pilha é que é mais fácil para um sistema operativo gerir apenas um bloco de memória de tamanho variável por processo. No entanto, os parâmetros e os endereços de retorno são forçados a coexistir no mesmo espaço de memória.
Computadores com múltiplas pilhas têm duas ou mais pilhas suportadas pelo conjunto de instruções. Uma pilha é normalmente usada para guardar os endereços de retorno. As restantes são usadas para avaliação de expressões e passagem de parâmetros entre subrotinas. Várias pilhas permitem manter o controlo do fluxo de informação separado da própria informação. No caso em que a pilha de parâmetros está separada da pilha de endereços de retorno o software pode passar um conjunto de parâmetros através de várias camadas de subrotinas sem o custo de copiar os dados para novas listas de parâmetros.
Uma importante vantagem do uso de várias pilhas é a velocidade. Várias pilhas permitem o acesso a múltiplos valores num ciclo de relógio. Uma máquina que possa aceder simultaneamente à pilha de dados e à pilha de endereços de retorno pode efectuar chamadas e retornos de subrotinas em paralelo com operações de dados.
As estratégias de implementação variam desde usar apenas memória do programa para armazenar os elementos da pilha, ter alguns registos que guardam o topo da pilha a ter uma unidade de memória para a pilha completamente separada.
Uma arquitectura com um buffer pequeno, vê tipicamente a pilha como uma porção reservada do espaço da memória do programa. As pilhas usam o mesmo espaço de memória das instruções e variáveis, permitindo que as instruções normais de referência da memória acedam aos elementos da pilha. Estes elementos podem também ser endereçados através de um deslocamento a partir dum ponteiro para a memória.
O facto de um buffer deste tipo ser simples de implementar e gerir tornou-o bastante popular. Como a maioria dos elementos da pilha residem na memória principal a gestão de ponteiros, strings e outras estruturas de dados é bastante simples. A desvantagem desta abordagem é que uma largura de banda significativa é consumida para ler e escrever elementos na pilha.
Se uma arquitectura tem um buffer suficientemente largo para que a largura de banda da memória não seja consumida ao aceder aos elementos da pilha, então estamos perante uma arquitectura com buffer largo. Este buffer pode ser implementado de várias formas: pode ser um grande conjunto de registos acedido por um esquema de janela, uma unidade de memória que está isolada do programa ou uma unidade de memória cache dedicada no processador.
Uma vantagem de possuir um buffer largo é que não são consumidos ciclos de relógio para aceder aos dados e endereços de retorno das subrotinas. Isto pode levar a melhorias significativas no desempenho, especialmente em ambientes com uso intensivo de subrotinas. Mas, uma desvantagem de possuir uma unidade de memória separada para a pilha é que esta pode não ser suficiente para todas as aplicações. Neste caso pode ser necessário colocar os dados na memória do programa para possibilitar novas entradas na stack. Guardar todo o buffer quando se alterna entre tarefas num ambiente multi-tarefa pode impor um overhead inaceitável na mudança de contexto. Este problema pode ser evitado através da divisão da memória da pilha em áreas separadas para diferentes tarefas.
O número de operandos no formato das instruções tem um tremendo impacto na forma como as pilhas são construídas em hardware e na forma como podem ser usadas pelos programas.
Instruções com 0 operandos não permitem que qualquer operando esteja
associado ao opcode da instrução. Todas as operações são
implicitamente realizadas com os elementos de topo das pilhas. Este modo de
endereçamento é muitas vezes chamado de endereçamento puro da pilha. Uma
arquitectura de 0 operandos tem necessariamente de usar uma das suas pilhas para
avaliação de expressões.
Mesmo numa máquina de pilha pura têm de existir instruções que especifiquem
endereços para ler ou guardar variáveis na memória, ler valores constantes,
chamada a subrotinas e instruções de salto condicionais. Estas instruções
têm um formato muito simples, normalmente usando apenas o endereço de memória
a seguir ao opcode da instrução para guardar o operando.
Existem diversas vantagens na simplicidade das instruções com 0 operandos. A primeira é que apenas o topo de uma ou duas pilhas pode ser referenciado por uma instrução. Isto simplifica a construção da pilha permitindo o uso com uma única entrada com 1 ou 2 registos de topo da pilha. A segunda é que é possível obter ganhos de velocidade lendo os operandos em paralelo com a descodificação da instrução, uma vez que os operandos para cada instrução são conhecidos antecipadamente como sendo os elementos de topo da pilha. Isto pode eliminar completamente a necessidade de pipelining para obter e guardar os operandos. Finalmente, é que as instruções podem ser extremamente compactas, sendo um formato de instruções de 8 bits suficiente para 256 opcodes diferentes. A descodificação das instruções é simplificada uma vez que o hardware de descodificação não tem a necessidade de interpretar modos de endereçamento.
Uma desvantagem do modo de endereçamento com 0 operandos é que modos de endereçamento complexos para acesso a estruturas de dados pode necessitar de várias instruções, assim como elementos que estejam armazenados no fundo da pilha podem ser difíceis de aceder se não existir um mecanismo para copiar o elemento de profundidade N para o topo da pilha.
Uma máquina com um formato de instruções com 1 operando normalmente realiza operações com o operando especificado e usa implicitamente o topo da pilha como o segundo operando. Este modo de endereçamento, também chamado de pilha/acumulador, oferece maior flexibilidade que o endereçamento com 0 operandos, uma vez que combina a obtenção de um operando com a operação na pilha. No entanto, como o operando é especificado pela instrução, uma implementação eficiente tem de incorporar uma pipeline para obtenção de parâmetros ou possuir um maior ciclo de relógio para permitir que o operando seja obtido.
Quando o operando está na pilha de parâmetros de uma subrotina ou na pilha de avaliação de expressões, a memória da pilha tem de ser acedida com o deslocamento indicado pelo operando para obter o elemento da pilha. Isto requer um maior tempo de execução ou mais hardware de pipelining do que ter os elementos de topo da pilha à espera de uma instrução.
Uma arquitectura com 1 operando normalmente possui uma pilha de avaliação de expressões. A maioria destas arquitecturas permite o endereçamento com 0 operandos quando o operando não é usado.
Formatos de instruções com 2 ou 3 operandos permitem que cada instrução especifique tanto a fonte como o destino. No caso em que as pilhas apenas são usadas para guardar os endereços de retorno, normalmente estamos em presença de uma máquina baseada em registos. Se os parâmetros de uma subrotina são passados para a pilha, então os operandos podem especificar um deslocamento em relação ao ponteiro da pilha ou um par de registos para a operação. Estas máquinas não necessitam duma pilha de avaliação de expressões, mas colocam no compilador a tarefa de obter os resultados intermédios das expressões avaliadas.
Estas arquitecturas com 2 ou 3 operandos oferecem um máximo de flexibilidade mas exigem hardware mais complexo para um mesmo nível de performance. Como os operandos não são conhecidos antes da instrução ser descodificada, uma pipeline de dados e memória de duas entradas têm de ser usadas para fornecer operandos à unidade de execução.