Do A Ssa

Apresentando a SSA (Static Single Assignment) Eduardo Spaki1 1

DIN – Departamento de Inform´atica da Universidade Estadual de Maring´a (UEM) Maring´a – PR – Brazil [email protected]

Abstract. In this paper, it is explaining the SSA optimization technique, a optimization technique for compilers, which improves many others algorithms of optimization. The explain shows some of its details (as the concept and the idea of the technique), readings and criticals about the same, having as a base the vision of some authors. It will be showed how to around the obscure situations, as points of decisions, with the φ-functions. Some algorithms to use the SSA Form will be quickly explained, tracing a parallel among source code, flow graph and dominance tree. In the paper it will be also improved importance of the technique and its use. Resumo. Neste artigo, e´ explicada a t´ecnica de otimizac¸a˜ o SSA, uma t´ecnica de otimizac¸a˜ o para compiladores, a qual beneficia muitos outros algoritmos de otimizac¸a˜ o. A explicac¸a˜ o abordar´a alguns de seus detalhes (como o conceito e a concepc¸a˜ o da t´ecnica), leituras e cr´ıticas sobre a mesma, baseando-se na vis˜ao de alguns autores. Ser´a exposto como contornar as situac¸o˜ es obscuras, como pontos de tomadas de decis˜ao, com as φ-functions. Alguns algoritmos para a adoc¸a˜ o da forma SSA ser˜ao brevemente explicados, tranc¸ando um paralelo entre c´odigo fonte, fluxo de controle e arvore de dominˆancia. No artigo ser´a ressaltada tamb´em a importˆancia da t´ecnica e a adoc¸a˜ o da mesma.

1. Introduc¸a˜ o A SSA, ou Static Single Assignment, e´ uma das in´umeras t´ecnicas de otimizac¸a˜ o que podem ser aplicadas e implementadas em um compilador. E´ uma t´ecnica independente de linguagem e processadores (arquitetura), pois ela e´ aplicada em uma representac¸a˜ o intermedi´aria da compilac¸a˜ o. Logo ap´os a aplicac¸a˜ o da SSA, e as otimizac¸o˜ es que se beneficiam dela, e´ necess´ario ”desfazer” a SSA para o c´odigo ser representado adequadamente no hardware. Ela foi concebida na d´ecada de 80 nos laborat´orio de pesquisa da IBM, com a finalidade de simplificar o fluxo de controle e tornar mais f´acil a adoc¸a˜ o de t´ecnicas que s˜ao beneficiadas pela declarac¸a˜ o u´ nica de uma vari´avel. Antigamente algumas otimizac¸o˜ es neste sentido eram feitas utilizando uma t´ecnica chamada def-use chain, que e´ uma eficiente estrutura de dados que cont´em o campo de uso de cada vari´avel e para cada declarac¸a˜ o o compilador mant´em os ponteiros da vari´avel, segundo Appel (1998), mantendo assim cada definic¸a˜ o das vari´aveis aos usos que cada uma alcanc¸a.

2. Definic¸a˜ o Neste conceito de otimizac¸a˜ o, cada vari´avel, que pode ser chamada de ”pseudoregistrador”, e´ atribu´ıda apenas uma u´ nica vez, e cada uso da vari´avel e´ dominado pela definic¸a˜ o dela. Isto viabiliza uma an´alise mais r´apida do c´odigo, tornando mais eficiente e f´acil aplicar outras otimizac¸o˜ es. Com a SSA e´ mais f´acil criar um grafo de fluxo de controle, ou controle de dependencia, e at´e mesmo uma an´alise de data-flow. Com a simplificac¸a˜ o realizada pelo formato SSA, apenas uma u´ nica definic¸a˜ o pode alcanc¸ar um uso particular da vari´avel, assim, achar a tal definic¸a˜ o e´ trivial. Ela tamb´em permite algoritmos, insens´ıveis ao fluxo, gozar dos benef´ıcios de algoritmos sens´ıveis ao fluxo, sem o custo de an´alises de fluxo de dados. Esta t´ecnica foi originalmente desenvolvida por Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, and Ken Zadeck. Eles eram pesquisadores da IBM na d´ecada de 80.

3. Detalhes Um simples exemplo de atribuic¸o˜ es pode ilustrar o ganho que h´a na an´alise de um c´odigo com SSA, como no algoritmo a seguir:

A = 1; A = 2; B = A;

Neste exemplo, a l´ogica e´ que a primeira linha, ou seja, a primeira atribuic¸a˜ o e´ dispens´avel. Assim, o valor que ir´a alimentar a vari´avel ”B” prov´em da ”segunda miss˜ao” da vari´avel ”A”. Para um compilador identificar esta otimizac¸a˜ o, teria de criar um grafo do fluxo da aplicac¸a˜ o e analis´a-lo. A SSA acaba individualizando as vari´aveis e seus usos. Logo, a identificac¸a˜ o do fluxo e as tarefas que ser˜ao otimizadas, tornam-se evidentes:

A1 = 1; A2 = 2; B1 = A2 ; Neste caso, um algoritmo de ”eliminac¸a˜ o de c´odigo morto” (detalhes sobre esta tecnica ser˜ao melhores detalhados neste artigo) se beneficiaria ao identificar a ”inatividade” de ”A1 ”.

4. Os Algoritmos Mayers (2003, p. 3) define SSA como um conceito que explicita o fluxo de informac¸o˜ es de dados de um determinado programa, concentrando na maneira como e´ realizada a definic¸a˜ o (ou seja, atribuic¸a˜ o) e uso de vari´aveis.

Briggs (p. 1) apresenta que a SSA e´ uma representac¸a˜ o intermedi´aria que os compiladores utilizam para facilitar a an´alise do aplicativo e beneficia as otimizac¸o˜ es. Appel (1998, p. 443) exp˜oe que muitas an´alises de dataflow precisam encontrar as dominancias de cada definic¸a˜ o de vari´avel, e que para isto existe o def-use chain. Mas este autor apresenta a SSA como uma melhoria desta ideia, definindo-a como ”uma representac¸a˜ o intermedi´aria na qual cada vari´avel tem apenas uma definic¸a˜ o no texto do programa”. O autor Mayers (2003) ressalta que h´a complicac¸o˜ es evidentes quando h´a fluxos de controles (tomadas de decis˜oes com if, lac¸os com um for, etc.). A Figura 1 demonstra o fluxo de controle do algoritmo proposto.

Figure 1. Fluxo de controle do algoritmo proposto

Logo, deve ocorrer a definic¸a˜ o de uma estrat´egia para portar a aplicac¸a˜ o para a forma SSA. Segundo o autor (MAYER, 2003), h´a dois passos fundamentais para a adoc¸a˜ o da SSA. O primeiro passo fundamental que Mayers apresenta e´ uma declarac¸a˜ o especial, chamada de φ-function. Esta func¸a˜ o, que ser´a tratada com mais detalhes neste artigo, basicamente cuidar´a dos n´os propostos no algoritmo, representando as possibilidades, do uso de uma vari´avel numerada, perante uma bifurcac¸a˜ o. O segundo e´ a re-nomeac¸a˜ o das vari´aveis de acordo com sua dominˆancia. Ambos os passos citados podem ser vistos na Figura 2. Foi levantada ent˜ao uma fase inicial, a identificac¸a˜ o das necessidades das φfunction, e suas aplicac¸o˜ es. A Figura 3 demonstra outro algoritmo passando pelas trˆes fases. Com isto, e´ preciso propor soluc¸o˜ es pr´aticas para que algoritmos sejam aplicados aos c´odigos para port´a-los para o SSA. Mayers (2003) apresenta algumas quest˜oes, melhorando-as, al´em de propor dois algoritmos para as mesmas. Mayers (2003), ressalta tamb´em que h´a m´etodos e t´ecnicas espec´ıficas para lidar facilmente com arrays e records e Appel extende isto at´e os ponteiros.

˜ de variaveis ´ Figure 2. Renomeac¸ao

Figure 3. Fases da SSA

4.1. Tratando os Arrays Uma atribuic¸a˜ o de um array para outro, por exemplo, pode ser tratada com uma atribuic¸a˜ o entre vari´aveis escalares. No entanto, as atribuic¸o˜ es dos arrays, muitas vezes tomam a forma de atribuic¸o˜ es de um elemento da matriz. Mas, mesmo neste caso, a id´eia e´ usar a matriz (array) como uma vari´avel escalar. Para realizar as operac¸o˜ es em arrays, Mayes (2003) ilustra m´etodos como: Acesso (Access) e Atualizar (Update) - veja a Figura 4: 4.2. Tratando os Records A fim de ajustar as estruturas records para o a forma SSA, podemos aplicar a mesma t´ecnica, citada para os arrays, considerando o registro como uma matriz e os campos de registro como elementos da matriz.

