Organização do Armazenamento
•
Estática
–
–
•
Variáveis globais;
Fortran;
Dinâmica (pilha e heap)
–
–
Variáveis locais;
Sem aninhamento:
•
•
–
Procedimento acessa somente variáveis locais e globais
C;
Com aninhamento:
•
•
Procedimento pode acessar variáveis não-locais;
Pascal;
Alocação estática
•
•
•
Endereços conhecidos em tempo de compilação,
possibilitando acesso mais eficiente;
Valores “persistem” entre chamadas de
procedimentos (se usada para procedimentos);
Compilador deve conhecer o tipo de cada
variável antes da execução:
–
•
Tipagem estática (PASCAL, JAVA, Haskell, etc.);
Tamanho dos objetos tem que ser conhecido em
tempo de compilação.
–
Retrição de “tipos de tamanho fixo”;
Alocação estática
type Date = record
y: Integer,
m: Integer,
d: Integer
end;
var a: Array 3 of Integer;
var b: Boolean;
var c: Char;
var t: Date;
a[0]
a
a[1]
a[2]
b
c
t.y
t
t.m
t.d
Espaço
não usado
Alocação estática - limitações
•
•
Não suporta procedimentos recursivos;
Estruturas de dados não podem ser
criadas dinamicamente.
Organização do Armazenamento
Pilha (Variáveis Locais)
•
•
Uso da pilha permite variáveis locais;
A pilha também armazena o estado do
programa durante chamadas de
procedimentos: valores de registradores,
contador do programa, computações
intermediárias etc.
Organização do Armazenamento
Pilha (Variáveis Locais)
let
var a: array 3 of integer;
var b: Boolean;
var c: Char;
proc Y () ~
let
var d: Integer;
var e: record c:Char, n:Integer end
in …;
proc Z () ~
let
var f:Integer
in
begin …; Y(); … end
in
begin …; Y(); …; Z(); … end
Organização do Armazenamento
Pilha (Variáveis Locais)
tempo de vida de variáveis globais
tempo de vida de
variáveis locais a Z
tempo de vida
de variáveis
locais a Y
tempo de vida
de variáveis
locais a Y
Programa
chama Y
Programa
inicia
Retorno
de Y
Z chama Y
Programa
chama Z
Retorno
de Y
Programa
pára
Retorno
de Z
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
ST = Stack Top
globals
ST
(1) Depois que o
programa inicia
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
LB = Local Base
globals
LB
frame
for Y
ST
(2) Depois que o
programa
chama Y
Estrutura de um frame
ligação
dados locais
ligação dinâmica
endereço de retorno
SB = Stack Base
LB = Local Base
ST = Stack Top
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
LB
frame
for Y
ST
(2) Depois que o
programa
chama Y
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
ST
(3) Após retorno
de Y
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
LB
frame
for Z
ST
(4) Após programa
chamar Z
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
frame
for Z
LB
frame
for Y
ST
(5) Após Z
chamar Y
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
LB
frame
for Z
ST
(6) Após
retorno de Y
Acessando Varáveis
Locais e Globais (Stack Frames)
SB
globals
ST
(7) Após
retorno de Z
Instruções para acessar variáveis
•
Variáveis globais:
–
–
•
LOAD d [SB]
STORE d [SB]
Variáveis locais:
–
–
LOAD d [LB]
LOAD d [LB]
Instruções para acessar variáveis
• Exemplos:
– LOAD 0 [SB]
• Ler variável global a[0];
– LOAD 4 [SB]
• Ler variável global c;
– LOAD 2 [LB];
• Para procedimento Y ler variávei local d;
– LOAD 4 [LB];
• Para procedimento Y ler variávei local e.n;
– LOAD 2 [LB];
• Para procedimento Z ler variávei local f;
Variáveis não-locais
•
Em linguagens como PASCAL,
procedimentos podem acessar variáveis nãolocais:
–
–
•
Procedimentos aninhados;
Procedimento pode acessar uma variável que não
é local a P mas é local a um procedimento que o
envolve;
Registradores L1, L2, …, Ln:
–
Acesso aos frames de variáveis não-locais;
Organização do Armazenamento
Pilha (Variáveis Locais)
let
var g1: Integer;
var g2: Array 3 of Boolean
proc Q () ~
let
var q: Array 3 of Char
proc R () ~
let
var r: Boolean;
in
begin … end
in
begin … end;
proc S () ~
let
var s: Array 4 of Char;
in
begin … end
in begin … end
Acessando Varáveis
Não- Locais
SB
globals
LB
ST
frame
for P
(1) Depois que o
programa
chama P
Acessando Varáveis
Não- Locais
SB
globals
L1
LB
frame
for P
frame
for Q
ST
(2) Após P
chamar Q
Acessando Varáveis
Não- Locais
SB
globals
LB
ST
frame
for P
(3) Depois de
retornar de Q
Acessando Varáveis
Não- Locais
SB
globals
L1
LB
frame
for P
frame
for S
ST
(4) Após P
chamar S
Acessando Varáveis
Não- Locais
SB
globals
L1
frame
for P
frame
for S
LB
frame
for Q
ST
(5) Após S
chamar Q
Acessando Varáveis
Não- Locais
SB
globals
L2
frame
for P
frame
for S
L1
frame
for Q
LB
ST
frame
for R
(6) Após Q
chamar R
Acessando Varáveis
Não- Locais
SB
globals
L1
frame
for P
frame
for S
LB
frame
for Q
ST
(7) Após retorno
de R
Acessando Varáveis
Não- Locais
SB
globals
L1
LB
frame
for P
frame
for S
ST
(8) Após retorno
de Q
Instruções para acessar variáveis
• Exemplos:
– LOAD d [SB]
• Para procedimento R acessar uma variável global
– LOAD d [LB]
• Para procedimento R acessar uma variável local a ele próprio;
– LOAD d [L1];
• Para procedimento R acessar uma variável local a Q;
– LOAD d [L2];
• Para procedimento R acessar uma variável local a P;
Estrutura Estendida de um frame
ligação estática
ligação
ligação dinâmica
endereço de retorno
dados locais
L1 = content(LB)
L2 = content(content(LB))
L3 = content(content(content(LB)))