Alto: A Link Time Optimizer
Edición y optimización de
ejecutables Compaq Alpha
Manel Fernández
Motivación

Linea CAP
• Arquitectura de computadores
• Modificaciones en el “hardware”
• Evaluación mediante simuladores

Cómo aplicar la tecnología de
compilación a nuestro trabajo?
Motivación

Herramientas de compilación
•
•
•
•

Ictineo
IMPACT
GNU cc
?
Es necesario un cambio tan “drástico”
en nuestra metodología?
Tucson, AZ
Talk outline
Introducción
 Usando “Alto”
 Fases de “Alto”
 Modificando “Alto”

Talk outline
Introducción
 Usando “Alto”
 Fases de “Alto”
 Modificando “Alto”

Qué es “Alto” ?

Optimizador de ejecutables Alpha/OSF1
Binario Alpha
alto
Binario Alpha
“mejorado”
“Alto”... para qué ?

Edición de binarios
• Instrumentación ¨Ad-hoc¨
• Visualización de código

Compilación a bajo nivel
• Alto IR es el Alpha ISA
• Optimizaciones “hardware-oriented”
A favor...
Código fuente disponible
 Eliminación del “front-end”

• Fichero de entrada: ejecutable
– Independencia del lenguaje de programación

Funcionamiento con/sin “profiling”

No hay cambios en la metodología!
En contra...

Código en fase de desarrollo
• Zonas de código “inhibido”
• No es portable
Binario final no ¨pixificable¨
 Consume muchos recursos

• Ej: Spec95 - 126.gcc
– >1/2 Gb de memoria (xdisk)
– 20-30´ de compilación
Talk outline
Introducción
 Usando “Alto”
 Fases de “Alto”
 Modificando “Alto”

Instalación

“Alto” URL
• http://www.cs.arizona.edu/alto

Compilación
•
•
•
•
•

more README
vi Makefile
...
gmake headers
gmake

Ejecutables
• alto
• {profadder}
• {profdump}
Última release pública: Agosto 1999 !!
Benchmarks

Binarios de entrada
• Compilados estáticamente
• Con “rellocation information”

Limitaciones de “Alto”
• Mejor preparado para código 21164
– arch ev5
• Global Pointer (GP) único
Compilación de benchmarks

Opciones de compilación
•
•
•
•
cc -Wl,-r -Wl,-d -Wl,-z -non_shared
f77 -Wl,-r -Wl,-d -Wl,-z -non_shared
gcc -Wl,-r -Wl,-d -Wl,-z -static
g++ -Wl,-r -Wl,-d -Wl,-z -static
• chmod +x ...
Invocando “Alto”

Optimizar un ejecutable
• alto -i <ifile> -o <ofile>

Opciones de invocación
• +300 “valores” no documentados!!!
• Ej: alto -V Phase+Status …
Opción
Valor
Concatenador
de valores
Valor
Opciones útiles
-V
-P
-T
-O
-r
-C
-L
-M
-p
Phase+Status+...
Loop+Bbl+Fun+...
Preproc+Postasm+...
Peep+Inline+...
<number>
<number>
Sensitive|...
Crit|Path|...
Bbl+Fun+...
Verbose info
Print “what”
Print “when”
Disable optimizations
Number of rounds
Cache size (#instr)
Liveness method
Inline method
Profile “what”
Talk outline
Introducción
 Usando “Alto”
 Fases de “Alto”
 Modificando “Alto”

Bibliografía… :-)

Bibliografía básica
• Aho, Sethi, Ullman. Compilers - Principles,
Techniques and Tools. Addison Wesley, 1986.
• Muchnick. Advanced Compiler Design and
Implementation. Morgan Kaufman, 1997.

“Alto” web page
• Muth, Debray, Watt., De Boss. alto: A Link-Time
Optimizer for the DEC Alpha. TR98-14, 1998.
• Muth. alto: A Platform for Object Code Modification.
PhD. Dissertation, 1999.
Fases del compilador

Loading phase
• Lee el binario y contruye el CFG

Optimization phase
• Optimizaciones locales/globales

Assembly phase
• Generación de código
CFG: Control flow graph
Loading phase

Lectura del binario
• “Rellocation information” (func & bbl)