˜ de Arrays Figure 4. Manipulac¸ao

4.3. Ponteiros e dependˆencia de mem´oria Appel (1998) exp˜oe os controles citados por Mayers como Armazenar (store) e Carregar (load). Esta forma acaba fazendo sentido, pois, para o autor, um programa real deve ler e armazenar words no mem´oria. Ambas as t´enicas s˜ao maneiras de acessar registros alocados dentro de uma colec¸a˜ o, seja ela a mem´oria ou uma matriz. Para muitas propostas de otimizac¸a˜ o e escalonamento, o compilador precisa saber ”como a declarac¸a˜ o B depende da declarac¸a˜ o A?” Para a forma SSA nunca ocorrera uma situac¸a˜ o onde as declarac¸o˜ es ”A” e ”B” escrevem na mesma vari´avel. Ent˜ao, com esta dependˆencia de mem´oria, o compilador tem que assegurar que cada alocac¸a˜ o de memoria deve ser escrita uma u´ nica vez. Para uma melhor compreens˜ao, considere o c´odigo a seguir:

M[i] = 4; x = M[j]; M[k] = j;

N˜ao h´a como tratar cada posic¸a˜ o da mem´oria individualmente, como uma vari´avel separada, porque n˜ao ha como saber se i, j, e k e´ o mesmo enderec¸o. Mas e´ poss´ıvel tratar a mem´oria como uma ”vari´avel”, onde a instruc¸a˜ o load cria um novo valor (da mem´oria inteira), acompanhe o rac´ıoc´ınio no c´odigo a seguir:

M1 = store(M0 , i, 4); x = load(M1 , j); M2 = store(M1 , k, j); E mesmo se uma outra tecnica de otimizac¸a˜ o re-ordenar as declarac¸o˜ e, do c´odigo proposto, o acesso a mem´oria permanece correto. Acompanhe a l´ogica:

M1 = store(M0 , i, 4);

M2 = store(M1 , k, j); x = load(M1 , j); Appel (1998) propˆos esta soluc¸a˜ o que acaba, como Mayers, cobrindo de maneira semelhante, tendo a u´ nica alterac¸a˜ o no nome dos m´etodos, ou func¸o˜ es, que tratam a leitura e atribuic¸a˜ o de valores em estruturas como matrizes e outras estruturas mantidas em mem´oria, como ponteiros. 4.4. Fronteira de Dominˆancias O primeiro algoritmo e´ a Fronteira de Dominˆancias (Dominance Frontiers). A id´eia e´ calcular fronteiras de dominˆancia e ent˜ao us´a-las para determinar onde colocar φ-functions. O conceito de dominˆancia pode ser compreendido em dizer que um n´o ”B” domina um n´o diferente, no grafo de fluxo de controle, se for imposs´ıvel chegar em ”B” sem passar por este outro n´o, nem que seja uma u´ nica vez. Isso e´ u´ til, porque se alguma vez chegar a ”B”, fica v´alida a id´eia de que o c´odigo da dominˆancia de B foi executado. Para definir as fronteiras de dominˆancia, um n´o ”B” estar´a na fronteira de dominˆancia de um n´o ”A” se ”A” terminantemente n˜ao dominar ”B”, mas n˜ao dominam alguns antecessores imediatos de ”B”. As fronteiras de dominˆancia capturam os locais exatos que devem ser colocadas as φ-functions. A definic¸a˜ o de uma vari´avel ”V” e´ dita um dom´ınio da utilizac¸a˜ o de ”V”, se o uso pode ser rastreado at´e uma definic¸a˜ o u´ nica. No entanto, ao entrar nos fluxos de controle, a vari´avel apresentar´a v´arias definic¸o˜ es, conseq¨uentemente novos dom´ınios. S˜ao estas as fronteiras dinˆamicas (pois depende do fluxo que a aplicac¸a˜ o tomar durante sua execuc¸a˜ o), e e´ nestes locais que deve ser inserida a φ-function. Veja na Figura 5 um exemplo de Fronteira de Dominˆancia:

ˆ Figure 5. Fronteira de Dominancia

Repare que n˜ao h´a como chegar nos n´os circulados, sem antes passar pelo n´o

denominado ”5”, os n´os dentro da fronteira do n´o ”5”, por sua vez, estabeleciriam suas pr´oprias fronteiras de dominˆancia, evitando assim que o n´o ”5” englobe todos os n´os. Para tal t´ecninca evoluir dentro da SSA, e´ preciso determinar a a´ rvore de dominˆancia, que pode ser constru´ıda com propriedades do fluxo de controle correspondente. Os n´os da a´ rvore e do fluxo de controle s˜ao idˆenticos, segundo Mayers (2003), e as bordas da a´ rvore s˜ao determinadas usando a propriedade de dominˆancia imediata do fluxo de controle como e´ demonstrado na Figura 6.

´ ˆ Figure 6. Arvore de Dominancia

Compreendido o conceito da fronteira dinˆamica, Mayers (2003) prop˜oe algoritmos de Cytron que provaram que DF(X) pode ser expressa como uma uni˜ao de dois subconjuntos, DFlocal e DFup, e que ambos os subgrupos podem ser calculados com testes simples, usando a igualdade de informac¸o˜ es do fluxo de controle e da a´ rvore de dominˆancia. Para a a´ rvore proposta, seu estudo de computac¸a˜ o prevˆe que ela poderia ser computada da maneira representada na Figura 7. Uma vez realizada a computac¸a˜ o, seu resultado indicaria a inclus˜ao das φfunctions e a re-nomeac¸a˜ o de vari´aveis. A Figura 8 exemplifica um algoritmo proposto para computar o conjunto da Fronteira de Dominˆancia. Este algoritmo foi originalmente proposto por Cytron, autor j´a citados pelos autores nos quais este artigo se baseia. Neste c´odigo um antecessor do n´o ”n” e´ qualquer n´o do qual o controle e´ transferido para o n´o ”n”, e ”IDOM (n)” e´ o dominador imediato do n´o ”n”. 4.5. Gerac¸a˜ o Simples de SSA O segundo algoritmo proposto por Mayers (2003) prov´em de um estudo que ele fez em materiais de 1997, dos autores Aycock e Horspool. Trata-se da Gerac¸a˜ o Simples de SSA (Simple Generation of SSA Form).

˜ da arvore ´ ˆ Figure 7. Computac¸ao de dominancia proposta

E´ um algoritmo de duas fases, que se baseia na simples id´eia: primeiro devem ser inseridas as φ-funcions quando poss´ıvel. Em seguida, iterativamente, excluir aquelas que n˜ao s˜ao necess´arias. A primeira fase do algoritmo e´ chamada de RC, onde ser˜ao distribu´ıdas as func¸o˜ es φ livremente. A segunda e´ a fase de minimizac¸a˜ o das func¸o˜ es φ, ou seja, e´ feita uma limpa das func¸o˜ es, tentanto otimizar as chamadas da mesma, como pode ser visto na Figura 9. O autor (Mayer, 2003) complementa que Aycock and Horspool prop˜oe otimizac¸o˜ es neste algoritmo, como: One-pass RC phase, Mapping table. Basic blocks with single predecessors. Mayers (2003) conclui que os algoritmos para SSA propostos por Cytron, Aycock e Horspool s˜ao eficientes e que o SSA se tornou uma t´ecnica padr˜ao, amplamente utilizada, relembrando, inclusive, sua implementac¸a˜ o no compilador GNU, o GCC.

5. Compreendendo melhor a φ-funcion Quando h´a mais de um caminho que pode ser tomado em um c´odigo, devido a algum fluxo de controle, como tomadas de decis˜ao ou loops, fica obscuro determinar a declarac¸a˜ o u´ nica das vari´aveis. Por exemplo: em um if-then-else uma vari´avel ”V” pode assumir um valor no if e outro no else. A princ´ıpio n˜ao h´a como saber qual a definic¸a˜ o que ela

ˆ Figure 8. Algoritmo proposto para computar as Fronteiras de Dominancias

˜ das φ-funcions Figure 9. Minimizac¸ao

