Super Otimizador

Introdução

Linguagens de alto nível deveriam permitir ao programador abstrair o algoritmo da sua implementação. Para atingir esse objetivo, o programador não deveria ser consciente da arquitetura em que seu programa irá rodar. Entretanto, isso só é possível se o compilador possuir um bom otimizador; de outra maneira, o programador precisa tomar cuidado para seu programa não fique lento devido à má utilização dos recursos que o processador oferece.

Os otimizadores que existem no mercado, entretanto, não conseguem gerar o melhor código possível para um dado algoritmo. E mesmo que conseguissem, não há como garantir que o código gerado seja mesmo o melhor possível. Esse problema não existe com o Super Otimizador mostrado nessa página: com ele, garantidamente seu algoritmo é implementado da maneira ótima, sem nenhum espaço para outras otimizações.

Funcionamento

Para entender o funcionamento do Super Otimizador, precisamos primeiro definir alguns conceitos:

Programa: Por programa entendemos uma seqüência de operações que implementa uma função, ou seja, para uma dada seqüência de dados de entrada, a saída gerada é sempre a mesma.

Programa equivalente: Dois programas são equivalentes se, para uma mesma entrada, fornecem a mesma saída. Note que a equivalência só ocorre se a propriedade anterior for válida para todas as possíveis entradas do programa.

Compilador: A tarefa de um compilador é achar um programa equivalente ao código fonte fornecido, e que rode no processador alvo.

Métrica: Define-se uma métrica de um programa como um valor que o caracteriza. Métricas possíveis são: o tamanho do programa, em bytes; ou o número de ciclos que ele leva para executar.

Comprimento: O comprimento de um programa assembly é o número de instruções que ele possui. O comprimento é uma métrica possível para um programa assembly.

Otimizador: A tarefa de um otimizador é, dado um código fonte e um programa equivalente A, achar um segundo programa equivalente B, tal que a métrica de B seja menor que a métrica de A.

Programa ótimo: O programa ótimo é o programa equivalente a um código fonte que possui a menor métrica possível. Esse deveria ser o objetivo máximo de um otimizador.

Métrica monotônica crescente: Uma métrica é monotônica crescente se, ao adicionar uma instrução a um programa dado, seu valor torna-se maior que antes, ou seja, a diferença entre o valor novo e o anterior é positiva e maior que zero.

Tendo assimilado os conceitos acima, fica fácil entender o funcionamento do Super Otimizador. Inicialmente, cria-se um conjunto com todos os programas possíveis de comprimento unitário, e testa-se cada um deles para checar se algum é equivalente ao código fonte. Caso seja, anota-se a métrica desse programa e retira-se do conjunto todos os programas de métrica maior que a obtida. Retira-se também do conjunto todos os programas que não são equivalentes ao fonte.

Prosseguindo, adiciona-se ao conjunto todos os programas possíveis de comprimento dois, e novamente verifica-se se algum programa do conjunto é equivalente ao fonte. Caso ache-se outro programa equivalente, verifica-se se a métrica dele é menor que a métrica já obtida. Caso seja, troca-se a métrica alvo e retira-se do conjunto todos os programas de métrica maior que a obtida. Continua-se esse algoritmo até que haja pelo menos um programa equivalente encontrado, e todos os programas do comprimento atual tenham métrica maior que o alvo atual.

Esse método gera todos os programas possíveis para a arquitetura dada, ou seja, garantidamente ele vai achar pelo menos um programa que implementa o fonte fornecido. Além disso, como a métrica é monotônica crescente, então é certo que a partir de um certo ponto todos os programas gerados terão métrica maior que a métrica do programa equivalente encontrado. E, por fim, como todos os programas possíveis menores que a dada métrica foram testados, então certamente o programa equivalente encontrado é ótimo.

Implementação

A implementação do Super Otimizador para a arquitetura Z80 foi feita com base em emulação. Para testar se um programa é equivalente ao fonte fornecido, o fonte é compilado, e o programa a ser testado é emulado e comparado com o binário para todas as suas entradas possíveis. Como o fonte é testado após a compilação, a linguagem de entrada é irrelevante, sendo necessário apenas o binário do programa a ser testado. Nesta implementação optou-se por limitar o programa à linguagem ANSI C, mas isso pode ser facilmente estendido.

Para rodar o Super Otimizador, basta compilar o programa opt.c e preencher os parâmetros corretos no início do arquivo. As opções possíveis são:

MAXLEVEL: Este símbolo determina o comprimento máximo dos programas a serem inspecionados. Um valor MAXLEVEL=2 indica que todos os programas de comprimento menor ou igual a 3 serão pesquisados. Atualmente o limite para MAXLEVEL é 7.

CARRYSOL: Caso definido, esse símbolo indica que o resultado do programa deve ser retornado no flag de carry. Caso não definido, o resultado estará no acumulador.

measure_type: Essa váriavel indica qual a métrica a ser utilizada. Valores possíveis são: 0=métrica de comprimento, 1=métrica de bytes utilizados (otimização por espaço), 2=métrica de ciclos de execução (otimização por velocidade, nesse caso é utilizada a tabela de ciclos de um Z80 com um waitstate no ciclo M1).

