Construção de Compiladores II
Aula 10 – Geração de Código e Otimização
Andrei de A. Formiga
24 de maio de 2006
1
Introdução
2
Nı́veis de otimização
tido.
Este processo pode ser realizado em vários nı́veis
A geração de código pode ser simples, mas o re- de localidade. Algumas redundâncias só podem ser
sultado é invariavelmente ineficiente e desperdiça notadas se observarmos o código de uma rotina
os recursos computacionais disponı́veis, tanto em (função ou procedimento) inteira, enquanto para
termos de tempo quanto de espaço.
outros tipos de ineficiência mesmo isso não é o suUm módulo atual de geração de código deve ficiente.
tratar de dois problemas importantes: alocação
O nı́vel mais local de otimização que pode ser
de registradores e seleção de instruções. Como feito é analisar cada instrução do código gerado, ina resolução desses problemas envolve técnicas de dividualmente, procurando por ineficiências. Nesse
otimização, vale a pena estudar os dois tópicos de caso, são poucas as redundâncias que podem ser
geração de código nativo e otimização de forma observadas, pois a análise não pode nem comparar
conjunta. Um compilador pode inclusive juntar ou duas instruções próximas. Por isso mesmo, este
mesclar os dois módulos, o que é comum em várias tipo de análise extremamente localizada não cosorganizações das fases de sı́ntese.
tuma ser usada em compiladores reais. Os nı́veis
Nesta aula veremos as técnicas mais importantes que costumam ser observados em compiladores são
relacionadas à otimização e geração de código na- os seguintes:
tivo, principalmente em relação à alocação de registradores e seleção de instruções. Se o objetivo for
1. Otimização por janela
o de criar um módulo de geração de código mais
simples, que não faça a alocação de registradores
2. Otimização de blocos básicos
e seleção de instruções, pode-se utilizar as técnicas
já estudadas anteriormente, gerando código direta3. Otimização global (intra-procedural)
mente a partir da árvore sintática.
Começaremos estudando os nı́veis de otimização
4. Otimização inter-procedural
disponı́veis, e quais técnicas são comumente usadas
em cada nı́vel. Em seguida veremos como se faz a
5. Otimização de programa inteiro
alocação de registradores e seleção de instruções.
Cada nı́vel envolve uma análise mais global que
o anterior, e portanto consegue perceber mais redundâncias no código, e assim obter código de melhor qualidade. Em contrapartida, cada nı́vel é mais
complexo de implementar e torna a compilação
mais demorada, um fator que não deve ser desconsiderado. As seções a seguir detalham cada um
desses nı́veis, e que técnicas são usadas em cada
um deles.
O processo de otimização consiste em procurar redundâncias e ineficiências no código gerado e eliminar tais problemas, trocando trechos de código
problemático por versões melhores, mas equivalentes. A equivalência é uma necessidade absoluta,
claro, pois o significado do programa deve ser man1
2.1
R2 := R1 + #5
i := R2
R3 := i
R3 := R3 * #3
Otimização por janela
Neste nı́vel a análise é feita em um conjunto de instruções de número pré-determinado, normalmente
três ou mais. O compilador analisa cada grupo
de instruções separadamente, como se estivesse
deslizando uma janela pelo código. Embora ainda
bastante localizado, neste nı́vel já é possı́vel eliminar muitas redundâncias e ineficiências, e isso faz
com que muitos compiladores façam esse tipo de
otimização.
As técnicas usadas na otimização por janela são
muitas vezes usadas em outros nı́veis também, de
forma mais abrangente. Por isso, é interessante
ver exemplos destas técnicas primeiro no nı́vel mais
simples, e depois estudar como elas são aplicadas
em nı́veis mais abrangentes.
Em geral, cada técnica permite eliminar uma ou
mais instruções, em geral poucas, mesmo porque a
análise é bastante localizada. Mesmo assim, essas
melhorias podem resultar em uma diferença significativa no desempenho de um programa. Podemos
imaginar, por exemplo, que uma melhoria dessas
consiga eliminar apenas uma instrução de um loop
que é executado por um milhão de iterações; neste
caso, a otimização vai resultar na execução de um
milhão de instruções a menos.
A seguir, cada técnica é explicada e exemplificada.
R2 := R1 + #5
i := R2
R3 := R2 * #3
Figura 1: Eliminação de transferências
2.1.2
Desdobramento de constantes
Uma análise que pode ser feita mesmo no nı́vel das
instruções individuais, o desdobramento de constantes consiste em detectar expressões constantes,
que podem ser efetuadas em tempo de compilação,
e substituir as instruções para o cálculo da expressão pelo seu resultado constante, eliminando
uma ou mais instruções aritméticas e/ou lógicas.
Esta é uma otimização bastante simples mas que
pode bons ganhos de eficiência. Na figura 2 vemos
um exemplo simples: a expressão que é atribuı́da a
R3 a instrução à esquerda é constante, e pode ser
calculada durante a compilação, usando a instrução
à direita em seu lugar.
R3 := #2 * #3
R3 := #6
Figura 2: Desdobramento de constantes
2.1.3
Propagação de constantes
Em alguns casos a análise pode detectar que um
registrador ou variável terá um valor constante em
algum ponto do programa. Nestes casos, o comEm muitos casos, é possı́vel saber que uma in- pilador pode substituir ocorrências do registrador
strução de transferência da memória para um reg- ou variável pela constante, diretamente. Isso pode
istrador, ou de um registrador para a memória, é simplificar instruções de transferência e mesmo
desnecessária. Como a geração de código a par- eliminar algumas. Na figura 3, à esquerda, vemos
tir da árvore sintática é totalmente local, esse tipo um exemplo em que o registrador R2 recebe o valor
de redundância pode ocorrer com freqüencia. Ao constante 4 apenas para ser utilizado na próxima
analisar uma janela do código, o compilador pode instrução, que define o valor de R3. Como o compiremover essas instruções desnecessárias. A figura lador pode determinar que R2 tem o valor 4 na se1 mostra um exemplo deste processo: à esquerda gunda instrução, é possı́vel substituir a ocorrência
vemos o código antes da melhoria; é fácil notar que de R2 na expressão diretamente pelo seu valor. Em
R2 e R3 têm o mesmo valor, e que R3 depois re- seguida, detecta-se que o valor de R2 como 4 só
cebe outro valor, o que indica que a instrução de era usado nesta segunda instrução, e portanto toda
transferência para R3 é desnecessária. Na parte à a primeira instrução pode ser eliminada. O resuldireita da figura está o código melhorado, após a tado após a melhoria é mostrado na parte direita
eliminação da instrução de transferência para R3 da figura.
A técnica de propagação de constantes interage
e a alteração da última instrução para usar R2 ao
fortemente com o desdobramento de constantes.
invés de R3.
2.1.1
Eliminação de instruções de transferência redundantes
2
R2 := #4
R3 := R1 + R2
R2 := R4
R2 := R1 * #5
R2 := R2 + R3
R3 := R1 * #5
R3 := R1 + #4
R2 := R4
Figura 5: Eliminação de expressões comuns
Figura 3: Propagação de constantes
2.1.5
Muitas vezes, o uso de uma delas pode criar uma
oportunidade para usar a outra. Um exemplo pode
ser visto na figura 4, com o código original à esquerda. O primeiro passo é fazer propagação de
constantes, trocando a ocorrência de R1 na segunda
instrução pelo seu valor, 3. Em seguida, o desdobramento de constantes pode ser utilizado para
substituir a expressão 3 × 2 pelo seu resultado,
6; por fim, assumindo que o valor de R1 não é
necessário para instruções subseqüentes, a primeira
instrução pode ser eliminada, resultando no código
à direita. No total, uma instrução foi completamente eliminada e a outra foi simplificada de uma
operação aritmética para uma mais simples, apenas
de transferência.
R1 := #3
R2 := R1 * #2
Propagação de cópias
Mesmo em alguns casos quando não é possı́vel
determinar que um registrador terá valor constante em um ponto do programa, pode-se observar que ele terá o mesmo valor de algum outro
registrador. Neste caso, o compilador pode substituir os usos de um registrador pelo outro, desde
que nenhum dos dois tenha seu valor alterado. A
figura 6, à esquerda, mostra o código original, no
qual R1 e R2 possuem o mesmo valor, graças à
primeira instrução. Com isso, pode-se substituir
a ocorrência de R2 por R1 na segunda instrução;
adicionalmente, como o valor de R2 é redefinido
na terceira instrução, pode-se eliminar completamente a primeira, resultando no código melhorado
mostrado à direita na figura. O uso da propagação
de cópias pode reduzir o número total de registradores utilizados pelo código intermediário, o
que simplifica a tarefa do alocador de registradores
na geração de código nativo.
R2 := #6
Figura 4: Propagação e desdobramento de constantes
2.1.4
R4 := R1 * #5
R2 := R4 + R3
R3 := R4
R2 := R1
R3 := R1 + R2
R2 := #5
R3 := R1 + R1
R2 := #5
Figura 6: Propagação de cópias
Eliminação de sub-expressões comuns
Quando uma mesma sub-expressão ocorre duas
ou mais vezes dentro da janela de otimização, é
freqüentemente possı́vel fazer o cálculo só uma vez e
reaproveitar seu resultado. Na figura 5, à esquerda,
o código calcula a expressão R1 * #5 duas vezes,
uma vez na atribuição a R2 e outra na atribuição
a R3; uma melhoria, neste caso, é calcular a expressão apenas uma vez e reaproveitar seu resultado. Para isso, como o valor de R2 muda na segunda instrução, é necessário usar um outro registrador. O código à direita mostra a melhoria
aplicada, usando R4 para guardar o valor da subexpressão comum. É interessante observar que a
expressão só é calculada uma vez, mas foi necessário
usar um registrador a mais para isso.
2.1.6
Redução de força
Em muitas situações é possı́vel trocar uma instrução mais demorada por outra, mais rápida, mas
que tem o mesmo efeito. Por exemplo, multiplicar
R1 por 2 é o mesmo que somar R1 com ele mesmo;
o resultado é o mesmo, mas em muitas arquiteturas uma soma é mais rápida do que uma multiplicação. A mesma coisa pode ser feita com multiplicações e divisões por potências de 2, que podem ser substituı́das por deslocamentos de bits,
instruções muito mais eficientes. Um exemplo é
mostrado na figura 7. As duas instruções à esquerda são melhoradas para as instruções à direita:
uma multiplicação é trocada por uma soma, e uma
3
figura 8, e sua tradução para código intermediário
é mostrada novamente na figura 9.
outra multiplicação é substituı́da por um deslocamento à esquerda. A seqüência da direita executará
muito mais rápido.
R1 := R2 * #2
R3 := R4 * 4
int mdc(int a, int b)
{
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
R1 := R2 + R2
R3 := R4 << 2
Figura 7: Redução de força
2.2
Otimização por blocos básicos
A otimização por janela consegue bons resultados
para eliminar as redundâncias mais gritantes no
código gerado, mas não pode detectar problemas
no código que se mostram em instruções que caiam fora da mesma janela. Por exemplo, se uma
instrução apresenta uma redundância em relação
a uma outra instrução que está a 10 instruções de
distância, e o tamanho da janela é 5, nenhuma melhoria neste código será possı́vel.
O próximo nı́vel de otimização é o que analisa
blocos básicos, ao invés de janelas simples. Um
bloco básico é um trecho do código gerado que inicia
com uma instrução rotulada – ou seja, o destino de
algum desvio – e termina com algum desvio, condicional ou incondicional. A importância de um bloco
básico para a análise do código é que o controle só
entra em um bloco básico pelo inı́cio, e só deixa
o bloco básico no final. Assim, é possı́vel saber
exatamente quais instruções serão executadas no
bloco, e em que seqüencia. Se existissem desvios
condicionais dentro do bloco, seria impossı́vel determinar a próxima instrução após a execução do
desvio, e isso tornaria muito difı́cil determinar que
um registrador possui um valor constante, por exemplo, ou as outras informações necessárias para
qualquer otimização.
As regras para identificar os blocos básicos são
simples:
return a;
}
Figura 8: Cálculo do MDC na linguagem C
WHILE:
THEN:
FIMIF:
FIMW:
R0 := 100
R1 := 104
IF NOT R0 != R1 GOTO FIMW
R2 := 100
R3 := 104
IF R2 > R3 GOTO THEN
R4 := 100
R5 := 104
R6 := R4 - R5
100 := R6
GOTO FIMIF
R7 := 100
R8 := 104
R9 := R8 - R7
104 := R9
GOTO WHILE
RET
Figura 9: Cálculo do MDC em código intermediário
O começo do código na figura 9 marca o inı́cio
do primeiro bloco básico, que se extende até o
primeiro desvio condicional, na terceira linha. O
próximo bloco básico inicia na quarta linha e vai
até o próximo desvio condicional, e assim o processo
continua na delimitação dos blocos, até chegar à divisão em blocos mostrada na figura 10.
Depois de dividir o código em blocos básicos,
o compilador pode analisar cada bloco básico de
maneira indivisı́vel, já que o bloco sempre é execu-
1. Uma instrução rotulada marca o inı́cio de um
novo bloco básico, terminando o anterior
2. Um desvio marca o fim do bloco básico atual, começando um novo bloco na instrução
seguinte
Para um exemplo, retornamos à função para calcular o máximo divisor comum, mostrada na aula
passada. O código da função em C é repetido na
4
WHILE:
THEN:
FIMIF:
FIMW:
istrador, e em caso negativo, ela é gravada na tabela
associada ao registrador da instrução analisada.
Esse processo de numeração de valores identifica sub-expressões repetidas, realiza a propagação
de cópia e propagação de constantes dentro do
bloco básico, e ainda possibilita também a redução
de força de instruções. Também pode-se utilizar
a numeração de valores para guardar o resultado
de expressões constantes, ao invés de apenas registradores, com o intuito de aplicar o desdobramento de constantes. Finalmente, a eliminação
de instruções de transferência redundantes é conseguida naturalmente, pois o compilador sabe que
valores estão em que registradores, podendo eliminar transferências redundantes de valores já presentes na tabela.
Com esse tipo de análise por numeração
de valores, a otimização por janela torna-se
desnecessária, em geral, embora ainda possa ser usada principalmente para realizar algumas reduções
de força que não são detectadas pela análise por
numeração de valores.
R0 := 100
R1 := 104
IF NOT R0 != R1 GOTO FIMW
R2 := 100
R3 := 104
IF R2 > R3 GOTO THEN
R4 := 100
R5 := 104
R6 := R4 - R5
100 := R6
GOTO FIMIF
R7 := 100
R8 := 104
R9 := R8 - R7
104 := R9
GOTO WHILE
RET
Figura 10: Divisão do código para MDC em blocos
básicos
tado inteiramente. O objetivo das análises é minimizar o número de instruções de transferência e
identificar cálculos redundantes. Existem algumas
técnicas para fazer isso, mas para nossos propósitos
aqui podemos usar a numeração de valores.
Numeração de valores consiste em guardar, em
alguma estrutura de dados, todos os valores e expressões já vistos anteriormente pelo compilador.
Como, para executar qualquer operação, o resultado de todas as sub-expressões terá que ficar, em
algum momento, em um registrador, o compilador
guarda que registrador está associado a cada subexpressão; assim, quando essa sub-expressão for
vista novamente, o compilador pode substitui-la
pelo registrador associado. Por exemplo, se a instrução R2 := R0 + R1 aparecer no código, o compilador vai associar a expressão R0 + R1 ao registrador R2, e toda vez que essa mesma expressão
for vista dentro do bloco básico, ela pode ser substituı́da por R2.
Uma forma de guardar essas expressões já vistas,
e verificar se uma expressão já foi vista, é usar uma
tabela hash. Pode-se indexar a tabela pela string
da expressão vista, e para cada expressão associar
um registrador. Ao analisar uma nova instrução,
o compilador primeiro verifica se ela já foi vista;
em caso positivo, pode ser substituı́da por um reg-
2.3
Otimização
procedural
global
ou
intra-
A seção anterior mostrou como pode ser feita a
otimização dentro dos blocos básicos, mas ainda é
necessário analisar o código em nı́veis menos locais.
O próximo passo é analisar rotinas (funções e procedimentos) inteiras, e identificar melhorias e redundâncias que ocorrem entre blocos básicos diferentes. Esse é o papel da otimização global, que tem
esse nome por uma questão de tradição, mas que
é mais apropriadamente chamada de otimização
intra-procedural.
Para realizar a análise nesse nı́vel são utilizadas
duas técnicas: análise de fluxo de dados e transformação do código para a forma SSA (Static Single
Assignment).
A análise de fluxo de dados é geralmente feita
através do estabelecimento de equações de fluxo
de dados. Os blocos básicos são organizados em
um grafo de fluxo de controle, indicando que blocos podem desviar para que outros blocos; em
seguida, cada bloco no grafo é analisado em relação
às equações de fluxo de dados, considerando suas
entradas e saı́das em relação aos blocos adjacentes
no grafo. Eventualmente essa análise atinge um
ponto-fixo e a solução das equações é determinada.
5
Essas equações indicam os caminhos que os dados
seguem para formar os valores necessários em cada
bloco.
A tradução para forma SSA é feita para que cada
variável só seja atribuı́da uma única vez no programa, e identificando onde essa variável será usada
para construir valores futuros. Em situações onde
não é possı́vel determinar que valores especı́ficos
serão usados, constrói-se uma função de escolha,
normalmente chamada de φ. A construção da forma SSA e a decisão de quais valores são utilizados
nos pontos onde existem funções φ são processos
que podem ser realizados por análises de fluxo de
dados.
A partir da forma SSA é possı́vel realizar
propagação de constantes e de cópia, eliminação
de sub-expressões redundantes, e eliminação de instruções de transferência, tudo isso em um nı́vel que
analisa rotinas inteiras. Não entraremos em mais
detalhes aqui sobre essas técnicas; a análise de fluxo
de dados é usada em várias otimizações em vários
compiladores, e a forma SSA vem sendo adotada
nos últimos anos por compiladores otimizadores
mais avançados. A versão 4 do compilador GCC
utiliza a forma SSA para fazer melhoria do código
gerado.
Formas mais gerais de otimização inter-procedural são conseguidas extendendo as técnicas usadas para otimização intra-procedural, principalmente o uso de análise de fluxo de dados e da
forma SSA. Neste caso, as equações de fluxo de
dados se tornam mais complexas de chegar a uma
solução, mas algumas análises podem resultar em
equações possı́veis de resolver e que levarão a melhorias no código. Como no caso da otimização
intra-procedural, não entraremos em maiores detalhes sobre essas técnicas aqui.
2.5
Otimização de programa inteiro
O nı́vel mais global de análise e otimização
possı́vel é, obviamente, analisar todo o programa
de uma vez só. Embora isso não seja prático
para o processo incremental de desenvolvimento,
e muitas vezes se torna impraticável, pode-se usar
a otimização de programa inteiro para gerar uma
versão final de um programa, neste caso utilizando
o máximo de otimização que seja possı́vel.
O custo óbvio nesse caso, além da complexidade das análises, é um gasto de memória muito
maior, pois as estruturas de dados que guardarão
informações que permitam identificar redundâncias
e melhorias se tornarão bem maiores ao analisar o
programa completo.
2.4 Otimização inter-procedural
As técnicas utilizadas ainda são a análise de
Após otimizar rotinas inteiras, o próximo nı́vel é fluxo de dados e a forma SSA, embora mais uma
procurar por melhorias que se mostram ao anal- vez as equações se tornem mais complexas. A
isar várias rotinas e seus relacionamentos. Um ex- maior diferença para o caso da otimização interemplo de melhoria que pode ser feita neste nı́vel procedural é que aqui o compilador precisa ver
é a otimização de chamadas. O objetivo desta todo o programa, já que compilar módulos sepaotimização é eliminar algumas chamadas de função radamente pode evitar a detecção de algumas reque são desnecessárias, trocando-as por instruções dundâncias e oportunidades para melhoria. De
de desvio simples. Como uma instrução de cha- resto, os processos são praticamente os mesmos.
mada de função precisa criar uma pilha local,
guardar valores de registradores e outras tarefas
de manutenção, uma instrução de desvio simples 3
Alocação de registradores
é bem mais rápida de executar; a questão é que em
alguns casos não é necessário fazer todas essas tare- O código intermediário normalmente utilizado em
fas de manutenção, e o compilador pode detectar compiladores se vale de um número ilimitado de
registradores, para simplificar tanto o processo
isso.
Outra melhoria que pode ser feita nesse nı́vel é a de geração do código intermediário quanto sua
expansão em linha de funções pequenas. Para econ- otimização. Entretanto, numa máquina real o
omizar uma chamada de função, o compilador pode número de registradores é limitado, e em alguns
substituir diretamente o corpo da função no ponto casos bem pequeno.
Os registradores no código intermediário são
de chamada, usando os parâmetros da chamada no
chamados de registradores virtuais, enquanto que
lugar dos argumentos da função.
6
os da máquina-alvo são registradores reais. O
processo de alocação de registradores consiste em
mapear os registradores virtuais nos registradores
reais, na medida do possı́vel, e usar a memória
como armazenamento auxiliar quando não sobrarem mais registradores reais.
A alocação de registradores é feita determinando
quais registradores virtuais têm valores ativos ao
mesmo tempo no código. Esses registradores virtuais não poderão ser mapeados para um mesmo registrador real, pois ambos precisam estar ativos ao
mesmo tempo. Diz-se então que dois registradores
virtuais nessa situação interferem um com o outro.
O primeiro passo para determinar a interferência
entre registradores virtuais é obter as regiões em
que cada registrador virtual está ativo no código.
Isso pode ser feita com uma análise de fluxo de
dados, e não será estudado em detalhes aqui.
Sabendo-se as regiões de atividade de cada registrador, constroi-se um grafo de interferência, no
qual cada registrador virtual é um nó e dois nós
estão ligados por uma aresta se eles interferem um
com o outro, ou seja, estão ativos ao mesmo tempo
no código.
A partir daı́ o problema é equivalente a um problema conhecido como coloração de grafos: como
escolher cores para os nós de um grafo de forma
que dois nós adjacentes (ou seja, ligados por uma
aresta) nunca tenham a mesma cor. Esse problema é computacionalmente NP-completo, sendo
impraticável usar algoritmos para achar a melhor
solução, na maioria dos casos. Entretanto, compiladores mais avançados costumam usar uma série
de heurı́sticas para achar uma boa coloração do
grafo de interferência, o que equivale a achar uma
boa alocação dos registradores.
Vejamos um exemplo de como decorre o processo.
Voltando ao código intermediário para o cálculo
do MDC, mostrado na figura 9, é fácil levantar as
regiões de atividade de cada registrador virtual: sua
região começa quando ele é atribuı́do, e termina na
última instrução que utiliza seu valor. Ao levantar as regiões para cada registrador e construir o
grafo de interferência, obtemos o grafo mostrado na
figura 11. Pelo grafo, uma primeira constatação é
que serão necessários pelo menos três registradores
reais, pois esse é o tamanho do maior componente.
Além disso, registradores virtuais que fiquem em
nós de componentes diferentes podem ser alocados
para um mesmo registrador real. O resultado final
é que só precisamos de três registradores reais para
o código inteiro.
R0
R1
R2
R4
R5
R3
R7
R6
R8
R9
Figura 11: Grafo de interferência para código do
cálculo do MDC
Para ilustrar, usaremos aqui os registradores
da arquitetura IA-32 da Intel, reservando os registradores EAX, EBX e ECX para o código do
cálculo do MDC. Após a alocação de registradores,
o código fica como na figura 12. O código resultante poderia ser otimizado trivialmente usando
propagação de cópias, e o resultado é mostrado
na figura 13. A partir daı́ a tradução para código
nativo da arquitetura IA-32 seria trivial: basicamente, apenas mudar as instruções da sintaxe do
código intermediário para a sintaxe da linguagem
assembly da arquitetura, e desdobrar os IFs para
duas instruções (teste e desvio condicional). Isso
pode ser feito automaticamente pelo compilador,
com facilidade.
7
WHILE:
THEN:
FIMIF:
FIMW:
EAX := 100
EBX := 104
IF NOT EAX != EBX GOTO FIMW
EAX := 100
EBX := 104
IF EAX > EBX GOTO THEN
EAX := 100
EBX := 104
ECX := EAX - EBX
100 := ECX
GOTO FIMIF
EAX := 100
EBX := 104
ECX := EBX - EAX
104 := ECX
GOTO WHILE
RET
Figura 12: Cálculo do MDC com registradores alocados
WHILE:
THEN:
FIMIF:
FIMW:
EAX := 100
EBX := 104
IF NOT EAX != EBX GOTO FIMW
IF EAX > EBX GOTO THEN
ECX := EAX - EBX
100 := ECX
GOTO FIMIF
ECX := EBX - EAX
104 := ECX
GOTO WHILE
RET
Figura 13: Cálculo do MDC após propagação de
cópias
8