Instruções Básicas A Linguagem Maquina

5/10/2018 Instru es B sicas A Linguagem Maquina

1/69

lnstrucoes Basfcas: A Linguagemda MaquinaCom Deus falo espanhol; com as mulheres, italiano; com os homens, frances; e, commeu cavalo, alemdo.Carlos v, rei de Frant;a1337-1380

3.1 tntroducao3.2 Operacoes Executadas pelo Hardware da

Maquina3.3 Operandos do Hardware da Maquina3.4 Representac;ao de lnstrucoes3.5 lnstrueoes de Desvio3.6 Suporte a Procedirnentos pelo Hardware da

Maquina3.7 Alern dos Numeros3.8 Outros Estilos de Enderec;arnento no MIPS

3.9 Execuc;ao de urn Programa3.10 Urn Exernplo para Juntar as Pecas3.11 Arrays versus Ponteiros3.12 Casos Reais: lnstrucdes do PowerPC e do 80x863.13 lendas e Falhas3.14 consideracoes Finais3.15 Perspectiva Historica e leituras

Cornplernentares3.16 Terrnos-Chave3.17 Exercfcios

Os Cinco Componentes Classicos de um Computador

Avaliacao daperformance


2/69

3.1 lntroducaoPara comandar 0hardware de urn computador, voce precisa fa-lar a linguagem dele. As palavras da Iinguagem da maquina saochamadas de instrucoes, e seu vocabulario e chamado de con-junto de instrucoes. Neste capitulo, vamos estudar 0conjunto deinstrucoes de uma maquina real, considerando tanto a maneiracomo n6s humanos codificamos as instrucoes dessa linguagemquanta 0modo como as maquinas entendem as instrucoes quelhes sao passadas. A estrategia para estudo da linguagem demaquina e comecar com uma notacao semelhante a de uma lin-guagem de programacao, porem com muitas limitacoes, e ir re-finando essa linguagem passo a pas so, ate chegar a linguagemque a maquina efetivamente entende. *Voce tern todo 0direito de pensar que as linguagens entendi-das pelas maquinas sao muito diferentes umas das outras, a exem-plo do que ocorre com os idiomas usados por n6s humanos, mas,na verdade, elas sao muito semelhantes, mais parecendo diale-tos regionais do que lfnguas independentes. Portanto, depois quevoce aprende a linguagem de maquina de determinado proces-sador, toma-se muito facil aprender outras mais. A justificativapara essa semelhanca e 0 fato de os processadores serem todosconstrufdos a partir das mesmas tecnologias de hardware, combase nos mesmos principios fundamentais. Alem disso, vai ficarclaro, no decorrer do capitulo, que existem algumas operacoesbasicas que todos os processadores precisam realizar. 1 3 , impor-tante lembrar que os projetistas de maquinas tern urn objetivo.comum: encontrar urn conjunto de instrucoes que facilite tantoa construcao do hardware quanta a do compilador e, ao mesmotempo, maximize a performance e minimize os custos. Esse ob-jetivo e perseguido himuito tempo, como se pode depreenderda seguinte citacao, escrita em 1947, muito antes que voce pu-desse imaginar que urn dia compraria urn computador, mas quee tao verdadeira hoje quanta era naquela epoca,

E fdcil observar, pelos metodos logico-formais, que existemalguns [conjuntos de instruciies] que, em tese, silo capazes deeontrolar e dar inicio a execucdo de qualquer sequencia deoperaciies ... As consideracoes realmente deeisivas do pontode vista atual, no que di: respeito a selecdo de um [conjuntode instrucoes], silo de natureza mais prdtica: a simplicidade

lnstrucoss Basicas: A Linguagem da Maquina 5

