Pilhas de execução e runtime

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Ambiente de Execução
rotinas que são agregadas ao código gerado para dar suporte à alocação de memória, chamada de procedimentos etc.
*
*
*
Procedimentos - Definições
Definição de um procedimento: nome + corpo.
Uso de um procedimento: chamada
parâmetros (ou argumentos) formais x parâmetros reais (ou argumentos).
*
*
*
Árvores de Ativação
Fluxo de controle é sequencial (em linguagens imperativas/OO).
A execução de um procedimento começa no começo do corpo do procedimento e ao final retorna o controle ao ponto imediatamente depois do ponto em que o procedimento foi chamado.
*
*
*
Árvores de Ativação (cont.)
Ativação de um procedimento = execução de um procedimento
Tempo de vida de uma ativação – sequência de passos do início ao fim do corpo de um procedimento p, incluindo a execução de procedimentos chamados por p.
se a e b são ativações de procedimentos, seus tempos de vida ou não se sobrepõem ou são aninhados.
*
*
*
Árvores de Ativação (cont.)
procedimentos recursivos – uma nova ativação pode ocorrer antes de uma ativação anterior do mesmo procedimento terminar.
recursão não precisa ser direta!
*
*
*
Árvore de Ativação - Exemplo
procedure quicksort (m,n : integer);
var i : integer;
begin
 if (n > m) then begin
 i := partition(m,n);
 quicksort (m,i-1);
 quicksort (i+1,n);
 end;