assumiu. Para suprir esta necessidade e´ que foi introduzida a func¸a˜ o φ. Segundo Appel (1998, p. 434-435) ela exp˜oe as vari´aveis resultantes do n´o. Appel (1998) prop˜oe uma soluc¸a˜ o para convers˜ao de um programa para a forma SSA muito pr´oxima a Gerac¸a˜ o Simples de SSA citada por Mayers (2003), na qual primeiramente deve-se adicionar as φ-functions e, em seguida, re-nomear as vari´aveis.

6. Uma alternativa a φ-funcion O autor Briggs prop˜oe uma alternativa para as φ-funcions.Trata-se das ”C´opias” (Copies). Briggs prop˜oe isto baseando-se na id´eia de que raramente algum computador tenha um hardware capaz de representar e executar as φ-funcions.Com isto os compiladores j´a acabam fazendo a c´opia naturalmente. Por´em e´ poss´ıvel refin´a-la com a Colorac¸a˜ o de Grafos do Fluxo de controle. Briggs ressalta que a Colorac¸a˜ o de Grafos, n˜ao e´ uma tarefa trivial, mas se n˜ao for executada adequadamente o compilador pode executar o ”copy folding” ingenuamente, levando a erros. Briggs monta o algoritmo da Figura 10 para escalonar o suo das C´opias, definidas pelo mesmo.

7. O Uso e Aplicac¸a˜ o da SSA Como j´a mencionado no artigo, a forma SSA e´ utilizada para a otimizac¸a˜ o do programa em um compilador. Segundo Mayers (2003) as seguintes otimizac¸o˜ es podem se beneficiar de SSA Form. 7.1. Propagac¸a˜ o de Constante A propagac¸a˜ o de contante (Constant Propagatio) avalia uma constante e propaga esta informac¸a˜ o a todos os locais no c´odigo onde existe uma vari´avel que a representaa. Assim ocorreria a eliminac¸a˜ o de vari´aveis, deixando seus valores expl´ıcitos no c´odigo. Veja um c´odigo apresentado por Mayers (2003) na Figura 11. 7.2. Eliminac¸a˜ o de Redundˆancia Parcial Basicamente, a Eliminac¸a˜ o de Redundˆancia Parcial (Elimination of Partial Redundancies) e´ a eliminac¸a˜ o de c´alculos que s˜ao realizados duas, ou mais, vezes com os mesmos valores de entrada e sa´ıda. Veja outro exemplo que o Mayers (2003) fornece na Figura 12. 7.3. Deslocamento de C´odigo O Deslocamento de C´odigo (Code Motion) e´ uma outra t´ecnica para evitar c´alculos desnecess´arios de valores em tempo de execuc¸a˜ o, principalmente dentro de lac¸os de repetic¸a˜ o. Al´em disso, introduz vari´aveis tempor´arias para armazenar valores calculados, visando inicializ´a-los em locais adequados no c´odigo. Uma estrat´egia, denominada de deslocamento de c´odigo seguro, e´ colocar estes inicializac¸o˜ es o mais cedo poss´ıvel. A Lazy, ao contr´ario, coloca o inicializac¸o˜ es t˜ao tarde quanto poss´ıvel, visando a otimizac¸a˜ o computacional, ou seja, Lazy atrasaria ao m´aximo a inicializac¸a˜ o de um valor, at´e que o valor fosse realmente necess´ario para a continuac¸a˜ o do programa. Esta estrat´egia resulta em uma vida u´ til m´ınima das vari´aveis tempor´arias. Na Figura 13 e´ demonstrada a traduc¸a˜ o do c´odigo para a forma SSA, tornando poss´ıvel passar a atribuic¸a˜ o a execuc¸a˜ o de algumas tarefas apenas uma u´ nica vez. 7.4. Eliminac¸a˜ o de C´odigo Morto Eliminac¸a˜ o de C´odigo Morto (Dead Code Elimination) e´ a eliminac¸a˜ o de c´odigos que s˜ao computados mas n˜ao alteram nada relevante para o resultado e/ou ambiente. S˜ao c´odigos ineficazes. Acompanhe na Figura 14.