Construcción del CFG
• Algoritmo clásico
• Funciones, BBs y aristas
• Optimizaciones triviales
– Elimina el cálculo del GP
– Normaliza operaciones
– ...
Construcción del CFG
caller
callee
call
edge
init
node
return
edge
exit
node
call
node
link edge
return
node
“Pseudo” funciones
caller
call
node
call
edge
hell
node
link edge
return
node
HELL
return
edge
jsr r26,(r27)...
“Pseudo” funciones
jmp r31,(r28)
HELL
HELL-LITE
relocate
basic block
jsr r26,(r27)
relocate
function
call_pal callsys
CALL
PAL
Optimization phase
Hard
Easy
Optimizations
Optimizaciones
aplicadas una
sola vez
#rounds
Hard
Optimizations
#rounds
Easy
Optimizaciones
sencillas
iterativamente
Easy
Optimizations
Easy optimizations
Register liveness analysis
Unreacheable code elimination
Peephole optimizations
Partial evaluation
Branch optimizations
Constant propagation
Jump table analysis
Copy propagation
Stack usage patterns
Alias analysis
Load/store avoidance
Code compression
Basic block replication
Inline small functions
Common subexpression elimination
Register renaming
liveness.c
opt.misc.c
peephole.c
eval.c
opt.branch.c
opt.constant.c
opt.switch.c
opt.propagation.c
opt.stack.c
aliasing.c
opt.loadstore.c
opt.compress.c
opt.dupbbl.c
opt.inline.c
opt.cse.c
opt.regrealloc.c
Hard optimizations
Shrink-wrapping
Cloning
Inlining
Value profiling
Code compression
Stack merging

opt.shrinkwrap.c
opt.dupfun.c
opt.inline.c
opt.inline.indir.c
opt.inline.jumps.c
opt.valprof.c
factor.bbl.c
factor.prolog.c
opt.stack.c
Muchas de ellas inhibidas !!!
Assembly phase

Code layout
• Dirigido por profiling (si disponible...)

Scheduling
• 21164 oriented
• Extended basic blocks
• BB alignment

Generación de código
Talk outline
Introducción
 Usando “Alto”
 Fases de “Alto”
 Modificando “Alto”

Code guidelines

Space-efficient (vs. speed)
• Preferible recalcular a almacenar
• Evita el uso de punteros
– Manipulación de elementos sobre listas
– Implementación de listas sobre vectores

Uso intensivo de macros !!!
• Aumenta la legibilidad del código
Include files
Log information
Fun/BB/Instr flags
Register file definitions
All data structures & macros
error.h
flags.h
regs.h
global.h
COFF binary file management
ELF binary file management
system.coff.h
system.elf.h
opcode.h
Alpha ISA opcodes
(generado automaticamente de table.c)
Estructuras de datos

Fichero global.h

Declaración de estructuras
• Todo son arrays globales
– Funciones / BBs / Instrucciones
• Acceso a traves de macros
Declaración de macros
 Declaración de límites de arrays

• Mucha memoria - Recompilar ??!!
Command line options

Módulo cmdline.c

Variable global
• Valores por defecto para opciones

Declaración de arrays globales
• Declaración estática !!!
• Mejor si sustituimos por “malloc”´s...

Lectura de comandos
Alpha ISA

Modulo table.c
• Similar al alpha.def del SimpleScalar
0x10,
0x00,
I_addl,
“addl”,
IT_IOP,
RES_PC,
0,
PIPE_E0|PIPE_E1,
1,
1
• wh64 missing!!!
Opcode number
Function number
Opcode name
Assembly name
Type
Resource usage
Resource definition
Pipeline usage
Latency average
Latency high
Ejemplo: remove NOPs
#undef __PROC__
#define __PROC__ “OptEliminateNoops”
extern BOOL OptEliminateNoops(FILE *fp)
{
INDEX iins;
NUMBER kcount = 0;
BOOL
verbose = HasOption(PRINT_OPT_VERBOSE,”Noop”);
FOREACH_LIVE_INS(iins)
{
if( AinsIsNoop(iins) )
/* kill noops */
{
if( verbose )
{
fprintf(fp,”\tKilling: “);
PrintIns(fp,iins);
}
}
kcount++;
AinsKill(iins);
...
Ejemplo: remove NOPs
...
/* kill useless moves */
if( AINS_CODE(iins) == I_lda &&
AINS_DATA(iins) == 0 &&
AINS_REG_B(iins) == AINS_REGC(iins) ) )
{
if( verbose )
{
fprintf(fp,”\tKilling: “);
PrintIns(fp,iins);
}
}
}
kcount++;
AinsKill(iins);
InfoStatus(fp,”\t[OptNoop] Killed Noops %d\n”, kcount);
}
return (kcount>0);
The End
Descargar

Easy Optimizations