1 Módulo 15: Projeto do Professor — O Compilador Fica Pronto
Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro, com as decisões justificadas uma a uma. É o modelo do que o seu grupo entrega na entrega final, não algo a copiar.
1.1 Visão Geral do Módulo 15
Último módulo. O compilador fica pronto, medimos o que construímos e fechamos o percurso.
A atividade tem três frentes. A otimização: identificar os blocos básicos na representação intermediária, construir o grafo de fluxo de controle e implementar pelo menos duas transformações locais, verificando em cada caso que a semântica foi preservada. A integração final: o executor completo, com tratamento de erro, rodando sobre entradas reais e não apenas sobre exemplos preparados. E a consolidação, com a retrospectiva do que foi construído.
Resolvi a atividade e há dois resultados que quero antecipar, porque os dois contrariam a expectativa com que se chega a este módulo.
O primeiro é que o otimizador quase não encontra o que otimizar neste artefato. Rodado sobre um programa típico da linguagem, ele remove zero instruções. Isso não é falha: a representação intermediária sai da tradução direta do módulo 13, sem redundância, e um otimizador que não acha nada em código apertado está funcionando. Registro o número em vez de esconder, e escrevi um programa artificial à parte para mostrar as transformações operando.
O segundo é mais interessante e é o achado do módulo. A eliminação de subexpressões comuns — uma das transformações que a ementa pede — preserva a semântica e mesmo assim não pode ser aplicada neste compilador. Ela viola uma precondição da máquina de destino, e quem a acusa é uma verificação que escrevi no módulo 14, um módulo antes de o otimizador existir. Está na tarefa 4, demonstrada em código.
1.2 Tarefa 1: Blocos básicos e o grafo de fluxo
A atividade — identificar os blocos básicos na representação intermediária e construir o grafo de fluxo de controle.
Um bloco básico é uma sequência maximal de instruções em que o controle entra pela primeira e sai pela última — sem desvio para dentro do meio, sem desvio para fora antes do fim. A razão de a otimização operar sobre eles é econômica: dentro de um bloco a ordem de execução é a ordem do texto, e isso dispensa raciocinar sobre caminhos.
15_blocos.h
#ifndef PENEIRA_15_BLOCOS_H
#define PENEIRA_15_BLOCOS_H
#include <cstddef>
#include <set>
#include <string>
#include <vector>
#include "13_ri.h"
namespace peneira {
// BLOCOS BÁSICOS E GRAFO DE FLUXO DE CONTROLE.
//
// Um bloco básico é uma sequência maximal de instruções em que o controle entra
// pela primeira e sai pela última — sem desvio para dentro do meio e sem desvio
// para fora antes do fim. É a unidade sobre a qual a otimização local opera, e
// a razão de ela existir é simples: dentro de um bloco, a ordem de execução é a
// ordem do texto, e isso dispensa raciocinar sobre caminhos.
// Um bloco básico, dado pelo intervalo semiaberto de instruções que o compõe.
struct BlocoBasico {
std::size_t inicio = 0;
std::size_t fim = 0; // exclusivo
std::vector<std::size_t> sucessores;
// O fim da regra não é um bloco — não há instrução lá —, mas é um destino
// legítimo, e é para onde vão os desvios de condição falsa. Sem este campo
// um bloco que só sai pelo fim apareceria sem sucessor nenhum, e um
// condicional cujo alvo é o fim apareceria com um sucessor só, escondendo
// justamente a bifurcação que o grafo existe para mostrar.
bool saiParaOFim = false;
};
struct GrafoDeFluxo {
std::vector<BlocoBasico> blocos;
// Índice do bloco que contém cada instrução.
std::vector<std::size_t> blocoDaInstrucao;
};
// O algoritmo dos líderes. Um líder é: a primeira instrução; toda instrução
// alvo de desvio; e toda instrução que segue imediatamente um desvio. Cada
// líder abre um bloco, que vai até o líder seguinte.
std::vector<std::size_t> lideres(const CodigoRI& ri);
GrafoDeFluxo construirGrafo(const CodigoRI& ri);
std::string formatarGrafo(const CodigoRI& ri, const GrafoDeFluxo& g);
// ---------------------------------------------------------------------------
// Análise de fluxo de dados: variáveis vivas, por ponto fixo
// ---------------------------------------------------------------------------
//
// Um temporário está VIVO num ponto se algum caminho a partir dali o lê antes
// de redefini-lo. É a informação que torna a eliminação de código morto segura:
// só se remove a definição de algo que não está vivo na saída.
//
// A análise é PARA TRÁS — a informação flui do uso para a definição — e é
// resolvida por ponto fixo: repetir as equações até nada mudar. É exatamente a
// mesma técnica dos conjuntos de anuláveis e produtivos do módulo 8 e dos
// primeiros e seguidores do módulo 10. Terceira aparição do mesmo padrão no
// semestre, e vale nomear: quando a definição de um conjunto se refere a si
// mesma, calcula-se por ponto fixo.
struct AnaliseDeVivacidade {
// Para cada instrução, os temporários vivos na saída dela.
std::vector<std::set<std::string>> vivosNaSaida;
// Quantas rodadas até estabilizar. Serve para mostrar que o ponto fixo
// existe e é alcançado, em vez de afirmá-lo.
std::size_t iteracoes = 0;
};
AnaliseDeVivacidade analisarVivacidade(const CodigoRI& ri);
std::string formatarVivacidade(const CodigoRI& ri,
const AnaliseDeVivacidade& a);
// Sucessores de uma instrução no fluxo de controle. O índice igual ao tamanho
// do vetor representa o fim da regra e não tem sucessor.
std::vector<std::size_t> sucessoresDe(const CodigoRI& ri, std::size_t i);
// O que a instrução define e o que ela lê. Separado porque três clientes
// precisam da mesma informação — vivacidade, eliminação de morto e o cálculo de
// subexpressões — e tê-la em um lugar só evita que divirjam.
std::string definidoPor(const InstrucaoRI& ins);
std::vector<std::string> lidosPor(const InstrucaoRI& ins);
// Uma instrução tem efeito colateral quando sua execução importa mesmo que seu
// resultado não seja lido. Nesta linguagem, só a emissão — e essa distinção é
// o que separa uma eliminação de código morto correta de uma que apaga a saída
// do programa.
bool temEfeitoColateral(const InstrucaoRI& ins);
} // namespace peneira
#endif // PENEIRA_15_BLOCOS_HA identificação usa o algoritmo dos líderes: é líder a primeira instrução, toda instrução alvo de desvio, e toda instrução que segue imediatamente um desvio. Cada líder abre um bloco que vai até o líder seguinte.
15_blocos.cpp
#include "15_blocos.h"
#include <algorithm>
#include <sstream>
namespace peneira {
std::string definidoPor(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::Constante:
case OpRI::CasamentoDe:
case OpRI::Valor:
case OpRI::Comparacao:
return ins.resultado;
default:
return std::string();
}
}
std::vector<std::string> lidosPor(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
return {ins.arg1};
case OpRI::Comparacao:
return {ins.arg1, ins.arg2};
case OpRI::Emite:
// arg1 é o rótulo literal, não um temporário. Incluí-lo aqui faria
// o rótulo virar um nome vivo e nunca eliminado — inofensivo por
// acaso, e errado por princípio.
return {ins.arg2};
default:
return {};
}
}
bool temEfeitoColateral(const InstrucaoRI& ins) {
return ins.op == OpRI::Emite;
}
std::vector<std::size_t> sucessoresDe(const CodigoRI& ri, std::size_t i) {
if (i >= ri.instrucoes.size()) {
return {};
}
const InstrucaoRI& ins = ri.instrucoes[i];
if (ins.op == OpRI::Desvio) {
return {ins.destino};
}
if (ins.op == OpRI::DesvioSeFalso) {
// Dois sucessores: a queda e o alvo. É esta instrução que faz o fluxo
// deixar de ser uma linha e virar grafo.
if (ins.destino == i + 1) {
return {i + 1};
}
return {i + 1, ins.destino};
}
return {i + 1};
}
std::vector<std::size_t> lideres(const CodigoRI& ri) {
std::set<std::size_t> marcados;
if (!ri.instrucoes.empty()) {
marcados.insert(0);
}
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
const bool ehDesvio =
ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso;
if (!ehDesvio) {
continue;
}
// Alvo do desvio é líder — desde que caia dentro do código. O destino
// igual ao tamanho é o fim da regra, que não abre bloco.
if (ins.destino < ri.instrucoes.size()) {
marcados.insert(ins.destino);
}
// A instrução seguinte a um desvio também é líder: se o desvio for
// tomado, o controle nunca chega nela pela queda.
if (i + 1 < ri.instrucoes.size()) {
marcados.insert(i + 1);
}
}
return std::vector<std::size_t>(marcados.begin(), marcados.end());
}
GrafoDeFluxo construirGrafo(const CodigoRI& ri) {
GrafoDeFluxo g;
const std::vector<std::size_t> ls = lideres(ri);
if (ls.empty()) {
return g;
}
for (std::size_t k = 0; k < ls.size(); ++k) {
BlocoBasico b;
b.inicio = ls[k];
b.fim = (k + 1 < ls.size()) ? ls[k + 1] : ri.instrucoes.size();
g.blocos.push_back(b);
}
g.blocoDaInstrucao.assign(ri.instrucoes.size(), 0);
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
for (std::size_t i = g.blocos[k].inicio; i < g.blocos[k].fim; ++i) {
g.blocoDaInstrucao[i] = k;
}
}
// Arestas: saem da ÚLTIMA instrução de cada bloco, porque é a única de onde
// o controle pode deixar o bloco. Calcular a partir de qualquer outra
// produziria arestas que não existem.
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
if (g.blocos[k].fim == g.blocos[k].inicio) {
continue;
}
const std::size_t ultima = g.blocos[k].fim - 1;
for (const std::size_t s : sucessoresDe(ri, ultima)) {
if (s >= ri.instrucoes.size()) {
g.blocos[k].saiParaOFim = true;
continue;
}
const std::size_t destino = g.blocoDaInstrucao[s];
auto& suc = g.blocos[k].sucessores;
if (std::find(suc.begin(), suc.end(), destino) == suc.end()) {
suc.push_back(destino);
}
}
}
return g;
}
std::string formatarGrafo(const CodigoRI& ri, const GrafoDeFluxo& g) {
std::ostringstream out;
out << " bloco | instrucoes | sucessores\n";
out << " ------+------------+-----------\n";
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
const BlocoBasico& b = g.blocos[k];
const std::string faixa =
std::to_string(b.inicio) + ".." + std::to_string(b.fim - 1);
out << " B" << k << " | " << faixa;
for (std::size_t i = faixa.size(); i < 9; ++i) {
out << ' ';
}
out << " | ";
bool primeiro = true;
for (const std::size_t s : b.sucessores) {
if (!primeiro) {
out << ", ";
}
out << "B" << s;
primeiro = false;
}
if (b.saiParaOFim) {
if (!primeiro) {
out << ", ";
}
out << "(fim)";
primeiro = false;
}
if (primeiro) {
out << "(fim)";
}
out << '\n';
}
(void)ri;
return out.str();
}
AnaliseDeVivacidade analisarVivacidade(const CodigoRI& ri) {
AnaliseDeVivacidade a;
const std::size_t n = ri.instrucoes.size();
a.vivosNaSaida.assign(n, std::set<std::string>());
std::vector<std::set<std::string>> vivosNaEntrada(n);
bool mudou = true;
while (mudou) {
mudou = false;
++a.iteracoes;
// Percorre de trás para a frente: a informação flui do uso para a
// definição, e ir na direção do fluxo faz o ponto fixo convergir em
// menos rodadas. Ir para a frente também converge — só demora mais.
for (std::size_t k = n; k > 0; --k) {
const std::size_t i = k - 1;
std::set<std::string> saida;
for (const std::size_t s : sucessoresDe(ri, i)) {
if (s < n) {
saida.insert(vivosNaEntrada[s].begin(),
vivosNaEntrada[s].end());
}
}
std::set<std::string> entrada = saida;
const std::string def = definidoPor(ri.instrucoes[i]);
if (!def.empty()) {
entrada.erase(def);
}
for (const std::string& uso : lidosPor(ri.instrucoes[i])) {
if (!uso.empty()) {
entrada.insert(uso);
}
}
if (saida != a.vivosNaSaida[i] || entrada != vivosNaEntrada[i]) {
a.vivosNaSaida[i] = saida;
vivosNaEntrada[i] = entrada;
mudou = true;
}
}
}
return a;
}
std::string formatarVivacidade(const CodigoRI& ri,
const AnaliseDeVivacidade& a) {
std::ostringstream out;
out << " instr | vivos na saida\n";
out << " ------+---------------\n";
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
out << " " << i;
if (i < 10) {
out << ' ';
}
out << " | ";
if (a.vivosNaSaida[i].empty()) {
out << "(nenhum)";
} else {
bool primeiro = true;
for (const std::string& v : a.vivosNaSaida[i]) {
if (!primeiro) {
out << ", ";
}
out << v;
primeiro = false;
}
}
out << '\n';
}
return out.str();
}
} // namespace peneiraSobre a condição composta do módulo 13, a demonstração --blocos dá:
lideres: 0, 5, 10
bloco | instrucoes | sucessores
------+------------+-----------
B0 | 0..4 | B1, (fim)
B1 | 5..9 | B2, (fim)
B2 | 10..11 | (fim)Três blocos, um por operando da conjunção mais o da emissão, e a estrutura é exatamente a do curto-circuito: de B0 sai-se para B1 se a primeira comparação passar, e direto para o fim se não passar.
Uma correção que a primeira versão desta tabela exigiu vale registrar, porque o erro era de exibição e escondia o conceito. O fim da regra não é um bloco — não há instrução lá —, e a primeira versão simplesmente descartava as arestas que apontavam para ele. O resultado é que B0 aparecia com um único sucessor, e um bloco terminado em desvio condicional com um sucessor só contradiz a própria definição de desvio condicional. A saída negava o que o comentário do código afirmava. O campo que marca a saída para o fim existe por isso.
Onde é fácil errar aqui. Calcular os sucessores de um bloco a partir de qualquer instrução que não seja a última. Só da última o controle pode deixar o bloco — é a definição —, e usar outra produz arestas que não existem.
Como verificar. A soma dos tamanhos dos blocos tem de ser igual ao número de instruções, sem sobreposição nem buraco. E todo alvo de desvio tem de ser o início de algum bloco; se um alvo cai no meio de um bloco, a identificação de líderes está incompleta.
1.3 Tarefa 2: Análise de fluxo de dados, por ponto fixo
A atividade — explicar o papel da análise de fluxo de dados e a noção de solução por ponto fixo.
A eliminação de código morto precisa saber se um valor ainda será lido, e essa pergunta não se responde olhando uma instrução: depende de todos os caminhos a partir dela. É análise de fluxo de dados, e implementei a mais direta delas — variáveis vivas.
Um temporário está vivo num ponto se algum caminho a partir dali o lê antes de redefini-lo. A análise é para trás, porque a informação flui do uso para a definição, e é resolvida por ponto fixo: repetir as equações até nada mudar.
A demonstração --vivacidade mostra o resultado e o custo:
instr | vivos na saida
------+---------------
0 | t0
1 | t1
2 | t1, t2
3 | t3
4 | (nenhum)
5 | t4
...
ponto fixo alcancado em 2 rodada(s)Duas rodadas: uma que calcula e outra que confirma que nada mudou. O ponto fixo existe e é alcançado, e isso está medido em vez de afirmado.
Vale nomear o padrão, porque esta é a terceira aparição dele no semestre e a repetição é o que o fixa. No módulo 8, os conjuntos de símbolos anuláveis e produtivos foram calculados por ponto fixo. No módulo 10, os conjuntos de primeiros e seguidores. Aqui, as variáveis vivas. Sempre que a definição de um conjunto se refere a si mesma, a solução é iterar até estabilizar — e as três implementações têm a mesma forma.
Há uma leitura da tabela que explica o módulo inteiro: quase nenhum temporário fica vivo por muito tempo. No máximo dois ao mesmo tempo, e cada valor é consumido logo depois de produzido. É a mesma quantidade que a coloração do grafo de interferência apontou no módulo 14, calculada por outro caminho — e é o que explica por que a eliminação de código morto encontra tão pouco aqui.
Onde é fácil errar aqui. Incluir o rótulo da emissão entre os operandos lidos. Ele é um literal, não um temporário, e contá-lo o transformaria num nome vivo que nunca é eliminado. Inofensivo por acaso neste caso, e errado por princípio — por isso a função que lista os operandos despacha por operação em vez de varrer campos.
Como verificar. Um temporário não pode estar vivo antes de ser definido. Se aparecer na saída de uma instrução anterior à sua definição, as equações estão trocadas.
1.4 Tarefa 3: As transformações, e a preservação verificada
A atividade — implementar pelo menos duas transformações locais, verificando em cada caso que a semântica foi preservada.
A regra que governa tudo aqui é absoluta: a transformação tem de preservar a semântica. Otimização não é esperteza — é transformação com condição de aplicabilidade, e a condição é o que separa uma otimização de um defeito. Cada função do arquivo declara a sua.
15_otimizacao.h
#ifndef PENEIRA_15_OTIMIZACAO_H
#define PENEIRA_15_OTIMIZACAO_H
#include <cstddef>
#include <string>
#include <vector>
#include "10_ast.h"
#include "12_sema.h"
#include "13_objeto.h"
#include "13_ri.h"
#include "14_codegen.h"
#include "15_blocos.h"
namespace peneira {
// OTIMIZAÇÕES LOCAIS, cada uma com a condição que a torna segura.
//
// A regra que governa tudo aqui é absoluta e não negociável: a transformação
// tem de PRESERVAR A SEMÂNTICA. Otimização não é esperteza — é transformação
// com condição de aplicabilidade, e a condição é o que separa uma otimização de
// um defeito. Toda função deste arquivo declara a sua.
//
// Uma propriedade da nossa representação intermediária simplifica a vida e vale
// nomear: cada temporário é atribuído UMA ÚNICA VEZ. Isso é, em pequeno, o que
// a forma de atribuição única estática mencionada no módulo 13 faz em grande, e
// é o que torna dispensável verificar se um valor foi redefinido entre a
// definição e o uso — não há redefinição possível.
struct EstatisticasDeOtimizacao {
std::size_t dobramentos = 0;
std::size_t subexpressoesEliminadas = 0;
std::size_t instrucoesMortas = 0;
std::size_t iteracoes = 0;
std::size_t instrucoesAntes = 0;
std::size_t instrucoesDepois = 0;
};
// ---------------------------------------------------------------------------
// Dobramento de constantes
// ---------------------------------------------------------------------------
//
// Substitui uma comparação entre dois valores conhecidos na compilação pelo
// resultado dela.
//
// CONDIÇÃO DE SEGURANÇA: os dois operandos têm de ser constantes literais, e a
// operação tem de ser pura — sem efeito e sem depender de nada além dos
// operandos. Comparação satisfaz. Se a linguagem tivesse divisão, o dobramento
// precisaria excluir o divisor zero, porque a expressão que falha em execução
// não pode ser substituída por um valor em compilação.
CodigoRI dobrarConstantes(const CodigoRI& ri, EstatisticasDeOtimizacao& e);
// ---------------------------------------------------------------------------
// Eliminação de código morto
// ---------------------------------------------------------------------------
//
// Remove instruções cujo resultado não é lido em caminho nenhum.
//
// CONDIÇÃO DE SEGURANÇA: duas, e esquecer a segunda é o erro clássico. O
// resultado não pode estar vivo na saída — o que a análise de vivacidade
// responde — E a instrução não pode ter efeito colateral. Uma emissão não
// produz resultado algum, então um verificador que olhe só a primeira condição
// a considera morta e apaga a saída inteira do programa.
//
// O parâmetro `guardaDeEfeito` existe para DEMONSTRAR esse erro: com ele em
// falso, a função vira a versão defeituosa. Não é código morto nem opção de
// configuração — é o contraexemplo executável de que a condição importa.
CodigoRI eliminarCodigoMorto(const CodigoRI& ri, EstatisticasDeOtimizacao& e,
bool guardaDeEfeito = true);
// ---------------------------------------------------------------------------
// Eliminação de subexpressões comuns
// ---------------------------------------------------------------------------
//
// Quando a mesma expressão é computada duas vezes dentro de um bloco, sem que
// seus operandos mudem entre as duas, a segunda pode reusar o resultado da
// primeira.
//
// CONDIÇÃO DE SEGURANÇA: os operandos não podem ser redefinidos entre as duas
// ocorrências (garantido pela atribuição única), a expressão tem de ser pura, e
// as duas ocorrências têm de estar NO MESMO BLOCO — fora do bloco não há
// garantia de que a primeira tenha sido executada.
//
// ATENÇÃO, e este é o achado deste módulo: esta transformação é semanticamente
// correta e MESMO ASSIM não pode ser aplicada neste compilador. Ver
// `cseQuebraGeracao` e o relatório da demonstração.
CodigoRI eliminarSubexpressoes(const CodigoRI& ri, const GrafoDeFluxo& g,
EstatisticasDeOtimizacao& e);
// Devolve os temporários que passariam a ser lidos mais de uma vez se a
// eliminação de subexpressões fosse aplicada. Vazio significa que a
// transformação é compatível com o gerador de código.
//
// A máquina de destino é de pilha, e ler um temporário é DESEMPILHÁ-LO. O
// gerador do módulo 14 verifica que cada temporário é lido exatamente uma vez,
// e a eliminação de subexpressões faz exatamente o contrário: ela existe para
// que um resultado sirva a vários leitores. Correta para uma máquina de
// registradores, incompatível com esta.
std::vector<std::string> cseQuebraGeracao(const CodigoRI& original,
const CodigoRI& otimizado);
// ---------------------------------------------------------------------------
// Condutor
// ---------------------------------------------------------------------------
//
// Aplica as transformações seguras repetidamente até nada mais mudar — um ponto
// fixo, pelo mesmo motivo dos módulos 8, 10 e da análise de vivacidade: cada
// transformação cria oportunidades para as outras. Dobrar uma constante torna
// morto o cálculo que a produzia; remover o cálculo pode tornar morto o que o
// alimentava.
CodigoRI otimizar(const CodigoRI& ri, EstatisticasDeOtimizacao& e);
// Gera o objeto inserindo a otimização entre a representação intermediária e a
// emissão. Espelha `gerarObjeto` do módulo 14, com uma passada a mais no meio.
//
// Mora aqui, e não no módulo 14, para que a dependência aponte para a frente:
// o gerador não pode precisar do otimizador, senão o compilador do módulo 14
// deixaria de compilar sozinho. O preço é a repetição do laço que percorre as
// ações, e é preço consciente.
ProgramaObjeto gerarObjetoOtimizado(const ResultadoSemantico& semantico,
const NoAst& raiz,
RelatorioDeGeracao& relatorio,
EstatisticasDeOtimizacao& e);
} // namespace peneira
#endif // PENEIRA_15_OTIMIZACAO_HImplementei dobramento de constantes e eliminação de código morto como as duas do condutor, e uma propriedade da nossa representação intermediária simplifica as duas: cada temporário é atribuído uma única vez. Isso é, em pequeno, o que a forma de atribuição única estática mencionada no módulo 13 faz em grande, e dispensa verificar se um valor foi redefinido entre a definição e o uso — não há redefinição possível.
15_otimizacao.cpp
#include "15_otimizacao.h"
#include <cstdlib>
#include <unordered_map>
namespace peneira {
namespace {
// Uma constante literal, se a instrução for uma. `ehNumero` distingue "100" de
// um texto, porque comparar texto por ordem não é permitido nesta linguagem e
// o dobramento não pode inventar essa comparação.
struct Literal {
bool existe = false;
bool ehNumero = false;
double numero = 0.0;
std::string texto;
};
Literal literalDe(const InstrucaoRI& ins) {
Literal l;
if (ins.op != OpRI::Constante) {
return l;
}
const std::string& bruto = ins.arg1;
if (bruto.size() >= 2 && bruto.front() == '"' && bruto.back() == '"') {
l.existe = true;
l.texto = bruto.substr(1, bruto.size() - 2);
return l;
}
char* fim = nullptr;
const double n = std::strtod(bruto.c_str(), &fim);
if (fim != nullptr && *fim == '\0' && !bruto.empty()) {
l.existe = true;
l.ehNumero = true;
l.numero = n;
}
return l;
}
bool avaliar(const std::string& operador, const Literal& a, const Literal& b,
bool& resultado) {
if (a.ehNumero != b.ehNumero) {
return false; // tipos diferentes: a semântica já recusou isto antes
}
if (a.ehNumero) {
if (operador == ">") { resultado = a.numero > b.numero; return true; }
if (operador == "<") { resultado = a.numero < b.numero; return true; }
if (operador == ">=") { resultado = a.numero >= b.numero; return true; }
if (operador == "<=") { resultado = a.numero <= b.numero; return true; }
if (operador == "==") { resultado = a.numero == b.numero; return true; }
if (operador == "!=") { resultado = a.numero != b.numero; return true; }
return false;
}
// Texto: só igualdade, porque só ela foi permitida na análise semântica.
if (operador == "==") { resultado = a.texto == b.texto; return true; }
if (operador == "!=") { resultado = a.texto != b.texto; return true; }
return false;
}
// Assinatura de uma expressão, para reconhecer repetição. Duas instruções com a
// mesma assinatura computam a mesma coisa.
std::string assinaturaDe(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::CasamentoDe:
return "casamento:" + ins.arg1;
case OpRI::Valor:
return "valor:" + ins.arg1;
case OpRI::Constante:
return "const:" + ins.arg1;
case OpRI::Comparacao:
return "cmp:" + ins.operador + ":" + ins.arg1 + ":" + ins.arg2;
default:
return std::string();
}
}
// Reescreve os operandos de leitura conforme o mapa de substituição.
void substituirLeituras(InstrucaoRI& ins,
const std::unordered_map<std::string, std::string>& de) {
auto trocar = [&](std::string& campo) {
const auto it = de.find(campo);
if (it != de.end()) {
campo = it->second;
}
};
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
trocar(ins.arg1);
break;
case OpRI::Comparacao:
trocar(ins.arg1);
trocar(ins.arg2);
break;
case OpRI::Emite:
trocar(ins.arg2);
break;
default:
break;
}
}
// Reconstrói o código sem as instruções marcadas, corrigindo os destinos dos
// desvios. Remover instrução renumera tudo que vem depois, e esquecer de
// corrigir os desvios é o modo mais rápido de transformar uma otimização
// correta num objeto quebrado.
CodigoRI removerMarcadas(const CodigoRI& ri, const std::vector<bool>& remover) {
const std::size_t n = ri.instrucoes.size();
std::vector<std::size_t> novoIndice(n + 1, 0);
std::size_t k = 0;
for (std::size_t i = 0; i < n; ++i) {
novoIndice[i] = k;
if (!remover[i]) {
++k;
}
}
novoIndice[n] = k;
CodigoRI saida;
saida.padrao = ri.padrao;
saida.ligacao = ri.ligacao;
for (std::size_t i = 0; i < n; ++i) {
if (remover[i]) {
continue;
}
InstrucaoRI ins = ri.instrucoes[i];
if (ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso) {
if (ins.destino <= n) {
ins.destino = novoIndice[ins.destino];
}
}
saida.instrucoes.push_back(ins);
}
return saida;
}
} // namespace
CodigoRI dobrarConstantes(const CodigoRI& ri, EstatisticasDeOtimizacao& e) {
// Mapa de temporário para o literal que ele contém. Vale porque cada
// temporário é atribuído uma única vez.
std::unordered_map<std::string, Literal> constantes;
CodigoRI saida;
saida.padrao = ri.padrao;
saida.ligacao = ri.ligacao;
saida.instrucoes = ri.instrucoes;
for (std::size_t i = 0; i < saida.instrucoes.size(); ++i) {
InstrucaoRI& ins = saida.instrucoes[i];
if (ins.op == OpRI::Constante) {
const Literal l = literalDe(ins);
if (l.existe) {
constantes[ins.resultado] = l;
}
continue;
}
if (ins.op != OpRI::Comparacao) {
continue;
}
const auto a = constantes.find(ins.arg1);
const auto b = constantes.find(ins.arg2);
if (a == constantes.end() || b == constantes.end()) {
continue;
}
bool valor = false;
if (!avaliar(ins.operador, a->second, b->second, valor)) {
continue;
}
// A comparação vira uma constante. Os operandos ficam sem leitor e
// serão removidos pela eliminação de código morto — não aqui, porque
// cada transformação faz uma coisa só.
const std::string resultado = ins.resultado;
ins = InstrucaoRI{};
ins.op = OpRI::Constante;
ins.resultado = resultado;
ins.arg1 = valor ? "1" : "0";
constantes[resultado] = literalDe(ins);
++e.dobramentos;
}
return saida;
}
CodigoRI eliminarCodigoMorto(const CodigoRI& ri, EstatisticasDeOtimizacao& e,
bool guardaDeEfeito) {
const AnaliseDeVivacidade vivacidade = analisarVivacidade(ri);
std::vector<bool> remover(ri.instrucoes.size(), false);
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
// Desvios nunca são mortos: eles não definem valor, definem controle.
if (ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso) {
continue;
}
// A segunda condição de segurança. Sem ela, toda emissão é considerada
// morta — ela não define temporário nenhum — e o programa otimizado
// deixa de produzir saída.
if (guardaDeEfeito && temEfeitoColateral(ins)) {
continue;
}
const std::string def = definidoPor(ins);
if (def.empty()) {
// Não define nada e não tem efeito guardado: só sobra a emissão
// quando a guarda está desligada, que é o caso do contraexemplo.
if (!guardaDeEfeito && temEfeitoColateral(ins)) {
remover[i] = true;
++e.instrucoesMortas;
}
continue;
}
if (vivacidade.vivosNaSaida[i].count(def) == 0) {
remover[i] = true;
++e.instrucoesMortas;
}
}
return removerMarcadas(ri, remover);
}
CodigoRI eliminarSubexpressoes(const CodigoRI& ri, const GrafoDeFluxo& g,
EstatisticasDeOtimizacao& e) {
std::vector<bool> remover(ri.instrucoes.size(), false);
std::unordered_map<std::string, std::string> substituir;
for (const BlocoBasico& bloco : g.blocos) {
// O dicionário é reiniciado a cada bloco, e é isso que mantém a
// transformação LOCAL: fora do bloco não há garantia de que a primeira
// ocorrência tenha sido executada.
std::unordered_map<std::string, std::string> disponivel;
for (std::size_t i = bloco.inicio; i < bloco.fim; ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
if (temEfeitoColateral(ins)) {
continue;
}
const std::string chave = assinaturaDe(ins);
if (chave.empty() || ins.resultado.empty()) {
continue;
}
const auto it = disponivel.find(chave);
if (it == disponivel.end()) {
disponivel.emplace(chave, ins.resultado);
continue;
}
// Já calculado neste bloco: a segunda ocorrência some e seus
// leitores passam a ler o primeiro resultado.
remover[i] = true;
substituir[ins.resultado] = it->second;
++e.subexpressoesEliminadas;
}
}
CodigoRI intermediario = ri;
for (InstrucaoRI& ins : intermediario.instrucoes) {
substituirLeituras(ins, substituir);
}
return removerMarcadas(intermediario, remover);
}
std::vector<std::string> cseQuebraGeracao(const CodigoRI& original,
const CodigoRI& otimizado) {
(void)original;
std::unordered_map<std::string, std::size_t> leituras;
for (const InstrucaoRI& ins : otimizado.instrucoes) {
for (const std::string& t : lidosPor(ins)) {
if (!t.empty()) {
++leituras[t];
}
}
}
std::vector<std::string> violacoes;
for (const auto& par : leituras) {
if (par.second > 1) {
violacoes.push_back(par.first + " passaria a ser lido " +
std::to_string(par.second) + " vezes");
}
}
return violacoes;
}
CodigoRI otimizar(const CodigoRI& ri, EstatisticasDeOtimizacao& e) {
e.instrucoesAntes = ri.instrucoes.size();
CodigoRI atual = ri;
// Ponto fixo: repete enquanto o tamanho encolher. Cada transformação cria
// oportunidade para a outra — dobrar uma constante deixa órfão o cálculo
// que a produzia, e removê-lo pode deixar órfão o que o alimentava.
//
// A eliminação de subexpressões NÃO entra aqui, e o motivo está no
// cabeçalho: ela é correta e incompatível com o gerador de código desta
// máquina. Deixá-la de fora é decisão registrada, não esquecimento.
for (;;) {
++e.iteracoes;
const std::size_t antes = atual.instrucoes.size();
atual = dobrarConstantes(atual, e);
atual = eliminarCodigoMorto(atual, e, true);
if (atual.instrucoes.size() >= antes) {
break;
}
}
e.instrucoesDepois = atual.instrucoes.size();
return atual;
}
namespace {
void colherAcoesOtim(const NoAst& no, std::vector<const NoAst*>& saida) {
if (no.tipo == TipoAst::Acao) {
saida.push_back(&no);
return;
}
for (const AstPtr& filho : no.filhos) {
if (filho) {
colherAcoesOtim(*filho, saida);
}
}
}
} // namespace
ProgramaObjeto gerarObjetoOtimizado(const ResultadoSemantico& semantico,
const NoAst& raiz,
RelatorioDeGeracao& relatorio,
EstatisticasDeOtimizacao& e) {
ProgramaObjeto objeto;
std::unordered_map<std::string, std::uint32_t> indiceDoPadrao;
for (const PadraoCompilado& p : semantico.padroes) {
indiceDoPadrao.emplace(
p.nome, static_cast<std::uint32_t>(objeto.padroes.size()));
objeto.padroes.push_back(serializarPadrao(
p.automato, p.nome, p.tipoDoCasamento == Tipo::Numero));
}
std::vector<const NoAst*> acoes;
colherAcoesOtim(raiz, acoes);
for (const NoAst* acao : acoes) {
TradutorRI tradutor;
const CodigoRI bruta = tradutor.traduzirAcao(*acao);
// A única diferença em relação ao gerador do módulo 14.
EstatisticasDeOtimizacao parcial;
const CodigoRI ri = otimizar(bruta, parcial);
e.dobramentos += parcial.dobramentos;
e.instrucoesMortas += parcial.instrucoesMortas;
e.iteracoes += parcial.iteracoes;
e.instrucoesAntes += parcial.instrucoesAntes;
e.instrucoesDepois += parcial.instrucoesDepois;
const auto it = indiceDoPadrao.find(acao->texto);
if (it == indiceDoPadrao.end()) {
continue;
}
RegraObjeto regra;
regra.indiceDoPadrao = it->second;
regra.ligacao = acao->conteudo;
regra.codigo = gerarCodigoDaRegra(ri, objeto, relatorio);
objeto.regras.push_back(std::move(regra));
++relatorio.regrasGeradas;
}
return objeto;
}
} // namespace peneira1.4.1 O que acontece num programa típico
Nada. E o número está publicado:
CASO 1 — programa tipico da linguagem
instrucoes antes: 12, depois: 12
dobramentos: 0, instrucoes mortas removidas: 0A tentação aqui seria escolher um exemplo que rendesse e apresentá-lo como típico. O resultado honesto é este, e ele tem explicação: a representação intermediária sai da tradução direta do módulo 13, cada valor é usado logo após ser produzido, e não há redundância a remover. Um otimizador que não acha nada em código apertado está certo.
1.4.2 O que acontece quando há o que fazer
Para mostrar as transformações operando, escrevi um programa artificial, e o rotulei como tal — a condição é decidível na compilação, coisa que nenhum programa útil faria:
antes: depois:
0: t0 := 100 0: t2 := 1
1: t1 := 500 1: se_falso t2 desvia para 4
2: t2 := t0 < t1 2: t3 := casamento n
3: se_falso t2 desvia para 6 3: emite "sempre", t3
4: t3 := casamento n 4: (fim da regra)
5: emite "sempre", t3
6: (fim da regra)
instrucoes: 6 -> 4, dobramentos: 1, mortas: 2, iteracoes: 2Duas coisas para reparar. As transformações se alimentam: dobrar a comparação deixa os dois operandos sem leitor, e a eliminação de código morto os remove — por isso o condutor repete até o ponto fixo em vez de fazer uma passada de cada. E o destino do desvio mudou de 6 para 4: remover instrução renumera tudo que vem depois, e esquecer de corrigir os desvios é o modo mais rápido de transformar uma otimização correta num objeto quebrado.
1.4.3 A preservação, verificada por confronto
A exigência de preservar a semântica não se demonstra por argumento — se demonstra por confronto. Compilo o mesmo programa com e sem otimização, executo os dois objetos sobre o mesmo corpus e exijo emissões idênticas, na mesma ordem e nas mesmas posições:
caso 1: 13 instrucoes sem otimizacao, 13 com
entradas comparadas: 5, emissoes conferidas: 5
equivalentes: SIM
caso 2: 7 instrucoes sem otimizacao, 5 com
entradas comparadas: 5, emissoes conferidas: 17
equivalentes: SIMComparo rótulo, valor e posição. Comparar só o valor deixaria passar uma transformação que reordena emissões ou desloca o casamento — dois defeitos plausíveis que a comparação frouxa não pegaria.
Isto não é prova: um corpus finito não cobre todas as entradas. É evidência, e é da mesma natureza do confronto entre autômato gerado e autômato manual do módulo 4. Dizer que é prova seria mais confortável e seria falso.
Onde é fácil errar aqui. Verificar a preservação comparando as representações intermediárias em vez das execuções. Duas representações diferentes podem ter o mesmo significado — é exatamente o que a otimização produz —, então a comparação estrutural acusa divergência onde não há. O que precisa ser igual é o comportamento observável.
Como verificar. O corpus tem de incluir entradas que exercitem os dois lados de cada desvio. Um corpus em que a condição é sempre verdadeira não distingue uma otimização correta de uma que apagou o caminho falso.
1.5 Tarefa 4: Duas transformações que parecem boas e não são
A atividade — justificar a segurança de cada transformação, com o caso de fronteira que a quebra.
1.5.1 A que quebra a semântica
A eliminação de código morto tem duas condições de segurança, e esquecer a segunda é o erro clássico. O resultado não pode estar vivo na saída — o que a análise de vivacidade responde — e a instrução não pode ter efeito colateral.
A emissão é o caso. Ela não produz resultado algum, então um verificador que pergunte apenas “o resultado é lido?” conclui que ela é morta. Deixei a versão defeituosa acessível por parâmetro, para que o efeito seja demonstrado em vez de descrito:
com guarda: 12 instrucoes, 0 removidas
sem guarda: 11 instrucoes, 1 removidas
emissoes no programa: 1 antes, 0 depois da versao sem guardaO programa otimizado não produz saída alguma. Ele continua compilando, continua executando, não acusa erro nenhum, passa em toda checagem estrutural — e não faz mais nada. É o exemplo mais direto de por que preservar a semântica é requisito absoluto e não recomendação: a versão quebrada é indistinguível da correta por qualquer critério que não seja o comportamento observável.
1.5.2 A que preserva a semântica e mesmo assim não serve
Este é o achado do módulo, e ele não estava previsto quando comecei.
A eliminação de subexpressões comuns é correta: quando a mesma expressão é computada duas vezes dentro de um bloco, sem que seus operandos mudem, a segunda pode reusar o resultado da primeira. Implementei, e o resultado sobre dois programas:
programa tipico (where com 'and'):
blocos: 3, subexpressoes eliminadas: 0, instrucoes: 12 -> 12
nenhuma violacao: as repeticoes de 'casamento n' caem em
blocos DIFERENTES, e a transformacao local nao as alcanca.
programa artificial (where value(n) > value(n)):
blocos: 2, subexpressoes eliminadas: 1, instrucoes: 8 -> 7
VIOLACOES da invariante de uso unico do modulo 14:
t0 passaria a ser lido 2 vezes
O gerador do modulo 14 RECUSA este codigo.No programa típico ela não dispara, e a razão é instrutiva: as repetições de casamento n caem em blocos diferentes, e uma transformação local não as alcança. Capturá-las exigiria análise global — que é justamente o panorama que a ementa pede e que este projeto não implementa.
No programa artificial ela dispara, e aí aparece o problema. A eliminação de subexpressões existe para que um resultado sirva a vários leitores. A máquina de destino é de pilha, e ler um temporário é desempilhá-lo: o segundo leitor encontraria a pilha vazia.
A transformação preserva a semântica e viola a precondição do gerador de código. E quem a acusa é a verificação de uso único que escrevi no módulo 14 — antes de o otimizador existir, sem prever este uso. Uma invariante escrita para proteger a geração de código detectou uma otimização incompatível um módulo depois.
Por isso ela está implementada e fora do condutor, com a decisão registrada no cabeçalho. Deixá-la de fora sem explicação pareceria esquecimento; deixá-la dentro produziria objeto quebrado.
Onde é fácil errar aqui. Concluir que uma transformação é aplicável porque é semanticamente correta. Correção semântica é condição necessária e não suficiente: a transformação também precisa respeitar as precondições da máquina de destino e das fases seguintes.
Como verificar. Rodar a verificação de uso único do gerador sobre o código otimizado, e não apenas sobre o código recém-traduzido. Se a otimização introduz violação, ela é incompatível — e o gerador é o lugar certo para descobrir isso, porque é ele que depende da invariante.
1.6 Tarefa 5: A integração final
A atividade — o executor completo, com tratamento de erro, rodando sobre entradas reais.
O executor do módulo 14 era mínimo por decisão: ele detectava objeto malformado em execução, quando a instrução defeituosa era alcançada. Isso significa que um objeto quebrado num caminho raro passa por bom até a entrada certa aparecer.
A integração final faz as mesmas checagens estaticamente, antes de qualquer execução, percorrendo o objeto inteiro:
15_validacao.h
#ifndef PENEIRA_15_VALIDACAO_H
#define PENEIRA_15_VALIDACAO_H
#include <string>
#include <vector>
#include "13_objeto.h"
namespace peneira {
// INTEGRAÇÃO FINAL: tratamento de erro completo.
//
// O executor do módulo 14 era mínimo por decisão: ele detectava objeto
// malformado em EXECUÇÃO, quando a instrução defeituosa era alcançada. Isso
// significa que um objeto quebrado num caminho raro passa por bom até a entrada
// certa aparecer.
//
// A validação abaixo faz as mesmas checagens ESTATICAMENTE, antes de qualquer
// execução, percorrendo todo o objeto em vez de só o caminho tomado. É a
// diferença entre "não deu erro nos testes" e "não pode dar erro".
struct ProblemaNoObjeto {
std::string onde;
std::string mensagem;
};
// Percorre o objeto inteiro e devolve tudo que está errado. Lista vazia
// significa que nenhuma das condições de erro previstas na especificação do
// módulo 13 pode ocorrer em execução.
//
// Checa: índices de constante e de padrão dentro da faixa; destinos de desvio
// dentro da faixa; toda regra alcançando um fim; e — a mais interessante — o
// BALANÇO DA PILHA, por simulação estática de todos os caminhos. Um objeto em
// que algum caminho desempilha de pilha vazia é malformado, e descobrir isso
// sem executar é possível porque o fluxo é acíclico.
std::vector<ProblemaNoObjeto> validarObjeto(const ProgramaObjeto& objeto);
// ---------------------------------------------------------------------------
// Preservação de semântica, verificada por execução diferencial
// ---------------------------------------------------------------------------
//
// A exigência de preservar a semântica não se demonstra por argumento — se
// demonstra por confronto. Compilamos o mesmo programa com e sem otimização,
// executamos os dois objetos sobre o mesmo corpus e exigimos emissões
// idênticas, na mesma ordem e nas mesmas posições.
//
// Isso não é prova: um corpus finito não cobre todas as entradas. É evidência,
// e é a evidência mais forte disponível a custo razoável — a mesma natureza do
// confronto entre autômato gerado e manual do módulo 4.
struct ResultadoDaComparacao {
bool equivalentes = true;
std::size_t entradasComparadas = 0;
std::size_t emissoesComparadas = 0;
std::string divergencia;
};
ResultadoDaComparacao compararExecucoes(const ProgramaObjeto& a,
const ProgramaObjeto& b,
const std::vector<std::string>& corpus);
} // namespace peneira
#endif // PENEIRA_15_VALIDACAO_H15_validacao.cpp
#include "15_validacao.h"
#include <algorithm>
#include <vector>
#include "14_vm.h"
namespace peneira {
namespace {
int efeitoNaPilhaDe(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST:
case OpCode::PUSH_MATCH:
return +1;
case OpCode::VALUE:
return 0;
case OpCode::CMP_GT:
case OpCode::CMP_LT:
case OpCode::CMP_GE:
case OpCode::CMP_LE:
case OpCode::CMP_EQ:
case OpCode::CMP_NE:
case OpCode::AND:
case OpCode::OR:
case OpCode::JUMP_IF_FALSE:
case OpCode::EMIT:
return -1;
case OpCode::JUMP:
case OpCode::HALT:
return 0;
}
return 0;
}
std::string ondeRegra(std::size_t r, std::size_t i) {
return "regra " + std::to_string(r) + ", instrucao " + std::to_string(i);
}
} // namespace
std::vector<ProblemaNoObjeto> validarObjeto(const ProgramaObjeto& objeto) {
std::vector<ProblemaNoObjeto> problemas;
// Padrões: tabela coerente com a quantidade de estados declarada.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
const PadraoObjeto& pd = objeto.padroes[p];
const std::string onde = "padrao " + std::to_string(p);
if (pd.finais.size() != pd.quantidadeDeEstados) {
problemas.push_back(ProblemaNoObjeto{
onde, "vetor de finais nao bate com a quantidade de estados"});
}
if (pd.transicoes.size() !=
static_cast<std::size_t>(pd.quantidadeDeEstados) *
kTamanhoDoAlfabeto) {
problemas.push_back(ProblemaNoObjeto{
onde, "tabela de transicao com tamanho errado"});
}
if (pd.quantidadeDeEstados > 0 &&
pd.estadoInicial >= pd.quantidadeDeEstados) {
problemas.push_back(
ProblemaNoObjeto{onde, "estado inicial fora de faixa"});
}
for (const std::uint32_t t : pd.transicoes) {
if (t != kSemTransicao && t >= pd.quantidadeDeEstados) {
problemas.push_back(
ProblemaNoObjeto{onde, "transicao para estado inexistente"});
break;
}
}
}
for (std::size_t r = 0; r < objeto.regras.size(); ++r) {
const RegraObjeto& regra = objeto.regras[r];
if (regra.indiceDoPadrao >= objeto.padroes.size()) {
problemas.push_back(ProblemaNoObjeto{
"regra " + std::to_string(r), "referencia padrao inexistente"});
continue;
}
if (regra.codigo.empty()) {
problemas.push_back(
ProblemaNoObjeto{"regra " + std::to_string(r), "codigo vazio"});
continue;
}
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
const Instrucao& ins = regra.codigo[i];
switch (ins.op) {
case OpCode::PUSH_CONST:
case OpCode::EMIT:
if (ins.argumento >= objeto.constantes.size()) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, i), "indice de constante fora de faixa"});
}
break;
case OpCode::JUMP:
case OpCode::JUMP_IF_FALSE:
if (ins.argumento >= regra.codigo.size()) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, i), "desvio fora de faixa"});
}
break;
default:
break;
}
}
// Balanço da pilha por simulação de todos os caminhos. O fluxo gerado
// por este compilador é acíclico — todo desvio vai para a frente —,
// então uma varredura em profundidade com marcação de visitado termina
// e cobre tudo.
//
// Guardamos a altura com que cada instrução é alcançada. Se a mesma
// instrução for alcançada com alturas diferentes, o objeto é
// malformado: a altura da pilha num ponto tem de ser propriedade do
// ponto, e não do caminho.
std::vector<int> alturaEm(regra.codigo.size(), -1);
std::vector<std::pair<std::size_t, int>> pendentes;
pendentes.push_back({0, 0});
bool jaReclamou = false;
while (!pendentes.empty()) {
const std::size_t pc = pendentes.back().first;
const int altura = pendentes.back().second;
pendentes.pop_back();
if (pc >= regra.codigo.size()) {
continue;
}
if (alturaEm[pc] >= 0) {
if (alturaEm[pc] != altura && !jaReclamou) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, pc),
"altura da pilha depende do caminho (" +
std::to_string(alturaEm[pc]) + " ou " +
std::to_string(altura) + ")"});
jaReclamou = true;
}
continue;
}
alturaEm[pc] = altura;
const Instrucao& ins = regra.codigo[pc];
const int depois = altura + efeitoNaPilhaDe(ins.op);
if (depois < 0 && !jaReclamou) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, pc), "desempilha de pilha vazia"});
jaReclamou = true;
continue;
}
if (ins.op == OpCode::HALT) {
continue;
}
if (ins.op == OpCode::JUMP) {
pendentes.push_back({ins.argumento, depois});
continue;
}
if (ins.op == OpCode::JUMP_IF_FALSE) {
pendentes.push_back({ins.argumento, depois});
pendentes.push_back({pc + 1, depois});
continue;
}
pendentes.push_back({pc + 1, depois});
}
// Toda regra tem de poder terminar. Sem HALT alcançável, o executor
// sai por passar da última instrução — o que funciona, mas deixa de
// ser garantia e vira acidente.
bool temHalt = false;
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
if (regra.codigo[i].op == OpCode::HALT && alturaEm[i] >= 0) {
temHalt = true;
break;
}
}
if (!temHalt) {
problemas.push_back(ProblemaNoObjeto{
"regra " + std::to_string(r), "nenhum HALT alcancavel"});
}
}
return problemas;
}
ResultadoDaComparacao compararExecucoes(
const ProgramaObjeto& a, const ProgramaObjeto& b,
const std::vector<std::string>& corpus) {
ResultadoDaComparacao r;
for (const std::string& entrada : corpus) {
++r.entradasComparadas;
const ResultadoExecucao ra = executar(a, entrada);
const ResultadoExecucao rb = executar(b, entrada);
if (ra.emissoes.size() != rb.emissoes.size()) {
r.equivalentes = false;
r.divergencia = "entrada \"" + entrada + "\": " +
std::to_string(ra.emissoes.size()) +
" emissoes antes, " +
std::to_string(rb.emissoes.size()) + " depois";
return r;
}
for (std::size_t i = 0; i < ra.emissoes.size(); ++i) {
++r.emissoesComparadas;
const Emissao& ea = ra.emissoes[i];
const Emissao& eb = rb.emissoes[i];
// Rótulo, valor E posição. Comparar só o valor deixaria passar uma
// transformação que reordena emissões ou desloca o casamento.
if (ea.rotulo != eb.rotulo || ea.valor != eb.valor ||
ea.posicao != eb.posicao) {
r.equivalentes = false;
r.divergencia = "entrada \"" + entrada + "\", emissao " +
std::to_string(i) + ": (" + ea.rotulo + ", " +
ea.valor + ", " + std::to_string(ea.posicao) +
") contra (" + eb.rotulo + ", " + eb.valor +
", " + std::to_string(eb.posicao) + ")";
return r;
}
}
}
return r;
}
} // namespace peneiraA checagem que mais rende é a do balanço da pilha, e ela é possível por uma propriedade do código que geramos: todo desvio salta para a frente, então o fluxo é acíclico e uma varredura em profundidade com marcação termina cobrindo tudo. A exigência é mais forte que “a pilha nunca fica negativa”: exige-se que a altura em cada instrução seja propriedade do ponto e não do caminho. Se dois caminhos chegam à mesma instrução com alturas diferentes, o objeto é malformado — mesmo que nenhuma entrada exercite os dois.
Essa é a diferença entre “os testes passaram” e “não pode dar errado”, e é o que justifica o esforço: o executor mínimo do módulo 14 nunca teria encontrado um desequilíbrio num ramo não exercitado.
A execução sobre o corpus inclui as entradas degeneradas de propósito:
"valores: 7 250 1200 480 -3 99 101"
grande = 250 / 1200 / 480 / 101 7 casamentos, 0 erros
"nada aqui"
(nenhuma emissao) 0 casamentos, 0 erros
"0 100 101 499 500 501"
grande = 101 / 499 / 500 / 501 6 casamentos, 0 erros
""
(nenhuma emissao) 0 casamentos, 0 errosA entrada vazia e a que não casa com nada estão ali porque são onde um executor mal terminado trava ou acusa erro sem motivo. Conferi a terceira à mão: dos seis números, saem os quatro estritamente maiores que cem — 100 não sai, e é o caso de fronteira que distingue > de >=.
E o comando principal fecha o ciclo, agora com otimização e validação no caminho:
fases do compilador:
analise lexica pronta (modulo 7)
analise sintatica pronta (modulo 10)
analise semantica pronta (modulo 12)
geracao de codigo pronta (modulo 14)
otimizacao pronta (modulo 15)
execucao pronta (modulo 15)Um objeto que não passa na validação não é gravado e o compilador sai com erro. Gravar um objeto que sabemos malformado seria produzir um artefato que só falha adiante, na mão de quem for executá-lo.
Onde é fácil errar aqui. Tratar a validação como opcional porque “o gerador é confiável”. O ponto da validação não é desconfiar do gerador — é que ela custa pouco e transforma uma classe inteira de defeitos de “aparece em produção” para “aparece na compilação”.
Como verificar. Introduzir deliberadamente um objeto malformado e conferir que a validação o rejeita. Uma validação que nunca reprovou nada pode estar sempre devolvendo lista vazia.
1.7 O que ficou de fora, e o compromisso que o número expõe
Três pontos do conteúdo do módulo não viraram código, e prefiro dizer quais e por quê a deixar a impressão de cobertura completa.
A propagação de cópias não tem alvo neste compilador. Ela substitui os usos de um temporário que é mera cópia de outro, e a nossa representação intermediária nunca emite instrução de cópia — a tradução do módulo 13 sempre produz um valor novo ou lê um casamento. O mecanismo existe e está em uso: é exatamente a substituição de leituras que a eliminação de subexpressões aplica. O que não existe é a instrução que ele removeria.
O panorama das otimizações globais ficou no conceitual, e a tarefa 4 mostra o motivo concreto em vez de enunciá-lo: as três ocorrências de casamento n que a transformação local não alcança, por caírem em blocos diferentes, são precisamente o que uma análise global pegaria. O limite da otimização local está medido, não afirmado.
E há o compromisso entre tempo de compilação, tempo de execução e agressividade das transformações, que os números deste módulo expõem melhor que qualquer argumento. O condutor roda até o ponto fixo — duas rodadas no programa artificial, uma no típico — e o ganho é de duas instruções no primeiro e zero no segundo. O custo de compilação é real e pago sempre; o ganho de execução é nulo no caso comum.
Num compilador deste porte, portanto, a otimização não se paga por desempenho. Ela se paga por outra coisa, e vale ser explícito: ela existe aqui para que a estrutura sobre a qual a otimização opera — blocos, fluxo, vivacidade — seja construída e compreendida, porque é essa estrutura que sustenta tudo que vem depois em compiladores de verdade. Um compilador de produção inverte a conta, com muito mais transformações sobre código muito menos apertado, e aí a agressividade passa a ter preço em tempo de compilação que precisa ser escolhido — é a razão de esses compiladores oferecerem níveis de otimização em vez de um só.
1.8 A retrospectiva: da expressão regular ao programa executável
Vale percorrer o caminho inteiro, porque é o que consolida a disciplina como uma coisa só em vez de quinze assuntos. A demonstração --retrospectiva monta o quadro a partir do artefato real:
| Módulo | O que entrou no artefato | Evidência no objeto final |
|---|---|---|
| 02 | especificação léxica como dado executável | 6 categorias |
| 03 | autômato determinístico, estados como índices | tabela de transição |
| 04 | Thompson: expressão regular para autômato | via de construção |
| 05 | subconjuntos e minimização | 11 estados no objeto |
| 06 | diferença de autômatos | inferência de tipo |
| 07 | analisador léxico sobre autômato, casamento mais longo | reusado no executor |
| 08 | gramática da linguagem | 22 produções |
| 09 | autômato de pilha (teoria) | o analisador do módulo 10 |
| 10 | descida recursiva para árvore | 13 nós |
| 11 | análise ascendente (comparação) | caminho não tomado |
| 12 | tabela de símbolos e tipos | 2 padrões tipados |
| 13 | três endereços e formato do objeto | especificação executável |
| 14 | geração de código e executor | 11 instruções |
| 15 | blocos, fluxo, otimização, validação | objeto validado |
O arquivo gerado tem 2816 células de transição e 11 instruções. A maior parte do programa objeto, em bytes, são os autômatos do primeiro bloco.
É o que quero deixar como fechamento: nesta disciplina, a teoria de linguagens formais não é preâmbulo da construção de compiladores. Ela é o produto. O autômato mínimo do módulo 5 está gravado no arquivo de saída; a diferença de autômatos do módulo 6 decidiu o sistema de tipos do módulo 12; o casamento mais longo do módulo 7 é o laço principal do executor. Três resultados que, quando foram apresentados, pareciam exercícios de fronteira.
1.9 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Blocos básicos | Algoritmo dos líderes, cobertura sem buraco | 3 blocos, líderes 0, 5 e 10 |
| Grafo de fluxo | Sucessores da última instrução de cada bloco | Bifurcação exibida, incluindo saída para o fim |
| Análise de fluxo de dados | Ponto fixo, com número de rodadas | Vivacidade, 2 rodadas |
| Duas transformações | Implementadas com condição de segurança declarada | Dobramento e código morto |
| Preservação de semântica | Confronto de execuções, não argumento | 5 entradas, 22 emissões, equivalentes |
| Transformação que quebra | Caso de fronteira demonstrado | Código morto sem guarda apaga a saída |
| Limite de aplicabilidade | Transformação correta e incompatível | Subexpressões comuns, recusada pelo gerador |
| Executor completo | Erro tratado em todas as fases | Validação estática de todos os caminhos |
| Entradas reais | Corpus com casos degenerados | Vazia, sem casamento, fronteira em 100 |
| Ponta a ponta | Do texto ao efeito observável | Compila, valida, grava e executa |
| Retrospectiva | Percurso com evidência no artefato | 14 módulos mapeados |
| Compilação limpa | Modo estrito, aviso como erro | Sem nenhum diagnóstico |
| Regressão | Demonstrações dos módulos 2 a 14 | Verificadas |
O que quero deixar registrado sobre esta entrega, e sobre o semestre, são duas coisas.
A primeira é que o otimizador quase não otimiza, e a entrega é boa assim. A orientação do módulo é priorizar a integração sobre a otimização, e o número que publiquei — zero instruções removidas num programa típico — é o resultado honesto de um artefato cuja representação intermediária já era apertada. Um grupo que apresentar ganhos espetaculares num compilador deste porte provavelmente mediu o exemplo errado.
A segunda é sobre como os defeitos apareceram ao longo destes módulos. Nenhum dos três mais sérios foi encontrado por teste ou por revisão. A notação de pontuação errada do módulo 7 apareceu quando o analisador léxico passou a usar o autômato de verdade. A interferência calculada errada do módulo 14 apareceu porque a mesma grandeza tinha dois caminhos de cálculo. E a incompatibilidade da eliminação de subexpressões apareceu porque uma invariante escrita para outro fim continuou sendo verificada. O padrão é o mesmo nos três: construir de verdade, medir por dois caminhos, e manter as invariantes ligadas. É o que este projeto de referência tem a ensinar além do conteúdo.