8. Retornando da Forma SSA Ap´os a transformac¸a˜ o e otimizac¸a˜ o do c´odigo, um programa na forma SSA deve ser traduzido em uma representac¸a˜ o execut´avel, retirando as φ-funcions, segundo Appel (1998). A SSA acaba n˜ao sendo mais u´ til na execuc¸a˜ o direta, logo as func¸o˜ es de mapeamento, sobre as quais a SSA foi fundada, podem ser descartadas. Assim restar´a uma

representac¸a˜ o intermedi´aria otimizada. Al´em disto, como j´a citado, a φ-funcion geralmente n˜ao e´ reconhecida pelo hardware. Existem v´arias formas de sair da forma SSA. Briggs, que exp˜oe a limitac¸a˜ o das φ-funcions perante o hardware, cita o uso de ”C´opias” sobre a representac¸a˜ o do grafo de interferˆencia.

9. Curiosidades O compilador GCC, a partir da sua vers˜ao 4.0 (Julho de 2005) introduziu em suas otimizac¸o˜ es a SSA. Antes, a representac¸a˜ o intermedi´aria gerada por ele era chamada de RTL (Register Transfer Language). A RTL e´ uma representac¸a˜ o de n´ıvel baixo, muito pr´oxima a` linguagem assembly (inspirada pelas express˜oes LISP S). O problema com a RTL e´ que as otimizac¸o˜ es que ela permite s˜ao muito pr´oximas ao destino. As otimizac¸o˜ es que requerem informac¸o˜ es de n´ıvel maior sobre o programa podem n˜ao ser poss´ıveis, pois suas express˜oes s˜ao perdidas na RTL. A a´ rvore SSA foi criada para ser independente de linguagem e de destino, suportando ainda an´alises melhoradas e otimizac¸o˜ es mais valiosas. (IBM, Sec¸a˜ o Conhecendo o GCC 4, 2008) E´ importante ressaltar que, por ser independente de linguagens, a t´ecnica n˜ao se limita apenas a` s linguagens imperativas. Alguns algoritmos de otimizac¸a˜ o s˜ao diretamente beneficiados pelo SSA, como: constant propagation , sparse conditional constant propagation, dead code elimination, global value numbering, partial redundancy elimination, strength reduction, register allocation. Alguns destes descritos neste artigo.

10. Cr´ıtica Os autores, j´a citados, em momento algum apresentaram um hist´orico mais preciso da t´ecnica SSA. A conseq¨ueˆ ncia e´ a falta de clareza na hora de ressaltar os reais benef´ıcios da t´ecnica diretamente ligada ao produto final da compilac¸a˜ o. Assim ficou apenas demonstrado que a t´ecnica beneficia outros algoritmos de otimizac¸a˜ o de c´odigo, pois a SSA simplifica a analise de fluxo de controle do c´odigo, evidenciando o tempo de vida das vari´aveis. Isto fez com que a SSA adquirisse uma classificac¸a˜ o de t´ecnica auxiliar. A SSA e´ uma t´ecnica que tem que ser aplicada, e spos os processamento de c´odigo pertinentes, deve-se ”retir´a-la de cena”. Isto acaba comprometendo o tempo de compilac¸a˜ o. Assim, algumas plataformas, que pr´ovem uma recompilac¸a˜ o de c´odigo, ap´os uma an´alise do comportamento da aplicac¸a˜ o, para melhorar o desempenho de algumas rotinas, acabam n˜ao se beneficiando tanto desta t´ecninca, pois o tempo de compilac¸a˜ o acaba embutido no tempo de execuc¸a˜ o . Os autores poderiam ter deixado claro se a SSA sozinho traz algum benef´ıcio ao produto final do compilador. Al´em disto, pela falta de precis˜ao do hist´orico, n˜ao ficou claro qual foi o real motivo que impulsionou os pesquisadores da IBM a desenvolver algo desta natureza.

Os autores tamb´em ficaram devendo mais exemplos da evoluc¸a˜ o de um c´odigo normal para um otimizado, passando pela SSA. Al´em disto poderiam ter trac¸ado exemplos colocando lado a lado a SSA e o use-def Chain.