ARGS: Este símbolo determina o número de parâmetros de entrada do programa. Para ARGS=1, você deve preencher a função final com o programa a ser compilado, o parâmetro de entrada é input. Para ARGS=2, você deve preencher final2, e os parâmetros de entrada serão a e h.

Tempo de execução

O Super Otimizador é exponencial no comprimento do programa encontrado, o que significa que é bastante lento. Para encontrar uma solução de comprimento seis ele leva 12 horas num Athlon 1.4GHz, embora seja bem mais rápido para comprimentos menores (um programa de comprimento 3 leva menos de 15 segundos).

Estes tempos só foram conseguidos utilizando otimizações na árvore de busca. Em especial, caso tenha sido encontrado um programa equivalente, programas com métrica maior que ele nem chegam a ser testados.

Além disso, uma análise de fluxo de dados impede que programas de registros indefinidos sejam testados. Assim, um programa do tipo ADD A,H não é testado pois ele sabe que o valor do registro H não está determinado, porém LD H,A; ADD A,H é testado pois o valor de H está determinado.

Sugestões

Se você tiver tempo disponível de CPU, abaixo estão algumas funções cujo programa ótimo eu gostaria de ver. (Dica: deixe rodando à noite, enquanto você estiver dormindo). Mande seus resultados para ricardo@700km.com.br, e adicione-os a esta página para referência futura.

return a&128?h:0;  			/* passo de multiplicação */
return a&1?h:0;    			/* passo de multiplicação */
return a>h?a:h;    			/* função max */
return (signed char)a<(signed char)h;   /* comparação com sinal */

Exemplos de código gerado

Função em CRetorno em A Retorno no carry
return 0;
XOR  A

AND  A
return 1;
LD   A,1

SCF
return input==0;
ADD  A,255
SBC  A,A
INC  A

CP   1
return input!=0;
CP   1
SBC  A,A
INC  A


ADD  A,255
return (signed char)input<0;
RLCA
AND  1

RLCA
return (signed char)input>0;
CPL
RLCA
LD   H,A
ADC  A,0
SBC  A,H

CPL
LD   H,A
RLCA
SUB  H
return (signed char)input<=0;
RLCA
LD   H,1
SUB  H
ADC  A,H
AND  H

SCF
LD   H,A
DEC  A
ADC  A,H
return (signed char)input>=0;
RLCA
SBC  A,A
INC  A

ADD  A,A
CCF
return input/2;
SRL  A
return (signed char)input/2;
LD   H,A
RLCA
SUB  H
RRA
/* abs(x) */
return (signed char)input<0?-input:input;
LD   H,A
RLCA
SBC  A,A
XOR  H
SUB  H
ADC  A,H
/* sgn(x) */
return (signed char)input<0?-1:input==0?0:1; 
RLCA
LD   H,A
SBC  A,H
SUB  H
ADC  A,H
/* incremento com saturação no máximo */
return input<255?input+1:255;
SUB  255
ADC  A,255
/* decremento com saturação no mínimo */
return input>0?input-1:0;
ADD  A,255
SBC  A,255
/* scroll em direção ao centro */
return input>32?input-1:input<32?input-1:input;
SUB 32
SUB 1
ADC A,32
/* A no intervalo 0-255 */
return ((input&7)==7)||((input&7)==0);
INC	A
AND	7
RRA	
CP	1
/* A no intervalo 0-7 */
return ((input&7)==7)||((input&7)==0);
LD	H,A
SUB	7
DEC	H
SUB	H
Função em CRetorno em A Retorno no carry
return a==h;
XOR  H
ADD  A,255
SBC  A,A
INC  A

XOR  H
SUB  1
return a!=h;
XOR  H
SUB  1
SBC  A,A
INC  A

XOR  H
ADD  A,255
return a<h;
SUB  H
RLA
AND  1

SUB  H
return a>h;
SCF
SBC  A,H
SBC  A,A
INC  A

SCF
SBC  A,H
CCF
return a<=h;
SCF
SBC  A,H
RLA
AND  1

SCF
SBC  A,H
return a>=h;
SUB  H
SBC  A,A
INC  A

SUB  H
CCF
return a&&h;
CP   1
LD   A,0
SBC  A,H
ADC  A,H

ADD  A,255
SBC  A,A
ADD  A,H
return a||h;
OR   H
SUB  1
SBC  A,A
INC  A

ADD  A,H
ADC  A,255
return a-h;
SUB  H
return h-a;
CPL
SCF
ADC  A,H
return a?h:0;
ADD  A,255
SBC  A,A
AND  H
/* incremento modular, h=(modulo-1) */
return a<h?a+1:0;
CP   H
INC  A
LD   H,A
SBC  A,H
AND  H
/* decremento modular, h=(modulo-1) */
return a?a-1:h;
ADD  A,255
LD   L,A
SBC  A,L
OR   H
AND  L
/* troca condicional de sinal */
return a?h:-h;
ADD  A,255
SBC  A,A
AND  H
ADD  A,A
SUB  H
/* min */
return a>=h?h:a;
SUB  H
LD   L,A
SBC  A,A
AND  L
ADD  A,H
Autor: Ricardo Bittencourt
Data: 2003.5.17
Copyright © 2003 Ricardo Bittencourt