Análise do Instruction Set Architecture (4) Estrutura de uma função ( / procedimento ) Estrutura do tema ISA do IA-32 1. 2. 3. 4. 5. 6. – função versus procedimento Desenvolvimento de programas no IA-32 em Linux Acesso a operandos e operações Suporte a estruturas de controlo Suporte à invocação/regresso de funções Análise comparativa: IA-32 (CISC) e MIPS (RISC) Acesso e manipulação de dados estruturados AJProença, Sistemas de Computação, UMinho, 2014/15 Suporte a funções e procedimentos no IA-32 (1) 1 • o nome duma função é usado como se fosse uma variável • uma função devolve um valor, um procedimento não – a parte visível ao programador em HLL: • o código do corpo da função • a passagem de parâmetros/argumentos para a função ... ... e o valor devolvido pela função • o alcance das variáveis: locais, externas ou globais – a menos visível em HLL (gestão do contexto da função): • • • • variáveis locais (propriedades) variáveis externas e globais (localização e acesso) parâm’s/argum’s e valor a devolver pela função (propriedades) gestão do contexto (controlo & dados) AJProença, Sistemas de Computação, UMinho, 2014/15 Suporte a funções e procedimentos no IA-32 (2) Análise do contexto de uma função – invocação e regresso visíveis apenas durante a execução da função deve suportar aninhamento e recursividade localização ideal (escalares): em registo, se os houver... localização no código em IA-32: em registo, enquanto houver... • instrução de salto, mas salvaguarda endereço de regresso – em registo (RISC; aninhamento / recursividade ? ) – em memória/na stack (IA-32; aninhamento / recursividade ? ) – variáveis externas e globais: – • externas: valor ou localização expressa na lista de argumentos • globais: localização definida pelo linker & loader (IA-32: na memória) propriedades dos parâmetros/arg’s (só de entrada em C): • por valor (cte ou valor da variável) ou por referência (localização da variável) • designação independente (f. chamadora / f. chamada) • deve suportar aninhamento e recursividade • localização ideal: em registo, se os houver; mas... • localização no código em IA-32: na memória (na stack) – valor a devolver pela função: – – invocação e regresso • instrução de salto para o endereço de regresso – salvaguarda & recuperação de registos (na stack) • função chamadora ? (nenhum/ alguns/ todos ? RISC/IA-32 ? ) • função chamada? (nenhum/ alguns/ todos ? RISC/IA-32 ? ) – gestão do contexto (em stack) • reserva/libertação de espaço para variáveis locais • atualização/recuperação do frame pointer (IA-32... ) • é uma quantidade escalar, do tipo inteiro, real ou apontador • localização: em registo (IA-32: int no registo eax e/ou edx) gestão do contexto (controlo & dados) ... AJProença, Sistemas de Computação, UMinho, 2014/15 Suporte a funções e procedimentos no IA-32 (3) Análise do código de gestão de uma função – propriedades das variáveis locais: • • • • 2 3 AJProença, Sistemas de Computação, UMinho, 2014/15 4 Suporte a funções e procedimentos no IA-32 (4) void swap(int *xp, { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } Análise de exemplos – revisão do exemplo swap • análise das fases: inicialização, corpo, término • análise dos contextos (IA-32) • evolução dos contextos na stack (IA-32) • análise de uma compilação do gcc – aninhamento e recursividade • evolução dos contextos na stack 5 AJProença, Sistemas de Computação, UMinho, 2014/15 Utilização de registos em funções no IA-32/Linux Utilização dos registos (de inteiros) – Três do tipo caller-save Caller-Save! %eax, %edx, %ecx Callee-Save! • save/restore: função chamada %edi – Dois apontadores (para a stack) %esp, %ebp %esi Pointers! • topo da stack, base/referência na stack %esp %ebp swap: pushl %ebp movl %esp,%ebp pushl %ebx movl movl movl movl movl movl 12(%ebp),%ecx 8(%ebp),%edx (%ecx),%eax (%edx),%ebx %eax,(%edx) %ebx,(%ecx) movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret Nota: valor a devolver pela função vai em %eax AJProença, Sistemas de Computação, UMinho, 2014/15 6 Análise das fases em swap, no IA-32 (fig. já apresentada) void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } %edx %ebx – Três do tipo callee-save %ebx, %esi, %edi %eax %ecx • save/restore: função chamadora int *yp) void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } – evolução de um exemplo: Fibonacci AJProença, Sistemas de Computação, UMinho, 2014/15 Designação independente dos parâmetros 7 AJProença, Sistemas de Computação, UMinho, 2014/15 Arranque! Corpo! Término! 8 Análise dos contextos em swap, no IA-32 void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } • em call_swap Construção do contexto na stack, no IA-32 call_swap • na invocação de swap 1. Antes de invocar swap 2. Preparação p/ invocar swap • na execução de swap • no regresso a call_swap • salvaguardar registos? • passagem de parâmetros 3. Invocar swap Que contextos (IA-32)? • passagem de parâmetros • via stack • espaço para variáveis locais • na stack • info de suporte à gestão (stack) • endereço de regresso • apontador para a stack frame • salvaguarda de registos AJProença, Sistemas de Computação, UMinho, 2014/15 9 %esp swap antigo %ebp %esp • atualizar frame pointer • salvaguardar registos ? • reservar espaço p/ var locais %esp 2. Corpo de swap 3. Término de swap ... 1. Antes de invocar swap endereço crescente void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } AJProença, Sistemas de Computação, UMinho, 2014/15 %esp %ebp-4 %ebp frame pointer zip2 stack zip1 antigo %ebp 11 ender. regresso parâmetros p/ swap salv. registos ? • libertar espaço de var locais %esp • recuperar registos ? • recuperar antigo frame pointer • regressar a call_swap frame pointer 4. Terminar invocação de swap... %ebp • libertar espaço com parâmetros na stack • recuperar registos? variáveis locais de call_swap stack antigo %ebp AJProença, Sistemas de Computação, UMinho, 2014/15 10 Evolução da stack, no IA-32 (1) call_swap endereço crescente frame pointer salv. registos ? %esp %ebp • e guardar endereço de regresso 1. Início de swap variáveis locais de swap Evolução da stack, no IA-32 (2) call_swap 2. Preparação p/ invocar swap • salvaguardar registos?...não... • passagem de parâmetros void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } AJProença, Sistemas de Computação, UMinho, 2014/15 %esp %ebp-12 endereço crescente &zip1 &zip2 zip2 frame pointer %ebp stack zip1 antigo %ebp 12 Evolução da stack, no IA-32 (3) call_swap call_swap endereço crescente 2. Preparação p/ invocar swap • salvaguardar registos?...não... • passagem de parâmetros leal pushl leal pushl -8(%ebp),%eax !Calcula &zip2 %eax Empilha &zip2 -4(%ebp),%eax Calcula &zip1 %eax !Empilha &zip1 %esp %ebp-12 3. Invocar swap • e guardar endereço de regresso &zip2 stack call swap %esp %ebp-12 antigo %ebp swap %esp void swap(int *xp, int *yp) %ebp %esp { frame pointer int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } swap: pushl %ebp !Salvaguarda antigo %ebp movl %esp,%ebp !Faz %ebp frame pointer pushl %ebx !Salvaguarda %ebx antigo %ebx endereço crescente antigo %ebp antigo %eip *xp *yp zip2 stack zip1 antigo %ebp AJProença, Sistemas de Computação, UMinho, 2014/15 stack zip1 antigo %ebp AJProença, Sistemas de Computação, UMinho, 2014/15 14 Evolução da stack, no IA-32 (5) 1. Início de swap • atualizar frame pointer • salvaguardar registos • reservar espaço p/ locais...não... &zip2 zip2 !Invoca função swap frame pointer %ebp 13 antigo %eip &zip1 zip1 AJProença, Sistemas de Computação, UMinho, 2014/15 endereço crescente void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } &zip1 zip2 frame pointer %ebp Evolução da stack, no IA-32 (4) Evolução da stack, no IA-32 (6) 2. Corpo de swap swap void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0; } movl movl movl movl movl movl 12(%ebp),%ecx 8(%ebp),%edx (%ecx),%eax (%edx),%ebx %eax,(%edx) %ebx,(%ecx) %esp %ebp frame pointer antigo %ebx antigo %ebp endereço crescente antigo %eip %ebp+8 %ebp+12 Carrega arg yp em ecx Carrega arg xp em edx Coloca y em t1(eax) Coloca x em t0 (ebx) Armazena y em *xp Armazena x em *yp *xp *yp zip2 zip1 stack antigo %ebp antigo %ebp 15 AJProença, Sistemas de Computação, UMinho, 2014/15 16 Evolução da stack, no IA-32 (7) swap %esp 3. Término de swap ... • libertar espaço de var locais...não... • recuperar registos • recuperar antigo frame pointer • regressar a call_swap call_swap antigo %ebx antigo %ebp endereço crescente antigo %eip void swap(int *xp, int *yp) { (…) } 4. Terminar invocação de swap... • libertar espaço de parâmetros na stack... • recuperar registos?...não... void call_swap() { int zip1 = 15213; int zip2 = 91125; (…) swap(&zip1, &zip2); (…) } *xp *yp popl %ebx !Recupera %ebx movl %ebp,%esp !Recupera %esp popl %ebp !Recupera %ebp %ebp ou frame leave Recupera %esp, %ebp pointer ret ! !Regressa à f. chamadora Evolução da stack, no IA-32 (8) zip2 zip1 &zip1 *xp &zip2 *yp %esp stack addl $8,%esp antigo %ebp Atualiza stack pointer frame pointer %ebp AJProença, Sistemas de Computação, UMinho, 2014/15 17 int fib_f(int n) { int i; int val = 1; int nval = 1; do-while do { int t = val + nval; val = nval; nval = t; i++; } while (i<n); int fib_w(int n) { int i = 1; int val = 1; int nval = 1; while } } } } while (i<n) { int t = val + nval; val = nval; nval = t; i++; return val; zip1 antigo %ebp 18 A série de Fibonacci no IA-32 (2) função recursiva (i=1; i<n; i++) { int t = val + nval; val = nval; nval = t; return val; função recursiva _fib_rec: pushl %ebp movl %esp, %ebp subl $12, %esp movl %ebx, -8(%ebp) movl %esi, -4(%ebp) movl 8(%ebp), %esi int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } AJProença, Sistemas de Computação, UMinho, 2014/15 stack int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } for for return val; } zip2 AJProença, Sistemas de Computação, UMinho, 2014/15 A série de Fibonacci no IA-32 (1) int fib_dw(int n) { int i = 0; int val = 0; int nval = 1; endereço crescente 19 AJProença, Sistemas de Computação, UMinho, 2014/15 Atualiza frame pointer Reserva espaço na stack para 3 int's Salvaguarda os 2 reg's que vão ser usados; de notar a forma de usar a stack… 20 A série de Fibonacci no IA-32 (3) A série de Fibonacci no IA-32 (4) função recursiva função recursiva int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } ... movl movl movl cmpl jle leal ... L1: movl %esi, -4(%ebp) 8(%ebp), %esi $1, %eax $2, %esi L1 -2(%esi), %eax int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } ... jle leal movl call movl leal ... Coloca o argumento n em %esi Coloca já o valor a devolver em %eax Compara n:2 Se n<=2, salta para o fim Se não, … -8(%ebp), %ebx AJProença, Sistemas de Computação, UMinho, 2014/15 21 L1 -2(%esi), %eax %eax, (%esp) _fib_rec %eax, %ebx -1(%esi), %eax Se n<=2, salta para o fim Se não, … calcula n-2, e… … coloca-o no topo da stack (argumento) Invoca a função fib_rec e ... … guarda o valor de prev_val em %ebx AJProença, Sistemas de Computação, UMinho, 2014/15 22 A série de Fibonacci no IA-32 (5) função recursiva função recursiva int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } int fib_rec (int n) { int prev_val, val; if (n<=2) return (1); prev_val = fib_rec (n-2); val = fib_rec (n-1); return (prev_val+val); } ... movl leal movl call leal ... %eax, %ebx -1(%esi), %eax %eax, (%esp) _fib_rec (%eax,%ebx), %eax AJProença, Sistemas de Computação, UMinho, 2014/15 A série de Fibonacci no IA-32 (6) Calcula n-1, e… … coloca-o no topo da stack (argumento) Chama de novo a função fib_rec 23 ... call leal L1: movl movl movl popl ret _fib_rec (%eax,%ebx), %eax -8(%ebp), %ebx -4(%ebp), %esi %ebp, %esp %ebp AJProença, Sistemas de Computação, UMinho, 2014/15 Calcula e coloca em %eax o valor a devolver Recupera o valor dos 2 reg's usados Atualiza o valor do stack pointer Recupera o valor anterior do frame pointer 24 Exemplo de cadeia de invocações no IA-32 (2) Exemplo de cadeia de invocações no IA-32 (1) Estrutura do código! yoo(…) { • • who(); • • } Cadeia de Call! yoo who(…) { • • • amI(); • • • amI(); • • • } who Função amI é recursiva amI(…) { • • amI(); • • } amI amI yoo(…) { • • who(); • • } Cadeia de Call! yoo who amI amI stack pointer %esp amI amI amI frame pointer %ebp amI AJProença, Sistemas de Computação, UMinho, 2014/15 25 Cadeia de Call! who amI amI amI amI stack pointer %esp frame pointer %ebp Cadeia de Call! stack pointer %esp yoo who amI amI who frame pointer %ebp amI who amI yoo amI • • • AJProença, Sistemas de Computação, UMinho, 2014/15 26 Exemplo de cadeia de invocações no IA-32 (4) amI(…) { • • amI(); • • } yoo • • • AJProença, Sistemas de Computação, UMinho, 2014/15 Exemplo de cadeia de invocações no IA-32 (3) who(…) { • • • amI(); • • • amI(); • • • } yoo yoo • • • 27 AJProença, Sistemas de Computação, UMinho, 2014/15 28 Exemplo de cadeia de invocações no IA-32 (6) Exemplo de cadeia de invocações no IA-32 (5) amI(…) { • • amI(); • • } Cadeia de Call! yoo frame pointer %ebp who amI stack pointer %esp amI(…) { • • amI(); • • } amI amI amI Cadeia de Call! yoo stack pointer %esp frame pointer %ebp amI amI who amI amI amI who amI who amI yoo amI amI yoo • • • AJProença, Sistemas de Computação, UMinho, 2014/15 29 AJProença, Sistemas de Computação, UMinho, 2014/15 Exemplo de cadeia de invocações no IA-32 (7) amI(…) { • • amI(); • • } Cadeia de Call! yoo frame pointer %ebp who amI stack pointer %esp amI amI Cadeia de Call! stack pointer %esp yoo who amI amI who amI amI yoo amI • • • AJProença, Sistemas de Computação, UMinho, 2014/15 frame pointer %ebp who amI amI 30 Exemplo de cadeia de invocações no IA-32 (8) amI(…) { • • amI(); • • } amI • • • yoo • • • 31 AJProença, Sistemas de Computação, UMinho, 2014/15 32 Exemplo de cadeia de invocações no IA-32 (9) who(…) { • • • amI(); • • • amI(); • • • } Cadeia de Call! amI(…) { • • • • } yoo who amI amI stack pointer %esp frame pointer %ebp amI Exemplo de cadeia de invocações no IA-32 (10) stack pointer %esp yoo who amI amI frame pointer %ebp who who yoo amI • • • AJProença, Sistemas de Computação, UMinho, 2014/15 • • • 33 AJProença, Sistemas de Computação, UMinho, 2014/15 Exemplo de cadeia de invocações no IA-32 (11) who(…) { • • • amI(); • • • amI(); • • • } Cadeia de Call! amI amI amI amI stack pointer %esp frame pointer %ebp Cadeia de Call! yoo who amI amI who amI yoo amI • • • AJProença, Sistemas de Computação, UMinho, 2014/15 35 34 Exemplo de cadeia de invocações no IA-32 (12) yoo(…) { • • who(); • • } yoo who amI amI yoo amI Cadeia de Call! AJProença, Sistemas de Computação, UMinho, 2014/15 stack pointer %esp frame pointer %ebp yoo • • • 36