11. Estudos Futuros Estudar a aplicac¸a˜ o da SSA em Linguagens que rodam sobre um ambiente de execuc¸a˜ o pr´oprio, como JAVA com a JVM (Java Virtual Machine) e C# com a CLI (Common Language Infrastructure). Assim ser´a poss´ıvel estudar em um n´ıvel mais alto a SSA, al´em de verificar os ganhos de an´alise de c´odigo para otimizac¸a˜ o da compilac¸a˜ o, pois em muitos casos, estes ambientes acabam embutindo a compilac¸a˜ o no tempo de execuc¸a˜ o (JIT - Just in Time), criando assim, uma oportunidade de realizar algumas avaliac¸o˜ es emp´ıricas. Trac¸ar um paralelo entre a SSA aplicada a linguagens compiladas (C, C++, Pascal etc.) e linguagens compiladas em tempo de execuc¸a˜ o de acordo com seu ambiente de execuc¸a˜ o (JAVA, C# etc.). O objetivo e´ identificar onde h´a maior ganho, al´em de verificar se h´a uma necessidade de aplicar a t´ecnica em ambas as fazes: compilac¸a˜ o para o ambiente e compilac¸a˜ o para a m´aquina. Para tal, torna-se fundamental, a estruturac¸a˜ o dos c´odigos propostos, como o de escalonamento de c´opias e o c´alculo da dominˆancia de fronteiras, em uma linguagem real, criando asssim a possibilidade de aplic´a-las em um compilador e/ou ferramenta. Com isto, ser´a poss´ıvel realizar testes reais, uma avaliac¸a˜ o emp´ırica, e um debbug para a melhor compreens˜ao dos algoritmos.

12. Conclus˜ao A SSA e´ um conceito que simplifica a adoc¸a˜ o de outras t´ecnicas de otimizac¸a˜ o. Estas por sua vez, implicam diretamente na otimizac¸a˜ o de c´odigos e na aplicac¸a˜ o final, melhorandoa em v´arios sentidos, como: tamanho final da aplicac¸a˜ o, performance, melhor uso de hardware etc. Foi ressaltado que a SSA e´ uma t´ecnica onde deve ocorrer um retorno para uma representac¸a˜ o simples do c´odigo, devido a falta de suporte (de hardware) para algumas caracter´ısticas da forma SSA, como as φ-funcions. Ficou claro tamb´em que um dos alicerces principais, da t´ecninca SSA, est´a nas φ-funcions, que garantem o suo correto de vari´aveis nas bifurcac¸o˜ es do c´odigo. O Artigo apresentou algumas das t´ecnicas que se beneficiam da SSA, explicando seus conceitos e ilustrando a evoluc¸a˜ , partindo da convers˜ao para a SSA at´e chegar na otimizac¸a˜ o, como foi o casa do Code Motion. Para tal, houve cr´ıticas a autores citados no artigo por ignorarem as origens da t´ecnica e comprometer uma aplicac¸a˜ o moderna da t´ecnica, devido ao d´eficit da proposta inicial da SSA. Logo foi proposto um novo estudo, onde seriam analisados dados provenientes da aplicac¸a˜ o da SSA nos compiladores de plataformas como o JAVA e o C#, estudando o comportamento do c´odigo e desempenho da aplicac¸a˜ o, quando a t´ecnica for aplicada na gerac¸a˜ o de byetecode, por exemplo.

References APPEL, Andrew W. (1998). Moder Compiler Implementation in C. England: Cambridge University. BRIGGS, Preston et. Al. (s\d) Practical Improvements to the Construction and Destruction of Static Single Assignment Form. Tera Computer Company. CYTRON, R. et. Al. (1989) Efficiently computing static single assignment form and the control dependence graph. ACM Trans. GCC. Sec¸a˜ o GNU Compiler Collection. Dispon´ıvel em: . Acesso em: 5 nov. 2009 a` s 9h10. Sec¸a˜ o Conhecendo o GCC 4, 28 out. 2008. . Acesso em: 05 nov. 2009 a` s 8h. MAYER, Sabine. (2003). Static Single-Assignment Form and Two Algorithms for its Generation. University of Konstanz. WIKIPEDIA. Sec¸a˜ o Static Single Assignment Form. . nov. 2009 a` s 9h.

Dispon´ıvel em: Acesso em: 5

˜ de copias ´ Figure 10. Algoritmo para escalonamento de inserc¸ao

˜ de Constante Figure 11. Propagac¸ao

˜ de Redundancia ˆ Figure 12. Eliminac¸ao Parcial

˜ do Deslocamento de Codigo ´ Figure 13. Aplicac¸ao

´ Figure 14. Codigo Morto