do equipamento exigida pelo [eonjunto de instruciies j e a clareza da sua aplicaciio aos problemas realmente importantesjunto com a velocidade de manipulacdo desses problemas.Burks, Goldstine e von Neumann, 194

SUP 0 RT. 0 A A "simplicidade do equipamento" e uma consideraW E B ~ao tao importante para as maquinas do ana 200quanto 0era para as maquinas da decada de 1950.objetivo deste capitulo e ensinar urn conjunto de instrucoes pertencente a urn processador tao simplequanta possfvel, mostrando tanto a interface do conjunto de instrucoes com 0 hardware quanta a relacao entre alinguagens deprogramacao de altomyel e tal conjunto de instrucoeSempre que for preciso usar uma linguagem de alto myel, utilizaremos a linguagem deprogramacao C. (Sevoce esta familiarizado coma linguagem Pascal e nao conhece a linguagem C, seria interessantconsultar a Extensao Web III, disponfvel em www.mkp.comcod2e.htm, para uma breve comparacao da C com a Pascal.)Aprendendo como as instrucoes sao representadas, voce acabara por entender 0principal conceito da teoria da computacao:o conceito do programa armazenado. Alem disso, voce tera oportunidade de exercitar os conceitos aprendidos, escrevendo programas em uma linguagem de maquina, e executando-os em ursimulador que vernjunto com este livro. * 0 capitulo termina comurn passeio pela evolucao hist6rica dos conjuntos de instrucoese com uma visao geral de outras linguagens de maquina,o conjunto de instrucoes escolhido para subsidiar nosso estudo foi 0 do MIPS, urn processador usado em produtos dNEC, da Nintendo, da Silicon Graphics e da Sony, entre outras companhias. 0 projeto do conjunto de instrucoes do MIPSe tipico dos projetos da decada de 1980. Seus segredos lhserao revelados gradativamente, sempre fazendo a ligacao dlinguagem com as estruturas da maquina. Essametodologia dexplanacao passo a pas so procura cercar de muitas explicacoestodos os componentes envolvidos, tomando muito mais palatavel 0 aprendizado da linguagem de maquina e da linguagemde montagem. Para manter foco no assunto, todas as secoesterrninam com uma figura que resume as instrucoes do MIPSestudadas ate aquele momento, dando destaque as partes apresentadas naquela secao,

3.2 Operaeoes Executadas pelo Hardware da MaquinaCom certeza deve haver instrucoes para executar as operaciies aritmeticas jundamentais.

Burks, Goldstine e von Neumann, 194Todo computador precisa ser capaz de executar operacoes aritmeticas, A notacao abaixo, da linguagem de montagem do MIPS

add a, b , Cinstrui 0 computador a somar as duas variaveis bee, colocando 0 resultado da soma em a.Esta notacao e extremamente rigida e muito limitada, na medida em que cada instrucao aritmetica do MIPS executa apenas umopera~a~ ~ precisa sempre ~eferenciar exat~ente tres variaveis, Por exemplo, suponha que desejemos colocar a soma de b, c, de na vanavel a. (Nesta secao, seremos dehberadamente vagos a respeito do conceito de "variavel"; na pr6xima secao, apresenta-remos urn quadro mais detalhado e mais realista sobre 0 assunto.)

"Essa notacao e conhecida como l inguagem de montagem. (N. T.)*0 simulador SPIM para a l inguagem de maquina do IVI lPS, processador cu ja l inguagemde maquina estudaremos neste capitulo, e assunto do Apendice A deste Iivro. As vers6es dsimulador para Unix, Windows e DOS estao disponivels para download no enderecowww.mkp.com/codie.htm. (N. T.)
http://www.mkp.com/http://www.mkp.com/codie.htm.http://www.mkp.com/codie.htm.http://www.mkp.com/


3/69

54 Orqanizacao & Projeto de Computadores - A Interface Hardware/Software

Linguagem de montagem do MIPS

Figura 3.1 Arquitetura do MIPS introduzida na Sel(iio 3.2. Os operandos reais da maquina so serao revelados na proxima secao. As partes que aparecem em negritomostram as estruturas da linguagem de montagem do MIPS introduzidas nesta se


4/69

lnstrucoes Baslcas: A Linguagem da Maquina 5

Solu~aoo compilador precis a quebrar este comando C em varias instrucoes da linguagem de montagem, uma vez que as instrucoes MIPS s6 realizam uma iinica operacao. A primeira das instrucoes MIPS calcula a soma de 9 e h. Precisamoscolocar 0 resultado em algum lugar, de maneira que 0 compilador cria uma variavel temporaria denominada t o :

a d d t o , 9 , h # A v a r i v e l t e m p o r r i a t o c o n t ~ m 9 + hEmbora a pr6xima operacao do trecho de programa em C seja uma subtracao, precisamos calcular a soma de icom j, antes dpodermos subtrair. Portanto, a pr6xima instrucao da linguagem de montagem do MIPS coloca a soma de ie j em outra variavetemporaria, criada pelo compilador, chamada t 1 :

a d d t l , i . j # A v a r i v e l t e m p o r r i a t l c o n t ~ m i + jFinalmente; a instrucao de subtracao diminui 0 valor da segunda soma do valor da primeira, colocando 0 resultado na variavelcompletando 0c6digo compilado:

s u b f . t O , t l # f r e c e b e t o - t l , q u e ~ (9 + h) - ( i + j )Estas instrucoes sao a representacao simb6lica da linguagem que 0processador MIPS realmente entende. Nas pr6ximas secoevamos transformar esta representacao simb6lica na linguagem real do MIPS.

3.3 Operandos do Hardware da MaquinaAo contrario dos programas em linguagens de alto nfvel, os operandos de instrucoes aritmeticas nao podem ser variaveis, poinao hi suporte em hardware para este conceito. Por esse motivo, eles vern de urn conjunto especial de localidades de mem6riachamados registradores. Registradores sao os tijolos com os quais se constr6i urn computador, pois eles sao as primitivas dprojeto do hardware que permanecem visfveis ao programador, quando 0projeto se toma operacional. Os registradores da aquitetura do MIPS sao de 32 bits. Grupos de 32 bits ocorrem tao freqtientemente no MIPS, que receberam 0nome de palavraA principal diferenca entre as variaveis de uma linguagem de alto nivel e os registradores e a quantidade limitada destes iiltimosdisponibilizados pelo hardware para uso. A maioria das maquinas atuais possui 32 registradores. 0 ?vIIPS nao foge a esta regrapossui 32 registradores em sua arquitetura. (Veja Secao 3.15 para urn breve hist6rico sobre 0mimero de registradores existentes narquitetura de divers as maquinas.) Portanto, dando continuidade a evolucao passo a passo da representacao simb6lica da linguagem do MIPS, nesta secao adicionamos a restricao de que os tres operandos das instrucoes aritmeticas do MIPS precisam ser escolhidos de urn dos 32 registradores de 32 bits.A razao para limitar em 32 0mimero de registradores pode ser encontrada no segundo dos quatro principios basicos do projetdo hardware:Principio de projeto 2: Quanto menor, mais rapido.

Urn grande mimero de registradores no hardware certamente faria crescer 0 ciclo do clock, tornando a maquina mais lenta.As regras do tipo "0menor e mais rapido" nao sao absolutas: 31 registradores no hardware nao devem fazer a maquina funcionar mais rapido do que se ela tivesse 32. Porem, a verdade por tras dessas observacoes faz com que os projetistas de computador aconsiderem com seriedade. Neste caso, 0projetista deve colocar na balanca a necessidade que os programas tern de mais registradores disponfveis, e 0desejo de manter 0 ciclo do clock tao pequeno quanto possivel.Os Capftulos 5 e 6 mostram 0papel fundamental que os registradores tern na construcao do hardware. Neste capitulo, veremoque 0 uso correto dos registradores e fundamental para 0born desempenho da maquina.Apesar de podermos simplesmente escrever instrucoes identificando por seus mimeros - de 0 a 31 - os registradores envolvidos, a convencao do MIPS usa urn cifrao ($) seguido de dois caracteres para referenciar urn registrador. A Secao 3.6 vai explicaos motivos que levaram a adocao desta convencao para os nomes dos registradores. Por enquanto, vamos usar $ sO , $ s 1,... paros registradores que correspondem as variaveis dos programas escritos em C, e $ t o , $ t1,... para os registradores temporaries,necessaries a traducao do programa em C nas instrucoes do MIPS.

Cornpila~aode urn Cornando de Atribui~aoem C Usando RegistradoresExemploFaz parte do trabalho do compilador fazer a associacao entre as variaveis de urn programa e os registradores do hardware. Tomemos como exemplo 0 comando de atribuicao do nosso exemplo anterior:

f = (9 + h) - (i + j);


5/69

56 Organiza({ao & Pro je to de Compu tadores - A Int er faceHardwa re /So ftware

Os valores das variaveis f, g, h, i e j podem ser atribufdos aos registradores $ sO, $ s 1, $ s 2, $ s 3 e $ S 4, respectiva-mente. Visto isto, pergunta-se: qual 0 c6digo em linguagem de montagem do MIPS, resultado da compilacao do comandoacima?Soluc;aoo programa compilado e muito semelhante ao apresentado no exemplo anterior, exceto pela substituicao dos nomes das variaveisconstantes das instrucoes aritmeticas pelos nomes dos registradores, atribufdos pelo compilador. As variaveis temporarias seraorepresentadas pelos registradores $ tOe $ t 1 :add $tO,$sl,$s2 # registrador $tO cont~m 9 + hadd $tl,$s3,$s4 # registrador $tl cont~m + jsub $sO,$tO,$tl # f recebe $tO - $tl, que ~ (g + h) - (i + j)

Nos exemplos dados ate agora, as estruturas da linguagem de programacao tern manipulado elementos de dados escalares, muitosimples de serem entendidos e tratados. Porem, como sabemos, as linguagens de programacao precisam suportar estruturas de dadosmais complexas, como os arrays. Tais estruturas podem conter muito mais elementos do que registradores disponfveis no hardwareda maquina. Como 0processador pode representar e acessar tais estruturas?Lembre-se dos cinco componentes de urn computador, introduzidos no Capitulo 1.Neste modelo, 0processador pode mantersomente urn pequeno rnimero de dados em seus registradores, mas a mem6ria do computador pode conter milhoes de elementos dedados. Portanto, as estruturas de dados, como os arrays, mantem-se armazenadas na mem6ria.Conforme explicamos anteriormente, as operacoes aritmeticas ocorrem somente entre valores armazenados em registradores ereferenciados pelas instrucoes do MIPS; portanto, 0MIPS precis a ter instrucoes que permitam a transferencia de dados entre amem6ria e os registradores. Tais instrucoes denominam-se instrucoes de transferencia de dados. Para acessar uma palavra na mem6ria,a instrucao deve fomecer ao processador 0 endereco na mem6ria da palavra a ser acessada. A mem6ria e simplesmente urn imensoarray unidimensional com 0endereco agindo como urn Indice para este array, comecando de O.Por exemplo, na Figura 3.2 0 ende-reco do terceiro elemento dos dados e 2, e 0 conteudo de Mem6ria[2] e 10.A instrucao de transferencia de dados que move urn dado da mem6ria para urn registrador e tradicionalmente chamada de load(carga). 0 formato da instrucao de load e 0nome da operacao seguido do registrador a ser carregado e de uma constante associadaa urn outro registrador, usados para enderecar a memoria. 0 endereco de memoria e formado pela soma da constante com 0conteii-do do registrador associado a ela (0 segundo registrador referenciado na instrucao de load). 0 verdadeiro nome desta instrucao noMIPS e 1 W , significando load word. *

310100

21 101o 1

Endereco Dados

P r o c e s s a d o r M e m o r i a

Figura 3.2 Enderejffos de memoria e conteudo da memoria nestes enderejffos. Esta e uma simplificacao do enderecamento do MIPS. A Figura 3.3 mostra 0en-derecamento do MIPS para palavras consecutivas da mem6ria.

*Na verdade, as instrucoes de load nao fazem uma "tr ansfer encia" do dado da mem6r ia para 0 registrador , mas sim uma simples "copia" deste , tendo ern vista que, ap6s a execucao dainstrucao, 0 dado continua arrnazenado na mem6ria. (N.T.)"Lembre-se de que 0primeiro indice do array e zero; portanto, ao indice 8 corresponde 0nono eiemento do array . (N . T . )


6/69


Cornpllaeao de uma Atribuit;ao com urn Operando na MemoriaExemploVamos supor que A seja urn array de 100 palavras, e que 0compilador tenha associado as variaveis 9 e h aos registradores $ se $ s 2, como anteriormente. Suponhamos tambem que 0endereco inicial do array, ou endereco-base, esta armazenado em $ s 3Traduza 0 seguinte comando de atribuicao, escrito em C, para a linguagem de montagem do MIPS:

9 = h + A[8];Soluc;aoApesar de haver uma tinica operacao neste comando de atribuicao escrito em C, urn dos seus operandos esta na mem6ria;portanto, precisamos em primeiro lugar transferir A [ 8] para urn registrador. Obtem-se 0 endereco deste elemento do arraypela soma do endereco-base do array A - encontrado no registrador $ s 3 - com seu fndice, que se usa para selecionarnono* elemento do array. 0valor obtido deve ser guardado em urn registrador temporario, para ser usado na pr6xima instru-9ao. Entao, a primeira instrucao compilada el w $ t O , 8 ( $ s 3 ) # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e A [ 8 ]A instrucao que se segue a esta pode operar normalmente com 0 valor de A [ 8 ], uma vez que ele esta em urn registrador, maiespecificamente em $ t o . A instrucao precisa entao adicionar h ( $ s 2 ) com A [ 8 ] ( $ t o ) e colocar 0 resultado da soma no registrador correspondente a 9 ($ s 1):a d d $ s l , $ s 2 , $ t O # 9 r e c e b e h + A [ 8 ]A constante que aparece na instrucao de transferencia de dados denomina-se deslocamento, e 0 registrador cujo valor armaze-nado e somado a esta constante e chamado de registrador-base.

InterfaceHardware/SoftwareAlem de associar variaveis a registradores, 0compilador aloca em enderecos da mem6ria determinadas estruturas de dados comoos arrays. Portanto, e facil para 0compilador colocar 0endereco inicial nas instrucoes de transferencia de dados, ja que a alocacaode espaco de mem6ria para programas e dados corre por conta dele.Considerando que sequencias de 8 bits ou bytes sao comuns de ocorrer na maioria dos programas, quase todas as arquiteturasenderecam bytes individuais. Portanto, 0 endereco de uma palavra deve ser igual ao endereco de urn dos bytes componentes dapalavra. Em funcao disto, 0 endereco de duas palavras sequenciais difere sempre de quatro unidades. Por exemplo, a Figura 3.3mostra 0 esquema real de enderecamento do MIPS correspondente 11Figura 3.2. Observe que a terceira palavra do array esta arma-zenada no endereco 8.No MIPS, as palavras precisam sempre comecar em enderecos que sejam multiples de 4. Esta necessidade e charnada restricdo de alinhamento, presente em muitas arquiteturas. (0Capitulo 5 mostra por que 0alinhamento leva a transferencias de dados mais rapidas.)As maquinas que enderecam bytes podem dividir-se em duas categorias: aquelas que usam 0 byte mais 11esquerda - bigendian - e aquelas que usam 0byte mais 11direita - little endian - para representar 0endereco da palavra. 0MIPS esta no rodas maquinas big endians. (0Apendice A, Secao A.9, mostra as duas opcoes para efetuar a numeracao dos bytes em uma pala-vra.)o enderecamento a byte tambem afeta a indexacao dos arrays. Para obter 0 endereco correto do byte no c6digo anterior, 0des-locamento a ser adicionado ao conteudo do registrador-base $ s 3 deve ser 4 X 8, 00 32, de modo que 0 elemento do arrayselecionado pela instrucao de load seja A [ 8] e nao A [ 8/4 ] .A instrucao complementar 11de load e tradicionalmente chamada de store (armazenamento); esta instrucao transfere (copia) urndado de urn registrador para a mem6ria. 0formato da instrucao de store e muito semelhante ao da instrucao de load: 0nome daoperacao seguido do registrador cujo conteiido deve ser armazenado na mem6ria, seguido pelo deslocamento e, finalmente, peloregistrador-base. Mais uma vez, 0endereco do MIPS e especificado em parte por uma constante e em parte pelo conteiido de urnregistrador. 0verdadeiro nome da instrucao de store no MIPS e SW , que significa store word.


7/69


10100

1011

Endereqo Dados

Processador MemoriaFigura 3.3 Esquema real de enderec;os do MIPS e 0 conteudo da memorianestas palavras. Os enderecos alterados aparecem em destaque, para contras-tar com os da Figura 3.2. Considerando que 0MIPS endereca byte, os endere-cos das palavras sao sempre multiplos de quatro (existem quatro bytes em umapalavra).

Compllacao Usando lnstrucoes de Load e StoreExemploSuponha que a variavel t1 esteja associada ao registrador $ S 2 e que 0 endereco-base do array A esteja arrnazenado em $ S 3.Qual 0 codigo de montagem do MIPS para 0 comando de atribuicao seguinte, escrito em C?

A [ 1 2 ] = h + A [ 8 ] ;solucaoApesar da existencia de uma iinica operacao neste comando C, agora existem dois operandos na memoria, de modo que saonecessarias mais instrucoes MIPS para implementar 0 comando. As duas primeiras instrucoes sao as mesmas do exemplo ante-rior, exceto pelo fato de agora estarmos usando 0deslocamento correto na instrucao de load, usada para selecionar A [8], con-siderando que 0MIPS endereca byte. A instrucao de soma coloca 0 resultado dessa operacao no registrador $ to.

l w $ t O , 3 2 ( $ s 3 ) # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e A [ 8 ]a d d $ t O , $ s 2 , $ t O # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e h + A [ 8 ]A ultima instrucao arrnazena a soma no endereco A [ 12 ] , usando 0valor 48 como deslocamento em relacao a base do array,representada pelo contetido do registrador $ s 3.s w $ t O , 4 8 ( $ s 3 ) # h + A [ 8 ] e a r m a z e n a d o d e v o l t a n a m e m 6 r i a e m A [ 1 2 ]

Os arrays muitas vezes sao acessados com variaveis em vez de constantes, de maneira que 0elemento do array selecionado emuma instrucao de transferencia pode mudar durante a execucao do programa.

Compila~ao Usando uma Variavel para lndexar 0ArrayExemploA seguir, apresentamos urn exemplo de urn array indexado por uma variavel,

g = h + A [ i ] ;Suponhaque A e urn array de 100 elementos cujo endereco-base esta no registrador $ S 3 e que 0compilador associ a as variaveis g,h e i aos registradores $ S 1 , $ s 2 e $ S4 . Qual 0 codigo gerado para 0 MIPS, correspondente ao comando C acima?

SolugaoAntes que possamos carregar A [i ] em urn registrador temporario, precisamos conhecer seu endereco. Antes de somar 0valorde iao endereco-base do array A , e preciso multiplicar 0valor do Indice ipor 4, devido a questao do enderecamento a byte. Noproximo capitulo, vamos aprender sobre a instrucao de multiplicacao; por ora, vamos usar 0 artiffcio de multiplicar ipor 4primeiro somando 0valor de i a ele mesmo ( i + i = 2 i)depois adicionando esta soma a ela mesma ( 2 i + 2 i = 4 i ) :

a d d $ t l , $ s 4 , $ s 4 # R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 2 * ia d d $ t l , $ t l , $ t l # R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 4 * i


8/69

Instruc,;5es Basicas: A Linguagem da Maquina 5Para obter 0endereco de A [i ], precisamos entao somar $ t 1 ao endereco-base de A , armazenado em $ s 3:a d d $ t l , S t l , $ s 3 # R e g i 5 t r a d o r t e m p o r a r i o $ t l r e c e b e 0 e n d e r e c o d e A [ i ] ( 4 *Agora, podemos usar esse endereco para carregar A [i ] em urn registrador temporario:lw $ t O , O ( $ t l ) # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e A [ i ]A instrucao final do codigo MIPS para 0comando C soma 0valor de A [ i]com h, e coloca 0resultado em q:

a d d $ 5 1 , $ s 2 , $ t O # 9 r e c e b e h + A [ i ]

+ $ 5 3 )

InterfaceHardware/SoftwareMuitos programas trabalham com muito mais variaveis do que 0 numero de registradores que a maquina-alvo tern disponiveisConsequentemente, 0compilador tenta manter nos registradores as variaveis usadas com mais frequencia, colocando as demaismemoria, usando instrucoes de load e store para mover essas variaveis da memoria para os registradores, e vice-versa. 0processde colocar na memoria as variaveis menos usadas (ou que so serao usadas mais tarde) e conhecido como derramamento (spillingde registradores.o principio de projeto do hardware relacionando tamanho e velocidade sugere, com muita propriedade, que 0acesso a memorideve ser muito mais lento que 0 acesso a registradores, visto que a quantidade destes iiltimos e muito menor que a quantidade denderecos de memoria. Este e de fato 0caso: 0acesso a dados em registradores se da de maneira muito mais rapida do que 0acessa dados na memoria.Portanto, os dados sao muito mais iiteis quando armazenados em registradores. Uma instrucao aritmetica do MIPS deve ler doregistradores, operar os dados lidos desses registradores e escrever 0 resultado da operacao. Uma instrucao de transferencia ddados no MIPS so Ie urn operando ou escreve urn operando, sem efetuar qualquer operacao sobre ele.Entao, os registradores do MIPS, alem de gastarem muito menos tempo para acessar operandos do que a memoria, ainda aprsentam urn throughput mais alto que a memoria - uma combinacao que ocorre muito raramente -, fazendo com que os dados eregistradores sejam mais rapidos de acessar e mais simples de usar. Para obter a melhor performance, os compiladores do MIPprecisam usar os registradores de modo eficiente.

A Figura 3.4 resume tudo 0 que vimos sobre a representacao simbolica das instrucoes do MIPS ate esta secao. As instrucoeload word e store word sao duas das instrucoes que transferem palavras entre a memoria e os registradores na arquitetura do MIPSOutros processadores usam outras instrucoes, alem da instrucao de load e da de store para transferir dados. Urn exemplo de arqutetura com esta altemativa e a do Intel 80x86, descrita na Secao 3.12.

Operandos do MIPS

32 registradores Posi' ioes de acesso rapldo para armazenamento de dados. No MIPS, os dados devem estarem registradores para que as operacees arltmettcas possam ser realizadas.$80, $81,$tO, $t1,No MIPS, estas posi'i0es so sao acessadas por instruf!ioes de transferencia de dados. 0MIPSendereca byte, de modo que enderef!ios de palavras consecutlvas dlferem de4 unidades.

2'0palavras de memoria Memoria[O],Memoria[4], ...,Mem6rla[ 4294967292]


add add $81, $s2, $83 $51 $52 + $53 Trss operandos; dados emregistradoresAritmetlca subtract 8ub $81, $82, $83 $51 = $52 - $53 Tres operandos; dados emregistradores

load word lw $81, 100 ($82) $81 = Memoria[$82 + 100) Dados transferldos da memoriapara registradoresTransferencia de dados store word 8W $81, 100($82) Memoria [$82 + 100) = $81 Dados transferldos deregistradores para a memoria

Figura 3.4 Arquitetura do MIPS introduzida na Sef!iao 3.3. As partes em negrito mostram asestruturas da l inguagem demontagem do MIPS introduzidasSecao 3.3.


9/69


Elabora-;ao: 0 modo de enderecarnento em que 0 deslocamento e somado ao conteudo do registrador-base e uma excelente ideia para serusada em estruturas de dados, uma vez que 0 registrador pode apontar para 0 lnlcio da estrutura e 0deslocamento pode selecionar 0elementodesejado dentro da estrutura. Vamos ver um exemplo disto na Se9ao 3.10.o registrador nas instrucoes de transferencia de dados foi inventado com 0objetivo de guardar 0 indice de um array, com 0deslocamento marcandoo enderaco inicial de tal array. Em razao disso, 0registrador-base e tarnbern conhecido como registrador-fndice. Atualmente as mem6rias sao muitomaiores que antigamente, eo modelo de software para alocacao de espaco de mem6ria e muito mais sofisticado, de modo que 0endereco-base doarray normal mente e passado em um registrador, pols ele nao cabe no deslocamento, como veremos mais tarde.3.4 Representa~ao de lnstrucoesEstamos preparados para explicar a diferenca entre a maneira como as pessoas instruem as maquinas e a maneira como as maqui-nas veem as instrucoes. Antes, porem, vamos rever rapidamente como a maquina representa mimeros,As pessoas aprenderam a pensar na base 10. No entanto, todos sabemos que os mimeros podem ser representados em qualquerbase de numeracao, Por exemplo, 0mimero 123 na base 10 e igual a 1111011 na base 2.Os mimeros sao mantidos no hardware do computador como urn conjunto de sinais eletr6nicos que podem assumir somente doisestados - alto e baixo. Portanto, em urn computador os mimeros sao considerados como na base 2. (Assim como os mimerosexpressos na base 10 sao chamados de mimeros decimals, os mimeros expressos na base 2 sao conhecidos como bindrios.) Urniinico dfgito de urn mimero binario e 0 "atomo" da ciencia da computacao, uma vez que toda a informacao e constitufda de digitosbinaries ou bits. 0 bit, urn conceito de extrema importancia no estudo do computador, pode portanto assumir urn de dois valores,normalmente associados a: alto ou baixo, ligado ou desligado, verdadeiro ou falso, e 1 ou O .As instrucoes tambem sao mantidas no computador como uma serie de sinais eletr6nicos altos e baixos e podem ser representa-das como mimeros. De fato, cada parte de instrucao pode ser considerada como um mimero separado, e a colocacao de tais mimerosum ao lado do outro forma a instrucao.Considerando que os registradores sao parte de quase todas as instrucoes, e preciso haver uma convencao para mapear 0 nomedos registradores em mimeros. Na linguagem de montagem do MIPS, os nomes de $ s 0 a $ S 7 sao mapeados nos registradores de16 a 23, e os nomes de $ t 0 a $ t 7, nos registradores de 8 a 15. Portanto, $S0 significa 0 registrador 16, $s 10 registrador 17, $s 2o registrador 18, . .. , $tO 0registrador 8, s t l 09, e por ai vai. Nas proximas secoes, sera descrita a convencao para os demaisregistradores.

Tradu~aode uma lnstrucao na Linguagem de Montagem do MIPS para umalnstrucao da MaquinaExemploVamos cumprir 0 proximo passo do refinamento da linguagem do MIPS com mais um exemplo. Vamos mostrar a versao nalinguagem do MIPS para a instrucao representada simbolicamente comoadd $tO. $sl, $s2

primeiro como uma combinacao de mimeros decimais e depois como mimeros binaries.Soluc;aoA representacao decimal e

o 17 18 8 o 32Cada ur n dos segmentos mostrados na instrucao e chamado de campo. 0primeiro e 0ultimo (contendo 0 e 32 neste caso), quandocombinados, informam aoMIPS que esta instrucao efetua uma adicao, 0 segundo campo informa 0mimero do registrador que vem a sero primeiro operando-fonte desta operacao de adicao (17 = $ s 1).0terceiro campo informa 0segundo operando-fonte para a adi~ao (18= $ s 2).0 quarto campo contem 0mimero do registrador que deve receber 0valor da soma (8=$ to). 0 quinto campo nao e utilizadonesse tipo de instrucao, de modo que seu valor neste caso e o . Pelo exposto, esta instrucao soma 0 conteiido do registrador $ s 1 ao doregistrador $ s 2, e coloca 0resultado da soma no registrador $ to .Esta instrucao tambem pode ser representada como campos de mimeros binaries equivalentes aos decimais mostrados ante-riormente:

000000 10001 10010 01000 00000 1000006 bits 5 bits 5 bits 5 bits 5 bits 6 bits

Para distinguir a linguagem de montagem desta ultima, vamos chama-la de linguagem de mdquina e a sequencia de suas instru-~6es de codigo de mdquina.


10/69

Instruc;:6es Basicas: A Linguagem da Maquina 6

Este layout de instrucao e chamado deformato de instrucdo. Como voce pode observar, contando 0mimero de bits do formato apresetado, a instrucao do rvIIPStern exatamente 32 bits, 0mesmo tamanho de uma palavra de mem6ria e de urn dado. Coerente com nosprincfpio de projeto onde afirmamos que a simplicidade e favorecida pela regularidade, todas as instrucoes do rvIIPStern 32 bits.

Campos das mstrucoes de Maquina do MIPSPara tomar mais facil a discus sao, os campos das instrucoes de maquina do MIPS recebem nomes:

op rs rt rd shamt tunc!6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

A seguir, veja 0 significado de cada urn dos campos das instrucoes do MIPS:III op: a operacao basic a a ser realizada pel a instrucao, tradicionalmente chamada de codigo de operaciio (opcode)III rs: 0 registrador contendo 0 primeiro operando-fonteIII rt : 0 registrador contendo 0 segundo operando-fonteIII rd: 0 registrador que guarda 0 resultado da operacao, tambem conhecido como registrador-destinoIII shamt: de quantidade de bits a serem deslocados. (Isto sera explicado no Capitulo 4, quando estudarmos as instrucoes ddeslocamento; ate la, este campo nao sera usado, e portanto contera sempre zero.)III junct: funcao. Este campo seleciona uma variacao especifica da operacao apontada no campo op, sendo as vezes chamado dcodigo de funciio.

Podem ocorrer problemas caso a instrucao precise de campos maiores que os mostrados anteriormente. Por exemplo, a instrucao dload word precisa especificar dois registradores e uma constante. Se 0campo da constante usasse os mesmos 5 bits do campo doregistradores, esta constante estaria limitada a 25 = 32. Como ela e usada para selecionar elementos de urn array muito grande ode uma estrutura de dados com muitos elementos, e necessario que e1apossa assumir valores muito superiores a 32. Portanto, escampo de 5 bits e muito pequeno para 0 fim a que se des t ina.Por isso, temos urn conflito entre 0desejo de manter todas as instrucoes do mesmo tamanho e 0desejo de ter urn iinico formatde instrucao. Este fato nos leva ao terceiro dos quatro principios basicos do projeto do hardware:Principio de projeto 3: Urn born projeto demanda compromisso.o compromisso escolhido pelos projetistas do MIPS foi manter todas as instrucoes do mesmo tamanho, precisando portanto dformatos diferentes para tipos distintos de instrucoes. Por exemplo, 0 formato acima e 0 tipo R (R-type), ouformato R (R-format)sendo 0R usado para lembrar 0uso de registradores pela instrucao, Urn segundo formato de instrucao e chamado de tipo I (I-typeouformato I (I-forman, e e usado na representacao das instrucoes de transferencia de dados. Os campos das instrucoes de format

I sao os seguintes:op rs rt enderec;:o

6 bits 5 bits 5 bits 16 bits

o campo de 16 bits reservado para 0endereco significa que uma instrucao de load word pode carregar qualquer palavra dentrda faixa entre 0 endereco constante no registrador-base - rs - acrescido ou decrescido de 215 ou 32.768 bytes (213 ou 8.19palavras).Vamos dar uma olhada na instrucao de load word da Secao 3.3, item Compilacao Usando Instrucoes de Load e Store.

l w $ t O , 3 2 ( $ s 3 ) # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e A [ 8 ]Aqui, o valor 19 (porcausade $ 53) e colocado no campo rs, o valor 8 (por causa de $ to) e colocado no campo rt, eo valor 32 no campde endereco. Observe que 0significado do campo rt mudou para esta instrucao: numa instrucao de load word, 0campo rt especificaregistrador destino, aquele que recebe 0 resultado da carga.Apesar de os nniltiplos formatos complicarem urn pouco 0projeto do hardware, podemos minimizar este efeito mantendo os formatoo mais parecidos possfvel. Por exemplo, os tres primeiros campos das instrucoes de tipo R e de tipo I sao do mesmo tamanho e tern omesmos nomes; 0quarto campo da instrucao de tipo I tern comprimento igual ao dos tres iiltimos campos da instrucao de tipo R.Voce deve estar perguntando como se da a distincao entre os formatos. A resposta e a seguinte: eles se diferenciam pelo valor dprimeiro campo. A cada formato e atribufdo urn valor diferente ao primeiro campo (op), de modo que 0hardware possa saber comtratar 0restante da instrucao: ou procura por tres campos (de tipo R) ou busca urn iinico campo (de tipo I). A Figura 3.5 mostra omimeros usados em cada urn dos campos para as instrucoes do MIPS cobertas ate a Secao 3.3.


11/69

62 Organiza9ao & Projeto de Computadores - A Interface Hardware/Software

a d d R 0 reg reg reg n.-a.sub (subtract) R 0 reg reg reg 0 34 n.-a.1 'Ii (load word) 35 reg reg n.-a. n.-a. n.-a. enderecoSI, (store word) 43 reg reg n.-a. n.-a. n.-a. endereco

Figura 3.5 Codificaltiio das instrult0es do MIPS. Na tabela acima, "reg" significa mimero de urn registrador entre 0 e 31, "endereco" urn valor de 16 bits, e, "n>a."(nao-aplicavel) significa que 0campo em questao nao existe nesse formato. Note que as instrucoes add e sub tern mesmo valor no campo op; 0hardware usa campo funct para decidir qual a operacao a ser executada: soma (32) ou subtracao (34).

Traducao da Linguagem de Montagem do MIPS para a Linguagem de MaquinaExemploPodemos agora pegar urn exemplo e percorrer todo 0caminho entre aquilo que 0programador escreve e 0que a maquina exe-cuta. Supondo que $ t 1 tern 0 valor-base do array A , e que $ S 2 corresponde a h , 0 comando de at r ibu icao escrito em C mostra-do a seguir

A[300] = h + A[300];e compilado eml waddS vJ

$tO,1200($t1)$tO,$s2. $tO$ t O , 120 0( $ t l)# Registrador temporario $tO recebe A[300]# Registrador temporario $tO recebe h + A[300]# h + A[i] ~ armazenado de volta na mem6ria em A[300]

Qual e 0 c6digo de maquina do MIPS correspondente a essas tres instrucoes?soiucaoPor conveniencia, vamos primeiro representar as instrucoes da linguagem de maquina do MIPS usando mimeros expressos emdecimal. A partir da Figura 3.5, podemos deterrninar as tres instrucoes da linguagem de maquina:

o t835 9

8 8 o 3 28 1200

43 9 8 1200

A instrucao 1 y V e identificada por 35 (veja Figura 3.5) em seu primeiro campo (op). 0 registrador-base 9 ($t1) e especifica-do no segundo campo (rs), e 0 registrador-destino 8 ($ t0) e especificado no terceiro campo (rt). 0 deslocamento para selecio-nar A [3 00 ] (1.200 = 300 X 4) pode ser encontrado no ultimo campo (endereco),A instrucao seguinte, de soma, e identificada pelo valor 0 em seu prirneiro campo (op) e pelo valor 32 no ultimo (funct). Os

tres registradores referentes aos operandos podem ser encontrados no segundo, no terceiro e no quarto campos e correspondemaos registradores $ s 2, $t 0 e $ to.A instrucao S w e identificada pelo valor 43 em seu primeiro campo. 0 restante desta ultima instrucao e identico a 1w .o formato binario, equivalente ao decimal discutido anteriormente, aparece a seguir (1.200 na base 10 e igual a 0000 01001011 0000 na base 2):

10011 01001 01000 0000 0100 1011 0000000000 10010 01000 01000 _ I 00000 I 1000001O~O11 01001 01000 0000 0100 1011 0000

Note a semelhanca entre as representacoes binarias da primeira e da ultima instrucao - 1We Sw. A unica diferenca e no terceirobit a partir da esquerda.


12/69

lnstrucoss Basicas: A Linguagem da Maqulna 6

A Figura 3.6 resume as partes da linguagem de montagem do MIPS descritas nesta secao. Conforme teremos oportunidade dver nos Capitulos 5 e 6, a similaridade das representacoes binarias de instrucoes que tenham alguma relacao simplifica muitoprojeto do hardware. Essas instrucoes sao outro born exemplo da regularidade da arquitetura do MIPS.Elaboral?80: A representacao de valores decimais na base 2 nos da uma maneira simples de representar inteiros positivos nas palavras dmem6ria do computador. 0Capftulo 4 mostra como representar os inteiros negativos, mas por ora basta que saibamos que em uma palavra d32 bits podemos representar inteiros entre -231 (-2.147.483.648) e +231 - 1 (2.147.483.647). Nurneros representados neste formato sao chmados de numeros inteiros em compiemento a 2.

Operandos do MIPS

32 registradores $s7H7$sO. $sl.s r o . ttl. Posleoes de acesso rapldo para armazenamento de dados. No MIPS. os dados devem estar emregistradores para que as ope racoes a r it rne ti c as possam ser realizadas. Os registradores $ 5 0 -$57 sao mapeados nos registradores reais de numsro 16-23 e os registradores HO-$t7 nosde numero 8-15.230 palavrasde mem6ria

No MIPS. estas poslcoes so sao acessadas por lnst rucoes de t ransterencta de dados. 0 MIPSendereca byte. de modo que enderecos de palavras consecutivas diferem de 4 unidades. Amemoria armazena estruturas de dados, como arrays. alarn dos registradores "derramados".

Memoria[O]Memoria[4] .....Memoria[4294967292]


Aritrnatica add a d d s s 1. $s2. $s3 $sl $s2 + $s3 rres operandos; dados em registradoressubtract sub s s i.$s2. $s3 $sl $s2 - $53 Tres operand os; dados em registradores

Transtsrencla load word 1 w $s 1, 100($s2) $sl Memoria[$s2 +100] Dados transferidos da memoria parade dados registradoresstore word sw $sl, 100($s2) Memoria[$s2 + 100] = $sl Dados transferidos de registradores paraa memoria

Linguagem de rnaquina do MIPS

addsublwswTamanho docampoFormato RFormato I

o add $81, $82, $8320 1 8 19a 1 8 1935 1 8 1743 1 8 17

6 bits 5 bits 5 bits

op rs rtop rs rt

17R Bub $81, $82, $837 o 34

1w $81, 100($82)00sw $81, 100($82)00

6 bits Todas as instruQoes do MIPS tem 32 bitsbits 5 bits

tunct Formato das instruQoes aritmetlcas

Figura 3.6Arquitetura do MIPS introduzlda na SeQao 3.4. As par tes em negrito most ram as estruturas da Iinguagem de montagem do MIPS introduzidas na Selia3.4. Os dois formatos de instrucao do MIPS estudados ate 0momenta foram os formatos ReI. Os primeiros 16 bits de ambos os formatos sao identicos: amboscontem urn campo op, informando a operacao basica; urn campo rs, fornecendo urn dos operandos-fonte; e urn campo rt, que especifica 0outro operando-fonte,com excecao da instmcao de load word, onde este campo especifica 0registrador-destino. Na instrucao formato R, os ultimos 16 bits sao divididos no campo rdespecificando 0registrador-destino; no campo shamt, que nao e usado no Capitulo 3 e, portanto, esta sempre em 0; e no campojimct, que indica a operacao especffica a ser realizada pela instrucao de formato R . A instrucao de formato I mantem em seus ultimos 16 bits urn campo de endereco.

rd shamtFormato das instrugoes detransferencia de dadosenderego


13/69

64 OrganizaQao & Projeto de Computadores - A Interface Hardware/Software

Memoria

Figura 3.7 Conceito de programa armazenado. Programas armazenados pennitem que urn computador que esteja fazendo urn trabaIho de contabilizacao douse deseus recursos passe, num piscar de olhos, a ser urn computador que ajuda urn autor a escrever urn livro. 0 chaveamento acontece simplesmente quando se carrega amemoria do computador com programas e dados, fazendo-o entao comecar a execucao desse prograrna, a partir de determinado endereco de memoria. 0 tratamento deinstrucoes do mesmo jeito que se tratam os dados facili ta enormemente tanto 0hardware da memoria quanto 0 software do sistema de computacao. Especificamente,a tecnologia de memoria necessaria para armazenar dados pode tambem ser usada no armazenamento de programas, e programas, como 0 compilador, por exemplo,podem traduzir codigo escrito em uma notacao mais proxima da conveniencia dos seres humanos para urn codigo que os computadores possam entender.

Quadro-ResumoA construcao dos computadores de hoje obedece a dois prindpios basicos:1. As instrucoes sao representadas como se fossem mimeros.2. Os programas devem ser armazenados na memoria antes de serem executados.o respeito a esses princfpios leva ao conceito de programa armazenado, ideia que tirou de dentro da garrafa 0 genic dacomputacao. A Figura 3.7 mostra 0poder deste conceito: especificamente podem estar na memoria programas tao diversosquanta 0codigo-fonte para urn programa de edicao de texto, 0codigo de maquina correspondente a compilacao desse pro-grama, 0 texto que 0programa compilado esta editando neste momento, e ate 0compilador que gerou 0 codigo de maquina,

3.5 lnstrucoes de DesvioA utilidade de um computador reside na possibilidade de se usar uma sequencia de instruciies repetidamente, sendo que 0nu-mero de iteracoes depende fundamentalmente do resultado dos cdlculos realizados pelo pr6prio programa. Quando a iteracdose completar, uma outra sequencia [de instruciies] sera executada, de modo que precisamos, na maioria dos casos, especi-ficar dois conjuntos paralelos [de instruciies] precedidos de uma instrucdo que vai determinar qual das duas seqiienciassera executada. Esta escolha poderd depender do sinal de um numero, com 0zero sendo reconhecido como positivo, para osprop6sitos da mdquina. Conseqiientemente, devemos introduzir uma [instructio] (a [instruciio] de transferencia condicio-nal) que ira, dependendo do sinal de um dado numero, fazer com que uma das duas seqiiencias seja executada.

Burks, Goldstine e von Neumann, 1947A diferenca entre urn computador e urna simples calculadora eletronica e a capacidade do computador de escolher entre diversos caminhosde execucao, Melhor dizendo, com base em dados de entrada e em valores criados durante a execucao do programa, diferentes instrucoespoderao vir a ser executadas. A tomada de decisao geralmente e representada nas linguagens de programacao pelo comando if, as vezescombinado com 0comando go to e com labels. A linguagem de montagem do MIPS inc1ui duas instrucoes de desvio, similares a urnif e a urn go to combinados. A primeira dessas instrucoes e

b eq registradorl, registrador2 , LlEsta instrucao, quando executada, forcara urn desvio para 0 comando com 0 label L1, se 0 valor no reg i s t r a do r 1 forigual ao valor no reg i s t r a do r 2 . 0 mnemonico b e q refere-se a desvie se igual (branch if equal). A segunda instrucao e

b ne registradorl, registrador2 , Ll


14/69

lnstrucoes Basicas: A Linguagem da Maquina 65

e significa que a proxima instrucao a ser executada e aquela que estiver armazenada no endereco L1 da memoria, se 0valor noreg i s t r ado r 1 for diferente do valor no reg i s t r ado r 2. 0 mnemonico b n e refere-se a desvie se niio igual (branch if noequal). As duas instrucoes que acabamos de descrever sao tradicionalmente chamadas de instruciies de desvio condicional.

Cornpilagao de urn Cornando if em urna lnstrucao de Desvio CondicionalExemploNo segmento de codigo a seguir, escrito na linguagem C, f, g, h, i e j sao variaveis:

if (i == j) go to L1;f 9 + h;L1: f=f-i;

Partindo do pressuposto de que as cinco variaveis de fate j correspondem aos cinco registradores, de $ s 0 a $ S 4, pergunta-se:qual 0 c6digo MIPS gerado pelo compilador?Solu~aoo primeiro comando C compara duas variaveis e desvia para a operacao de subtracao se elas forem iguais. Considerando queambos os operandos estao em registradores, esta operacao de alto nfvel pode ser mapeada diretamente na instrucao branch iequal (desvie se iguali do MIPS (mais tarde veremos que tratamento dar ao label Ll):beq $s3,$s4,L1 if desvia para Ll se i for igual a jo comando seguinte em C realiza uma tinica operacao, e 0 codigo gerado para ele possui simplesmente uma tinica instrucao:add $sO,$sl,$s2 i f f = 9 + h (i n s t r u c ;: a 0 n a 0 ex e cut a d a s e i for i 9 u a 1 a j)o ultimo comando em C tambem pode ser compilado em uma tinica instrucao. 0 problema e como especificar seu endereco demaneira tal que 0 desvio condicional possa saltar a instrucao de soma escrita acima.Como ja sabemos, as instrucoes estao armazenadas na memoria das maquinas com programa armazenado. Portanto, a cadainstrucao esta implicitamente associado urn endereco na mem6ria correspondente a palavra que ela estiver ocupando. A ul-tima instrucao do c6digo gerado para 0MIPS simplesmente incorpora 0 label L I, referenciado pela instrucao be q.L 1 : sub $sO,$sO,$s3 if f = f - i (sempre executado)Portanto, 0 label L1 corresponde ao endereco onde a instrucao sub esta armazenada.

Observe que 0montador desobriga tanto 0 compilador quanta 0 programador na linguagem de montagem da tarefa estafante etediosa de ca1cular os enderecos para os desvios, a exemplo do que ja acontecia com 0 calculo dos enderecos dos dados nas instru-90es de load e store (veja Se9ao 3.9).

InterfaceHardware/SoftwareCom frequencia os compiladores sao obrigados a criar desvios e labels que nao aparecem na programacao de alto nivel. Evitar 0desgaste de ter que escrever labels explicitos e desvios e urn dos beneficios de se programar em uma linguagem de alto nfvel, e 0principal motivo para justificar a rapidez de se programar neste myel.

compltaeao do Comando it-then-else em Desvios CondicionaisExemploUsando as mesmas variaveis e registradores do exemplo anterior, obtenha 0 c6digo MIPS gerado para 0 seguinte comando emC:if (i j) f 9 + h; else f 9 - h;

Solu~aoNa Figura 3.8 aparece 0 fluxograma daquilo que 0 c6digo MIPS deve fazer. A primeira expressao do comando C compara doisvalores, em busca da igualdade, de modo que fica muito claro que precisaremos da instrucao be q mais uma vez. Em geral, 0


15/69

66 Orqanlzacao & Projeto de Computadores - A Interface Hardware/Software

Exit:Figura 3.8 lIustrac;:iio das opc;:oesdo comando if mostradoaclma. A caixa a esquerda corresponde ao then do comandoif, e a da direita corresponde ao else.

c6digo sera mais eficiente se fizermos 0 teste em busca da condicao oposta, para que possamos desviar sobre 0 c6digo que exe-cuta a parte subseqtiente, correspondente ao then (0 label E 1 see definido a seguir):b n e $ s 3 , $ s 4 , E 1 s e i F d e s V i a p a r a E 1 s e s e i * " jo comando seguinte em C realiza uma iinica operacao, e 0 c6digo gerado para ele tern simplesmente uma iinica instrucao:a d d $ s O , $ s 1 , $ s 2 # f = 9 + h ( s a l t a e s s a i n s t r u ~ ~ o s e i * " j)Agora precisamos ir para 0 fim do comando if . Para isso, precisamos introduzir urn outro comando de desvio, geralmente cha-mado de desvio incondicional. Esta instrucao faz com que a maquina sempre execute 0desvio. Para fazer distincao entre 0 des-vio condicional e 0 incondicional, 0MIPS chama este ultimo tipo de instrucao de instrucao de jump (salto), abreviado como j

(0 label E x i t e definido a seguir):j E x i t # d e s v i a p a r a E x i to comando de atribuicao na parte referente ao else do comando ifpode novamente ser compilado em uma tinica instrucao demaquina. Simplesmente precisamos fazer com que 0 label E 1 s e seja incorporado a instrucao, Tambem ja mostramos que 0label E x i t deve estar depois desta instrucao, marcando 0 fim do c6digo do comando if-then-else compilado:E l s e : s u b $ s O , s s l , $ s 2 # f = 9 - h ( s a l t a e s s a t n s t r u c a o s e i = j)E x i t :

LoopsOs comandos de desvio sao importantes tanto para se escolher entre duas altemativas - caso dos comandos if - quanto paracontrolar iteracoes de uma detenninada computacao - caso dos loops. As mesmas instrucoes da linguagem de montagem saousadas na construcao de ambas as estruturas.

compuacso de um Loop Contendo um Array com (ndice VariavelExemploA seguir apresentamos urn loop programado na linguagem C:

L o o p : 9 = 9 + A [ i ] ;i = i + j;if (1 != h) g o t o L o o p ;Suponha que A seja urn array de 100 elementos e que 0 compilador associe as variaveis g, h , ie jaos registradores $ s 1, $ s 2,$ s 3 e $ s 4 , respectivamente. Vamos admitir tambem que a base do array A esteja em $ s 5 . Qual e 0 codigo, em linguagem demontagem do MIPS, que corresponde a este loop escrito em C?

Solu(:aoo primeiro passo e carregar 0 valor A [i ] em urn registrador temporario. Vamos tomar emprestado 0 c6digo de urn exemplosimilar, apresentado na Secao 3.3. E necessario apenas adicionar 0 label L0 0 p a primeira instrucao de modo a podennos desviarpara esta instrucao ao final do loop:

L o o p : a d da d da d dlw

H 1 , $ s 3 , $ s 3s t l , s t l , H 1H I , H I , $ ; ; 5$ t O , O ( $ t l )

# R e g i s t r a d o r t e m p o r ~ r i o $ t I r e c e b e 2 *# R e g i s t r a d o r t e m p o r ~ r i o $ t l r e c e b e 4 *# $ t l r e c e b e e n d e r e ~ o d e A [ i ]# R e g i s t r a d o r t e m p o r ~ r i o $ t O r e c e b e A [ i ]


16/69

tnstrucoss Baslcas: A Linguagem da Maquina 67

As duas instrucoes seguintes somam A [i ] com g, e j com i :add $sl.$sl.$tOa d d $ s 3 , $ s 3 , $ s 4 1 t 9 r e c e b e = 9 + A [ i ]1 t i r e c e b e = i + j

A instrucao final desvia de volta para L 00 p se i* h:b n e $ s 3 , $ s 2 , L o o p # d e s v i a p a r a L o o p s e i * hConsiderando que 0 corpo do loop modifica 0 valor de i,necessario multiplica-Io por 4 cada vez que entramos no loop. (ASecao 3.11 mostra como evitar essas "multiplicacoes" ao escrever loops como este.)

InterfaceHardware/SoftwareAs seqtiencias de instrucoes terminadas em urn desvio sao tao fundamentais para a compilacao que receberam definicao pr6pria:urn bloeo bdsico e uma sequencia de instrucoes sem desvio, exceto possivelmente no final, e sem labels-alvo de desvios, excetotalvez no infcio. Uma das primeiras tarefas do processo de compilacao e dividir 0 prograrna em blocos basicos,

C orn pila c;a o d e u rn L oo p whileExemploEm geral, os programadores nao escrevem loops usando os comandos go to, de maneira que e da responsabilidade docompilador traduzir os loops tradicionais para a linguagem do MIPS. Aqui temos urn loop tradicional escrito em C:

w h i l e ( s a v e [ i J == k )i = i+ j;Suponha que i , j e k correspondam aos registradores $ s 3 , $ s 4 e $ s 5, e que 0endereco-base do array s a v e esteja guardadoem $ s 6. Qual e 0 c6digo, em linguagem de montagem do MIPS, correspondente a este segmento de c6digo escrito em C?

Solu~aoo primeiro passo e carregar 0valor s a v e [i]m ur n registrador temporario. 0c6digo comeca similar ao do exemplo anterior:L o o p : a d d $ t l , $ s 3 , $ s 3 # R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 2 * ia d d $ t l , $ t l , $ t l # R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 4 * ia d d $ t l , $ t l , $ s 6 # $ t l r e c e b e e n d e r e ~ o d e s a v e [ i Jl w $ t O , O ( $ t l ) # R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e s a v e [ i J

A pr6xima instrucao e responsavel pelo teste do loop, saindo dele se s a v e [ i]1 = k:b n e $ t O , $ s 5 , E x i t # d e s v i a p a r a E x i t s e s a v e [ i J * k

A pr6xima instrucao soma j com i:a d d $ s 3 , $ s 3 , $ s 4 # i r e c e b e i + j

A instrucao final do loop desvia de volta para 0 teste do while no infcio do loop. Para marcar 0 fim do loop, simplesmente adi-cionamos 0 label E x it ap6s esta instrucao, como mostramos a seguir: .j L o o p # d e s v i a p a r a L o o p

E x i t :(0 Exercicio 3.9 trata da otimizacao desta sequencia.)

Os testes de igualdade ou desigualdade talvez sejam os mais populares de todos os testes de condicao, mas as vezes e pre-ciso verificar se 0valor de determinada variavel e menor que 0valor de outra. Por exemplo, urn loop for pode precisar realizarurn teste para verificar se 0 valor corrente do Indice e menor que O.Tais comparacoes, no c6digo do MIPS, sao realizadas comuma instrucao que compara os valores de dois registradores e atribui 0 valor Ia urn terceiro, se 0 valor do primeiro registradorfor menor que 0do segundo; caso contrario, atribui-se 0valor 0 a esse terceiro registrador. Esta instrucao do MIPS e chamadade instrucao set on less than, au s 1 t..Por exemplo,

s l t $ t O , $ s 3 , $ s 4


17/69


significa que 0 registrador $t 0 assume 0 valor 1 caso 0 conteiido do registrador $s 3 seja menor que 0 valor armazenado em$ s 4 ; caso contrario, 0 registrador $t 0 recebe 0 valor O .

InterfaceHardware/SoftwareOs compiladores que geram codigo para 0MIPS usam as instrucoes s 1t, b nee beq, e 0valor fixo $ze ro, disponfvel no regis-trador read only denominado $z e r 0, para criar todas as demais condicoes relativas: igual, nao-igual, menor que, menor ou iguala, maior que, maior ou igual a. (Como seria de se esperar, 0registrador $z e r o e mapeado no registrador 0.)

Compila~ao do Teste less ThanExemplo

Qual 0codigo MIPS para testar se uma var iavel a, correspondente ao registrador $sO, e menor que outra var iavel b (registrador $s 1 )e desviar para 0 label Le s s se a condicao for verdadeira?

Soluc;aoo primeiro passo e usar a instrucao set on less associada a urn registrador temporario:slt $tO,$sO,$sl # reg $tO recebe 1 se $sO < $sl (a < b)

Ap6s a execucao dessa instrucao, 0 registrador $t 0 recebe 0 valor 1 se a for menor que b. Portanto, uma instrucao de desviopara verificar se0conteiido de $tU e nulo tera 0mesmo efeito de urn desvio se a e menor que b. Considerando que 0registrador$ z e r 0 contem sempre 0 valor 0 armazenado, este ultimo teste e realizado a partir de uma instrucao bn e para comparar $ tocom $zero:# desvia para Less se $tO * 0I f (isto e , se a < b)

Portanto, este par de instrucoes, S 1 t e b n e, implementa urn J desvio se menor que.bne $tO, $zero, Less

Seguindo 0conselho de von Neumann sobre a simplicidade do "equipamento", a arquitetura do MIPS nao inclui em seu conjun-to de instrucoes a instrucao branch if less than, porque sua implementacao e muito complicada: para te-la no conjunto de instru-90es, seria necessario aumentar 0ciclo do clock ou implementa-la gastando muitos ciclos de clock, 0que aumentaria a quantidademedia de ciclos gastos por instrucao. Em vez de uma instrucao 1enta, e melhor duas instrucoes rapidas.

Coman do Case/SwitchA maioria das linguagens de programacao tern urn comando case ou switch que permite ao programador selecionar uma de mui-tas alternativas, dependendo do valor de uma iinica variavel. Umjeito de implementar 0comando switch e partir de uma sequen-cia de testescondicionais, transformando este comando em uma cadeia de comandos if-then-else. Porem, isto nem sempre funcionabern, porque as vezes as alternativas vern codificadas como uma tabela de enderecos de sequencias alternativas de instrucoes,chamadas tabela de enderecos de desvio, e 0programa so precisa indexar esta tabela, e entao desviar para a sequencia de instru-90es desejada. A tabe1a de desvios nada mais e que urn array de palavras contendo enderecos que correspondem a labels dentrodo c6digo.Para suportar esta situacao, maquinas como 0MIPS possuem uma instrucao de desvio a conteiido de registrador (j r), signi-ficando urn desvio incondicional para 0endereco armazenado no registrador especificado pela instrucao. 0 programa carrega aentrada apropriada a partir da tabela de desvios em urn registrador, e entao desvia para 0endereco apropriado atraves da instru-9ao jr.

Compila~ao de um Comando switch a Partir de uma Tabela de Endere~os de DesvioExemploEsta versao escrita em C de urn comando case e chamada de comando switch. 0c6digo a seguir escolhe entre quatro alternati-vas, dependendo do valor assumido pela variavel k, cujo domfnio de variacao e 0, 1,2 ou 3.


18/69

lnstrucoes Basicas: A Linguagem da Maqulna 6

S w i t c h ( k ) {c a s e 0: f = i + J: b r e a k ; 1* k 0 *1c a s e 1: f = g + h ; b r e a k ; 1* k 1 *1c a s e 2 : f = g h ; b r e a k ; 1* k 2 *1c a s e 3 : f = i j; b r e a k ; 1* k 3 *1

Suponha que as seis variaveis de f a k correspondam aos seis registradores de $ s 0 a $ S5 , e que 0registrador $ t 2 contenhavalor 4. Qual 0 c6digo correspondente na linguagem de montagem do MIPS?Solu~aoVamos utilizar a variavel k, do comando switch, para indexar uma tabela de enderecos de desvio, e entao desviar com basno valor carregado. Primeiro testamos 0valor de k para ter certeza de que ele e igual a urn dos valores do comando case (~ k ~ 3); se nao, 0 programa abandona 0 comando switch.

sltb n esltb e q$ t 3 , $ s 5 , $ z e r o$ t 3 , $ z e r o , E x i tH 3 , $ s 5 , H 2H 3 , $ z e r o , E x i t

i f t e s t a s e k < 0i f s e k < 0, d e s v i a p a r a E x i t: f / : t e s t a s e k < 4i f s e k >= 4, d e s v i a p a r a E x i t

Uma vez que estamos usando a variavel k para indexar urna tabela contendo palavras de memoria, precis amos primeiro multiplicar seu valor por 4 para transforma-lo em urn endereco de byte:a d da d d

H l , $ s 5 , $ s 5H I , H I , $ t l i f R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 2 * kif R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e 4 * k

Suponha que quatro palavras consecutivas na memoria, comecando no endereco armazenado em $ t 4 , tenham enderecos correspondentes aos labels L 0, L 1, L 2 e L 3 . Podemos, portanto, carregar 0 endereco do desvio em urn registrador, no caso $ t oconforme mostramos a seguir:a d d $ t l , H l . $ t 4l w H O , O ( $ t l ) if R e g i s t r a d o r t e m p o r a r i o $ t l r e c e b e e n d e r e ~ o d e J u m p T a b l e [ k ]if R e g i s t r a d o r t e m p o r a r i o $ t O r e c e b e J u m p T a b l e [ k ]

A execucao de uma instrucao de desvio para 0contetido de urn registrador faz com que 0programa passe a executar a instrucaoapontada na tabela de enderecos de desvio.

J r $ t O i f d e s v i a c o m b a s e n o c o n t e O d o d o r e g $ t OAs tres primeiras opcoes do comando switch deste exemplo tern a mesma estrutura: urn label, urna tinica instrucao para executao comando case, e finalmente urn desvio para fora do comando switch:

L O : a d d $ s O , $ s 3 , $ s 4 i f k = o p o r t a n t o f r e c e b e i + jj E x i t i f f i m d e s t e case p o r t a n t o d e s v i a p a r a E x i tLl: a d d $ s O , $ s l , $ s 2 i f k = 1 p o r t a n t o f r e c e b e 9 + hj E x i t i f f i m d e s t e case p o r t a n t o d e s v i a p a r a E x i tL 2 : s u b $ s O , $ s l , $ s 2 i f k = 2 p o r t a n t o f r e c e b e 9 - hj E x i t i f f i m d e s t e case p o r t a n t o d e s v i a p a r a E x i tUrn exemplo mais complexo poderia ter varias instrucoes para cada case.Voltando ao nosso exemplo, no ultimo case podemos eliminar 0 desvio para a safda do comando switch, pois as instrucoesdeste case sao as ultimas do switch. Devemos, no entanto, pendurar urn label E x it depois do ultimo comando deste case parmarcar 0 final do comando switch:L 3 : s u b $ s O , $ s 3 , $ s 4E x i t :

i f k = 3 p o r t a n t o f r e c e b e i - ji f f i m d e s t e c o m a n d o switch

A Figura 3.9 resume as partes da linguagem de montagem do MIPS descritas nesta secao. Esta fase do processo de evolucao daprendizado desta linguagem acrescentou a nossa representacao simb6lica os desvios condicionais e incondicionais, alem de mostrar as vantagens de termos 0 valor 0 armazenado permanentemente em urn registrador.Elaborac;ao: Se voce ja tiver ouvido falar a respeito dos desvios atrasados e estiver preocupado com a complexidade do conceito, nao h a motivopara preoeupar-se: 0montador do MIPS torna este conee i to invisivel ao programador da linguagem de montagem. Alern disto, vale um aviso paraos prograrnadores C que nao estiverem familiarizados com 0uso do coman do go to: sua execucao simplesmente transfere 0controle do programada instrucao go to para a instrucao armazenada no endersco constante do label do go to.


19/69

70 Organizat,;ao & Projeto de Computadores - A Interface Hardware/Software

Operandos do MIPS

32 registradores isO, $sl,HO, HI. $s7H7, $zero Poslcoss de acesso rapldo para armazenamento de dados. No MIPS, os dados devem estarem regis tradores para que as operacoes antmetlcas possam ser realizadas. Osregistradores $ s - $ s 7 sao mapeados nos registradores reais de nurnero 16-23 e osregistradores $t - $t7nos de numero 8-15. 0 registrador $zero do MIPS sempre temo valor 0 armazenado nele .230 palavrasde memoria Memoria[O],Memoria[4], "',Memoria[4294967292]

No MIPS, estas poslcoes so sao acessadas por lnstrucoes de transterencla de dados. 0MIPS enderec;:a byte , de modo que enderec; :os de palavras consecutivas d iferem de4 unidades. A memor ia armazena estruturas de dados, como arrays, alem dosregistradores "derramados".


Aritrnetica add add s si,$s2, $s3 $sl s s z + $s3

$sl

Compare se men or ou igual; usada junto abeq ea bne

subtract sub s s t , $s2, $s3 $sl $s2 $s3Tres operandos; dados em regislradoresTres operandos; dados em registradores

Transferenciade dados load wordlw ss l , 100($s2) $sl Mem6ria[$s2 + 100J Dados t ransfer idos da memoria para

registradoresstore word sw ss i,100($s2) Memoria[$s2 + 100J Dados transfer idos de registradores para amemoria

Desviocondlcional

branch on equal beq $sl, $s2, L se ($sl = = $s2)desvia para L Testar a igualdade e desviar se verdadeirabranch on notequal bne $sl, $s2, L se ($sl != $s2)desvia para L Testar a desigualdade e desviar severdadeira

Desvioincondicional

s u b

set on less than

R

sIt $sl, $s2,

lwsw

5ne

1917171818

Linguagem de rnaqulna do MIPS

17 o100

25

17It R o 19

Formato RForrmato I

J 2

rsrs

2500

rt rd shamt

$sl

34

42

funct

1;

sub $sl, ssz. $s3

sIt $sl, $82, $s3j 10000 (veja Segao 3_8)

Figura 3.9 Arquitetura do MIPS introduzida na Segao 3.5. As partes em negrito mostram as estruturas da linguagem de montagem do MIPS introduzidas na Secao3.5.0 formato J, usado nas instrucoes de desvio incondicional, e explicado na Sec; :ao3.8.A Secao 3.8tambem expl ica os valores do campo de endereco das instru-90es de desvio condicional.

rt enderec;:o

do MIPS tern 32 bits

Formato das lnstrucces de transferencla de dados


20/69

lnstrucoes Basicas: A Linguagem da Maquina 7

3.6 Suporte a Procedimentos pelo Hardware da MaquinaUrn procedimento, ou sub-rotina, e uma ferramenta para estruturacao de programas muito utilizada pelos programadores. Sao doos objetivos que motivam 0uso de urn procedimento: tornar 0programa mais facil de ser entendido e possibilitar a reutilizacao dcodigo do procedimento. 0 conceito de procedimento perrnite que 0programador se concentre em uma tinica parte do codigocada vez, sendo que os parametres funcionam como uma barreira entre 0procedimento e 0 resto do programa e os dados, permitindo que sejam passados valores do programa para 0 procedimento e que sejam recebidos pelo programa os resultados do processamento no procedimento.Voce pode imaginar 0 trabalho de urn procedimento fazendo analogia com 0 trabalho de urn espiao que precisa executar uplano secreto e que, para isto, adquire os recursos necessaries, realiza a tarefa exigida sem deixar pistas e volta ao ponto de origemcom os resultados esperados, para entrega-Ios ao contratante do service. Vale observar que todo espiao que se preza trabalha smente com as informacoes estritamente necessarias ao cumprimento da sua missao. Portanto, ele nao pergunta quem 0 contratopara executar 0 trabalho.Analogamente, durante a execucao de urn procedimento, 0programa e 0procedimento precisam executar os seis passos seguintes:1. Colocar os parametres em urn lugar onde eles possam ser acessados pelo procedimento.2. Transferir 0controle para 0procedimento.3. Garantir os recursos de mem6ria necessaries a execucao do procedimento.4. Realizar a tarefa desejada.5. Colocar 0 resultado em urn lugar acessfvel ao programa que chamou 0procedimento.6. Retornar 0 controle para 0 ponto de origem.Conforme mencionamos anteriormente, os registradores sao 0meio mais rapido de se armazenarem dados em urn computadorportanto, sempre que possivel, devemos usa-los para tal fim. Por esse motivo, 0 software do MIPS utiliza os seguintes registradoresna implementacao da chamada a procedimento:II $ a 0-$ a 3: quatro registradores para argumento, atraves dos quais sao passados parametres do programa para 0procedimento.. $ v0-$ vl : dois registradores para retorno de valores do procedimento para 0 programa.. $ r a: urn registrador que content sempre 0endereco para 0qual 0controle deve retornar ao final da execucao do procedimento. Em outras palavras, este registrador contem 0 endereco para 0procedimento retornar ao chamado ponto de origem.Alern de alocar esses registradores, a linguagem de montagem do MIPS possui uma instrucao usada unicamente por procedi

mentos, que faz exatamente 0 seguinte: desvia para urn endereco e simultaneamente salva 0 endereco da instrucao seguinte nregistrador $ r a. Esta instrucao e a jump and link (j a 1), cujo formato em linguagem de montagem e 0 seguinte:j a l E n d er e ~ o - do - P ro c e d i me n t oA parte do link do nome da instrucao tern por objetivo indicar que essa instrucao e composta por urn endereco ou urlink, que aponta para 0 local onde se originou a chamada, para permitir que 0procedimento, no final de sua execucao, retornpara 0 endereco correto. 0 valor desse "link", armazenado no registrador $ r a, e chamado de endereco de retorno. Observe quo conceito de endereco de retorno permite que 0procedimento seja chamado de qualquer parte do programa, retornando semprao local certo.A ideia do programa armazenado tern como pressuposto basico a necessidade de urn registrador para armazenar 0 conteudo dinstrucao corrente. Por razoes historicas, este registrador e quase sempre chamado de program counter, abreviado como PC narquitetura do MIPS, embora urn nome mais apropriado para ele talvez fosse instruction address register. A instrucao ja 1 salvavalor de PC +4 no registrador $ r a para estabelecer 0 link do fun do procedimento com a instrucao seguinte a ela.A instrucao para fazer 0 desvio de retorno ja e nossa conhecida:jr $ raA instrucao de desvio para conteudo de registrador, que ja foi usada anteriormente no comando switch, desvia para 0 enderecoarmazenado no registrador $ r a - 0que resolve 0nosso problema. Entao, em resurno, 0programa que chama 0procedimento, ochamador, coloca os valores dos parametres nos registradores $ a0-$ a 3, e usa a instrucao ja 1 Xpara desviar para 0procedimen-

to X(as vezes referido como procedimento chamado). Este Ultimo procedimento efetua 0processamento necessario, armazena oresultados em $ V0-$ vI e retorna 0 controle para 0 procedimento chamador, usando jr $ r a.

Utiliza~aode mais RegistradoresSuponha que, ao ser compilado, urn procedimento precise de mais do que os quatro registradores reservados para os argumentosAlem disso, 0procedimento chamado tambem precisa retornar mais de dois val ores ao procedimento chamador. Mais, lembre-sede que nos nos comprometemos a destruir todas as pistas ap6s completar a nossa missao, de modo que qualquer registrador usadpelo procedimento chamador deve ter seus valores restaurados, ou seja, deixados na condicao anterior a chamada. Esta situacaourn exemplo em que e necessario aumentar virtualmente a quantidade de registradores disponiveis, evidentemente usando a memoria, conforme mencionamos na ultima Interface Hardware/Software da Secao 3.3.


21/69


Fica claro que a pilha e a estrutura de dados ideal para aumentar virtualmente a quantidade de registradores disponfveis. Sabe-mos que a pilha implementa uma estrutura LIFO (Last In First Out, ou "lJltimo a Entrar, Primeiro a Sair") e que, por isto, ela pre-cisa de urn ponteiro para 0endereco que tenha sido incorporado a ela mais recentemente. Desse modo, 0procedimento que precisarde mais registradores do que os normalmente disponibilizados para argumentos e resultados, deve colocar na pilha, a partir doendereco apontado como topo da pilha, os valores correspondentes aos registradores adicionais. Em resumo, 0topo da pilha mostrao endereco a partir do qual os valores correspondentes aos registradores excedentes devem ser colocados, ou onde os valores anti-gos devem ser buscados. 0apontador de topo da pilha deve ser ajustado de uma palavra para cada registrador salvo ou recuperado.As pilhas sao estruturas tao conhecidas que tern seu proprio vocabulario para indicar a transferencia de dados de/para a pilha: co-locar dados na pilha e identificado neste vocabulario proprio como sendo uma operacao de push. J a a operacao de remover urn dadoda pilha e conhecida como pop.o software do MIPS aloca urn outro de seus registradores para ajudar na operacao de pilhas: 0 stack pointer, ou apontador depilha ($ Sp), usado para armazenar 0 valor do endereco do topo da pilha, endereco este usado pelo procedimento chamado paraguardar os valores dos registradores adicionais necessaries a sua correta execucao. Por razoes historicas, as pilhas sempre "cres-cern" dos enderecos mais altos para os mais baixos. Esta convencao significa que, se voce executar urn push para a pilha - colo-cacao de valores -, 0 valor corrente do stack pointer deve diminuir. Adicionar valores ao stack pointer e sinonimo de encolher 0tamanho da pilha, e portanto de retirar valores da pilha.

Oompllacao de um Procedimento que Nao Chama Outro ProcedimentoExemploVamos transformar em urn procedimento 0 trecho de programa do exemplo que demos na Secao 3.2, item Compilacao de umaDeclaracao C Complexa.int leaf_example (int g. int h, int i, int j){

int f;f = (g + h) - (i + j);return f;

Para 0 restante desta seciio, vamos supor que podemos somar ou subtrair valores como 4, 8 ()U 12 ao conteudo de determinadoregistrador. (A Secao 3.8 mostra como a linguagem de montagem do MIPS trata as constantes.) Qual 0 codigo gerado pelocompilador para tal procedimento na linguagem de montagem do MIPS?Solu~aoAs variaveis g, h, i e j, passadas como parametres, correspondem aos registradores $a 0, $a 1, $a 2 e $a 3, respectivamente,e f, 0 resultado, corresponde ao registrador $sO. 0 codigo gerado pelo compilador comeca comleaf_example:

o proximo passo consiste no salvamento dos registradores a serem usados pelo procedimento. 0 comando de atribuicao no corpodo procedimento e identico ao do exemplo da Se~ao 3.2, item Compilacao de uma Declaracao C Complexa, que utiliza doisregistradores temporaries. Entao, precisamos salvar tres registradores: $sO, $tOe $t 1. Vamos criar espaco para tres palavrasna pilha, e entao armazenar nesse espaco os valores correntes desses registradores:sub $sp,$sp,12sw s t l , 8($sp)sw $tO, 4($sp)sw $sO, O($sp)

# ajusta a pilha para abrir espa~o para guardar 3 itens# salva 0 conteOdo do registrador $tl com 0 objetivo de preserva-lo# salva 0 conteOdo do registrador $tO com 0 objetivo de preserva-lo# salva 0 conteOdo do registrador $sO com 0 objetivo de preserva-loA Figura 3.10 mostra a pilha antes, durante e depois da chamada ao procedimento. Os tres comandos seguintes correspondem aocorpo do procedimento, e sao apresentados a seguir, identicos ao exemplo da Secao 3.2 citado anteriormente.addaddsub

$tO,$aO,$als t l , $a2, $a3$sO,$tO,$tl# registrador $tO cont~m 9 + h# registrador $tl cont~m i + ji f f recebe $tO - s t l . que e (g + h) - (i + j)o valor de retorno, a ser armazenado em f, sent copiado em urn dos registradores especfficos para esse tipo de funcao, os cha-mados registradores de valor:

add $vO,$sO,$zero i f retorna f ($vO recebe $sO + 0)


22/69

Mem6ria alta

$ s p

Mem6ria baixa a.


s s p

$ s p

b. c.Figura 3.10Valores do stack pointer e da pilha (a) antes, (b) durante e (c) depois da chamada a procedimento. 0 stack pointer aponta sempre para 0 "topo" dpilha, ou para a ultima palavra arrnazenada na pilha.

Antes de retornar ao programa que chamou 0procedimento, devemos restaurar os valores dos registradores utilizados durantea execucao deste procedimento, para fazer com que eles adquiram os valores anteriores a chamada e, entao, que a pilha volte aoseus valores originais:lwlwlwadd

$sO, O($sp)$tO, 4($sp)s tl , 8($sp)$sp,$sp,12# restaura 0 valor de $sO para 0 chamador# restaura 0 valor de $tO para 0 chamador# restaura 0 valor de $tl para 0 chamador# ajusta a pilha de modo a remover os 3 itens

o procedimento termina com a execucao de uma instrucao de desvio para 0 conteiido de registrador, utilizando 0 registrador$ r a , que contem 0 endereco de retorno:jr $ra # desvia de volta para 0 programa que chamou

No exemplo anterior, utilizamos registradores temporaries e partimos do pressuposto de que seus valores antigos precisavamser salvos e depois recuperados. Para evitar tanto 0 salvamento quanto a recuperacao de registradores cujos valores nao serao usados, fato que pode acontecer com frequencia no caso dos registradores temporaries, 0 software do MIPS oferece duas classes dregistradores:

III $tO-$t9: 10 registradores temporaries que ndo sao preservados pelo procedimento chamado, quando de uma chamadaprocedimentoIII $ S 0-$ s 7: 8 registradores de salvamento que precisam ser preservados quando de uma chamada a procedimento (se usadoso procedimento chamado salva seus valores e depois os restaura)

Esta simples convencao reduz a necessidade de registradores virtuais, ou seja, daqueles registradores que precis am ser guarda-dos na pilha por causa do grande mimero de parametres e/ou de resultados envolvidos no processo de chamada a procedimen-to. No caso anterior, por exemplo, 0procedimento chamador nao esperava que os registradores $ tOe $ t 1 tivessem seus valores preservados, ap6s a chamada ao procedimento; portanto, podemos eliminar duas instrucoes de load e duas de store doc6digo gerado. No entanto, precisamos preservar 0 valor de $s 0, pois, pel a convencao, 0 procedimento chamado sabe quechamador precisa do valor original deste registrador.

Procedimentos AninhadosProcedimentos que nao chamam outros procedimentos sao chamados de procedimentos-folha. A vida seria muito mais simplesse todosos procedimentos fossem folhas, mas isto nao e verdade. Assim como urn espiao pode empregar outros espioes pararealizar parte da sua missao, e esses espioes "terceirizados" tambem podem buscar ajuda de outros espioes, tambem os procedi-mentos podem chamar outros procedimentos. Alem disso, os procedimentos recursivos chamam "clones" deles mesmos. Se japrecisamos ser cautelosos ao usar registradores em procedimentos- folha, e necessario redobrar esses cuidados ao chamar proce-dimentos nao-folha.Suponha, por exemplo, que 0programa principal chame urn procedimento A, com urn argumento 3, colocando este valor noregistrador $a 0, e entao execute j alA. Depois disso, suponha que 0 procedimento A chame urn procedimento B executandoa instrucao j a 1 8, com urn argumento 7, tambem colocado em $a O. Como A ainda nao terminou sua tarefa ao chamar Bhavera urn conflito no uso do registrador $a O. De maneira analoga, teremos problemas com 0 usa do conteiido de $ r a, poiseste registrador agora possui 0 endereco de retorno de B, escrito em cima do endereco de A (lembre-se de que A ainda naoterminou sua execucao), A nao ser que gastemos algumas linhas de programacao para evitar tais conflitos, teremos muitos pro-blemas para equacionar essas chamadas, como por exemplo fazer com que 0procedimento A retorne a quem 0chamou.


23/69


Uma solucao para isto e colocar na pilha todos os registradores que precisem ser preservados, a exemplo do que fizemos com osregistradores de salvamento. 0procedimento chamador coloca na pilha todos os registradores de argumento ($ a 0-$ a 3) ou regis-tradores temporaries ($ t 0-$ t 9) que sejam necessaries apos a chamada. 0 procedimento chamado coloca na pilha 0endereco deretorno, armazenado em $ r a, e todos os registradores de salvamento usados por ele ($ s 0-$ s 7).0 stack pointer $ S P e ajustadopara acomodar a quantidade de registradores colocados na pilha. Quando do retorno, os valores dos registradores sao restauradosa partir da pilha, e 0 stack pointer tambem volta ao seu valor inicial.Cornpllaeao de um Procedimento Recursivo Mostrando a Ligac;ao entreProcedimentos AninhadosExemploVamos analisar um procedimento recursivo para calculo do fatorial, escrito em C, e apresentado a seguir:

int fact (int n)if (n < 1) return (1);else return ( n * fact(n- 1);

Suponha que voce pode somar ou subtrair constantes com valores 1 ou 4 ao contetido de registradores, conforme sera mostradona Se~ao 3.8. Qual 0 codigo, em linguagem de montagem do MIPS, gerado pelo compilador?Solut;aooparametro passado atraves da variavel n corresponde ao registrador de argumento $a O.0 programa compilado comeca como label do procedimento, para depois salvar dois registradores na pilha, 0 $ rae 0 $a0 :fact:

subswsw$sp,$sp,8$ra, 4($sp)$aO, O($sp)

i f ajusta a pilha para receber 2 itensi f salva 0 endere~o de retornoi f salva 0 argumento nDa primeira vez que fa c t for chamado, a instrucao s wsalva um endereco no programa que chamou fa ct. As duas instrucoesseguintes testam se n e menor que 1, desviando para L1 se n ;;;, 1.

sltbeq $tO,$aO,l$tO, $zero, L1 i f testa se n < 1if se n >= I, desvia para L1Se n for menor que 1, fa c t retorna 0valor 1,colocando 1no registrador de valor. Para tanto, ele soma 1com 0e coloca 0resultadoem $vO.Depois disso ele retira dois valores de registradores de salvamento da pilha e desvia para 0endereco de retorno:

add $vO,$zero,l if retorna 0 valor 1add $ s p , $ s p, 8 if eli min a 2 itens d a pilhajr $ra if retorna para depois da instru~~o jalAntes de retirar os dois valores da pilha, devemos verificar se nao houve necessidade de carregar $a 0 e $r a . Em consequenciade $ a 0 e $ r a nao mudarem quando n e menor que 1, podemos pular essas instrucoes.Se n nao for menor que 1,0argumento n e decrementado, e entao fa c t e chamado novamente com 0valor ja decrementado:L1: sub $aO,$aO,l if n >= 1: argumento recebe (n - 1)jal fact if chama fact com argumento (n - 1)

A proxima instrucao e onde fa c t retorna. Agora, 0 endereco de retorno e 0 argumento antigos sao restaurados, junto com 0stack pointer:lw $aO, O($sp)lw sr e . 4($sp)add $sp, $sp,8

i f retorna de jal: restaura argumento ni f restaura 0 endere~o de retornoi f ajusta 0 stack pointer para eliminar 2 i tensA seguir, 0registrador de valor $v0 recebe 0produto do argumento antigo, $a 0 e 0valor corrente do registrador de valor. Vamossupor que a instrucao de multiplicacao esteja disponivel, mesmo considerando que ela so sera estudada no Capitulo 4:

mult $vO,$aO,$vO i f retorna n * fact (n - 1)Finalmente, fa c t desvia novamente para 0 endereco de retorno:

jr $ra i f retorna para 0 chamador


24/69


Registradores de salvamento: $s0-$ s7 Registradores temporaries: $ t 0-$ t 9Registrador stack pointer: $ s pRegistrador de enderec;;o de retorno: $ r a

Registradores de argumento: $a0-$ a3Registradores de retorno de valores: $ v 0-$ v 1

Figura 3.11 0 que e e 0 que nao e preservado quando de uma chamada a procedimento. Se 0 software usar 0 registrador frame pointer ou 0 global pointediseutidos nas proximas secoes, eles tambem devem ser preservados.

A Figura 3.11 apresenta urn resumo daquilo que deve ser preservado quando de uma chamada a procedimento. Note que podemos usar varies esquemas para preservar a pilha. Os valores da pilha situados acima do $ s p sao preservados simplesmentegarantirmos que 0procedimento chamado nao vai escrever na regiao acima do $s p: $s p e preservado pelo procedimento chamado adicionando a ele exatamente a mesma quantidade que the foi subtraida, ao passo que os demais registradores sao preservadose salvarmos seus valores na pilha (se eles tiverem sido usados) e restaurarmos tais valores a partir de laoEstas acoes tambem grantem que 0 chamador vai receber de volta 0mesmo dado que ele guardou na pilha por meio de urn store, quando executar urload: faz parte das prernissas do procedimento chamado preservar $ S P e, como consequencia dele, nao mudar a parte da pilhpertencente ao chamador, ou seja, a area acima de $ s p no momenta da chamada.Alccacao de Espayo para Novos DadosPara complicar ainda mais as coisas, a pilha tambem e usada para guardar variaveis que sao locais ao procedimento e que, poserem numerosas, nao podem ser armazenadas nos registradores, a exemplo de arrays locais ou outras estruturas de dados. 0 segmento da pilha que contem os registradores de salvamento do procedimento e suas variaveis locais e chamado de quadro do procedimento, ou registro de ativaciio. A Figura 3.12 mostra 0estado da pilha antes, durante e depois da chamada ao procedimento.Alguns softwares do MIPS usam urn registrador apontador de quadro - frame pointer ($ fp) - para apontar para 0quadro durn procedimento. 0 contetido do registrador $ s p pode mudar durante a execucao do proeedimento, e, portanto, as referenciasuma varia vel local na mem6ria podem ter diferentes deslocamentos, dependendo de onde elas estao no proeedimento, tomandoproeedimento mais diffeil de ser entendido. Por outro lado, 0 frame pointer oferece-se como urn registrador-base estavel para a

Mem6ria alta

Mem6ria baixa

$ f p

$fp

$f p

$ S p

a .

$ s p

0.

$ s p

C.Figura a. tz nustracao da alocalfao de espaco na pilha, (a) antes, (b) durante e (c) depois da chamada a procedimento. 0 frame pointer ($ fp) aponta paraprimeira palavra do frame. geralrnente urn registrador-argumento salvo na pilha, e 0 stack pointer ($ s p) aponta sempre para 0 topo da pilha . A pi lha e ajustada padar lugar a todos os registradores a serem salvos. e a qualquer variavel local residente na memoria . Considerando que 0stack pointer pode mudar durante a execucado programa, e mais facil para os programadores referenciar variaveis por meio do frame pointer, cujo valor e estavel, ernbora isto tambem possa ser feito por medo stack pointer e de urn poueo de aritmetica envolvendo 0endereco, Se nao houver variaveis loeais na pilba dentro de um procedirnento, 0compilador vai ganhatempo ao ndo inicializar e restaurar 0 frame pointer. Quando 0 frame pointer e usado; ele e in icializado a partir do endereco do $ s p em uma chamada, sendo $ srestaurado com a utilizacao de $ fp.


25/69

76 Orqaruzacao & Projeto de Computadores - A Interface Hardware/Software

$zero 0 valor da constante 0 n.-a.$vO-$vl 2-3 valores para guardar resultados e para avaliar express6es nao$aO-$a3 4-7 argumentos sim$tO-tt7 8-15 temporaries naosalvos sim$t8-$t9 24-25 mais temporaries nao$gp 28 global pointer sim$sp 29 stack pointer sim$fp 30 frame pointer sim

de retorno a simFigura 3.13Conven~o do MIPSpara utiliza~iio de registradores. 0 registrador 1, chamado $ at, e reservado para 0montador (veja Secao3.9), e os registradores26-27, chamados $ k0 - $ k1, sao reservados para 0 sistema operacional.

variaveis locais a um procedimento referenciarem a memoria. Observe que urn registro de ativacao aparece ou nao em uma pilha,dependendo se urn frame pointer explfcito for usado. Temos evitado 0 $ fp, nao modificando 0 $ s p dentro de urn procedimento:em nossos exemplos a pilha so e ajustada no inicio e no fim de urn procedimento.A Figura 3.13 resume as convencoes empregadas para utilizar os registradores de maneira racional pela linguagem de montagem doMIPS e a Figura 3.14 apresenta, de maneira resumida, as partes do conjunto de instrucoes basicas do MIPS descritas ate agora.Elabora{:ao: 0 que acontece se existirem mais de quatro parametres? Lembre-se de que a convencao do MIPS estabelece que os parametresextras devem ser colocados na pilha imediatamente acima do frame pointer. Entao 0procedimento obtern os primeiros quatro parametres dos re-gistradores $ a 0 a $ a3, e os demais da pilha, atravss do frame pointer.Conforme mencionamos na legenda da Figura 3.12, 0 usa do frame pointer e conveniente porque todas as reterenclas a varlaveis na pilha,dentro de um procedimento, terao 0mesmo deslocamento. No entanto, e tacil notar que 0 frame pointer e dispensavel, apesar de muito util: 0compilador C GNU MIPS utiliza este recurso, mas 0C da Silicon Graphics, que gera c6digo para 0MIPS, nao usa: em vez disso, utihza 0 registradornumero 30 como urn outro registrador de salvamento ($ s8).Elabora{:ao: A lnstrucao ja1 na verdade salva em $ r a 0endereco da lnstrucao armazenada na palavra seguinte ao enderec;:oonde ela esta arma-zenada, permitindo que 0 retorno de um procedimento se de simplesmente com a execucao de jr $ r a.'

InterfaceHardware/SoftwareUma variavel de urn programa em C e , em ultima analise, uma posicao de memoria, e sua interpretacao depende tanto do seu tipoquanta da sua classe de armazenamento. Os tipos serao discutidos detalhadamente no Capitulo 4, mas os exemplos incluem tiposinteiros e caracteres. A linguagem C tem duas classes de armazenamento: a automatica e a estatica. Variaveis automaticas sao 10-cais a um procedimento, e sao descartadas quando 0procedimento termina. As variaveis estaticas sobrevivem aos procedimentos.As variaveis da linguagem C declaradas fora de todos os procedimentos sao consideradas estaticas pelo compilador, assim comoqualquer variavel dec1arada que use a palavra-chave s tat ic. As demais sao automaticas. Para simplificar 0 acesso aos dadosestaticos,o software do MIPS utiliza urn outro registrador, denominado apontador global (global pointer), ou $ 9 p.Na

Documents

Instruções Básicas A Linguagem Maquina