end;
*
*
*
Árvore de Ativação – Exemplo
s
q(1,9)
p(5,9)
p(1,9)
q(1,3)
p(1,3)
r
q(5,9)
q(1,0)
q(2,3)
q(3,3)
q(2,1)
p(2,3)
q(5,5)
q(7,9)
…
*
*
*
Pilha de Controle
O Fluxo de controle de um programa consiste na travessia em profundidade da árvore de ativação.
Podemos usar uma pilha de controle para acompanhar as ativações de procedimentos “vivas”.
Empilha um nó no inicio da ativação e desempilha quando ela termina.
A pilha indica o caminho até a raiz na árvore de ativação.
*
*
*
Escopo de uma declaração
As regras de escopo de uma linguagem definem que declaração de um nome é usada, quando um nome aparece no texto de um programa.
Escopo local x Escopo não local
*
*
*
Escopo de uma declaração - Exemplo
procedure f (..);
var i : integer;
begin
…i = 10;
end;
procedure g(..);
var i : integer;
begin
… i = 20;
end;
*
*
*
Ligação de nomes (binding)
mesmo se nomes só forem declarados uma vez em um programa, eles podem se referir a objetos de dados (áreas de memória) diferentes durante a execução.
ambiente: mapeamento de nomes com sua localização em uma área de armazenamento
estado: mapeamento entre uma localização em área de armazenamento e o seu valor.
*
*
*
Ligação de nomes (binding)
ambiente
armazenamento
(r-value)
(l-value)
estado
nome
valor
*
*
*
Ligação de nomes (binding)
ambiente e estado são diferentes: atribuição muda o estado, mas não o ambiente.
quando associamos uma localização s a um nome x, dizemos que x está ligado (bound) a s; a associação propriamente dita é a ligação (o binding) de x.
*
*
*
Perguntas a responder
perguntas a responder, que definem aspectos de organização e ligação de nomes em um compilador:
procedimentos podem ser recursivos?
o que acontece com o valor dos nomes locais quando o controle retorna da ativação de um procedimento?
um procedimento pode referenciar nomes não locais?
*
*
*
Perguntas a responder (cont.)
como os parâmetros são passados quando um procedimento é chamado?
procedimentos podem ser passados como parâmetros?
procedimentos podem ser retornados como resultado?
podemos alocar áreas de armazenamento dinamicamente sob controle do programa?
A memória tem que ser desalocada explicitamente?
*
*
*
Organização do Armazenamento
Divisão típica da memória de execução: código, dados estáticos, pilha e heap (armazenamento dinâmico).
Vantagem da alocação estática: endereços são conhecidos em tempo de compilação, possibilitando acesso mais eficiente.
*
*
*
Organização do Armazenamento - pilha
Uso da pilha para armazenar variáveis locais e também para armazenar o estado do programa quando da chamada de procedimentos: valores de registradores, contador do programa etc.
*
*
*
Organização do Armazenamento - heap
Heap é usada para manter dados alocados dinâmicamente. 
Em linguagens em que o tempo de vida de ativações não pode ser representado por uma árvore de ativação usam a heap para guardar informações sobre ativações.
A forma controlada em que dados são alocados e desalocados na pilha tornam o armazenamento de dados na pilha mais eficiente.
*
*
*
Pilha x Heap
Como o tamanho desses estruturas cresce e diminui dinamicamente, normalmente elas são estruturadas de forma a uma crescer em direção à outra.
*
*
*
Registros de Ativação ou frame
empilhado no início da execução de um procesimento e desempilhado ao final.
Alguns campos podem ser substituidos por registradores
*
*
*
Registros de Ativação ou frame
*
*
*
Registros de Ativação
access link – referência para dados não locais, em outros registros de ativação;
control link – ponteiro para o registro de ativação do procedimento que chamou (caller).
*
*
*
Layout de dados locais
tamanho varia de acordo com o tipo dos dados e definições da linguagem e/ou da máquina destino.
pode necessitar de alinhamento (padding em assembler).
Exemplo: tamanhos em C de char, short, int, long, float, double, ponteiros, etc.
*
*
*
Estratégias de alocação de memória
Alocação estática, em tempo de compilação
Alocação na pilha
Alocação na heap
*
*
*
Alocação estática
não necessita de suporte em tempo de execução.
Os nomes estão sempre ligados às mesmas posições de memória.
Valores “persistem” entre chamadas diferentes a procedimentos.
Espaço de memória para variáveis pode ser alocado próximo ao procedimento ou em uma área específica.
*
*
*
Alocação estática - limitações
tamanho dos objetos tem que ser conhecido em tempo de compilação.
Procedimentos recursivos não são permitidos (podem funcionar de forma restrita).
Estruturas de dados não podem ser criadas dinâmicamente.
*
*
*
Alocação na pilha
baseada em uma pilha de controle, com registros de ativação sendo empilhados e desempilhados.
Armazenamento de variáveis locais na pilha (no registro de ativação da chamada).
Valores locais são removidos (perdidos) ao final da ativação.
*
*
*
Sequências de chamada
Sequência de chamada aloca o registro de ativação e preenche algumas informações. 
Sequência de retorno restaura o estado de forma que o procedimento que chamou (caller) o procedimento possa continuar sua execução.
*
*
*
Variações
Sequências de chamada e registros de ativação variam, mesmo em implementações de uma mesma linguagem.
O código da sequência de chamada é normalmente dividido entre o procedimento que chama (o caller) e o que é chamado (callee).
*
*
*
Divisão de tarefas - chamada
caller avalia parâmetros;
caller guarda endereço de retorno e valor de top_sp, e atualiza top_sp;
callee guarda registradores e outras informações de status.
callee inicializa dados locais e começa execução.
*
*
*
Divisão de tarefas - retorno
callee guarda valor de retorno próximo ao registro de ativação do caller.
usando informações do campo de status o callee restaura top_sp e outros registradores e vai para o endereço de retorno do caller.
caller copia valor retornado, se necessário.
*
*
*
Referências perdidas (dangling)
main ()
{ int *p;
 p = dangle();
}
int *dangle()
{ 
 int i = 23;
 return &i;
}
*
*
*
Alocação na heap
necessária quando valores de nomes locais devem ser mantidos após o fim da ativação, ou
uma ativação chamada deve sobreviver ao procedimento chamador (impossível em linguagens em que árvores de ativação representam o fluxo de controle).
Gerenciamento da heap pode ser feito de várias maneiras (e.g. lista encadeada)