Alto: A Link Time OptimizerAlto: A Link Time Optimizer
Edición y optimización de Edición y optimización de ejecutables Compaq Alphaejecutables Compaq Alpha
Manel FernándezManel Fernández
MotivaciónMotivación
Linea CAPLinea CAP• Arquitectura de computadoresArquitectura de computadores• Modificaciones en el “hardware”Modificaciones en el “hardware”• Evaluación mediante Evaluación mediante simuladoressimuladores
Cómo aplicar la tecnología de Cómo aplicar la tecnología de compilación a nuestro trabajo?compilación a nuestro trabajo?
MotivaciónMotivación
Herramientas de compilaciónHerramientas de compilación• IctineoIctineo• IMPACTIMPACT• GNU ccGNU cc• ??
Es necesario un cambio tan “Es necesario un cambio tan “drásticodrástico” ” en nuestra metodología?en nuestra metodología?
Tucson, AZTucson, AZ
Talk outlineTalk outline
IntroducciónIntroducción Usando Usando “Alto”“Alto” Fases de Fases de “Alto”“Alto” Modificando Modificando “Alto”“Alto”
Talk outlineTalk outline
IntroducciónIntroducción Usando Usando “Alto”“Alto” Fases de Fases de “Alto”“Alto” Modificando Modificando “Alto”“Alto”
Qué es “Alto” ?Qué es “Alto” ?
Binario AlphaBinario AlphaBinario Alpha Binario Alpha “mejorado”“mejorado”altoalto
OptimizadorOptimizador de ejecutables de ejecutables Alpha/OSF1Alpha/OSF1
““Alto”... para qué ?Alto”... para qué ?
EdiciónEdición de binarios de binarios• Instrumentación ¨Ad-hoc¨Instrumentación ¨Ad-hoc¨• Visualización de códigoVisualización de código
CompilaciónCompilación a bajo nivel a bajo nivel• Alto IR es el Alpha ISAAlto IR es el Alpha ISA• Optimizaciones “hardware-oriented”Optimizaciones “hardware-oriented”
A favor...A favor...
Código fuente Código fuente disponibledisponible Eliminación del “front-end”Eliminación del “front-end”
• Fichero de entrada: Fichero de entrada: ejecutableejecutable– IndependenciaIndependencia del lenguaje de programación del lenguaje de programación
Funcionamiento con/sin “Funcionamiento con/sin “profilingprofiling””
No hay cambios en la metodología!No hay cambios en la metodología!
En contra...En contra...
Código Código en fase de desarrolloen fase de desarrollo• Zonas de código “inhibido”Zonas de código “inhibido”• No es portableNo es portable
Binario final no ¨pixificable¨Binario final no ¨pixificable¨ Consume Consume muchos recursosmuchos recursos
• Ej: Spec95 - 126.gccEj: Spec95 - 126.gcc– >1/2 Gb de memoria (xdisk)>1/2 Gb de memoria (xdisk)– 20-30´ de compilación20-30´ de compilación
Talk outlineTalk outline
IntroducciónIntroducción Usando Usando “Alto”“Alto” Fases de Fases de “Alto”“Alto” Modificando Modificando “Alto”“Alto”
InstalaciónInstalación ““Alto”Alto” URL URL
• http://www.cs.arizona.edu/altohttp://www.cs.arizona.edu/alto
Última release pública: Agosto 1999 !!Última release pública: Agosto 1999 !!
EjecutablesEjecutables• altoalto• {profadder}{profadder}• {profdump}{profdump}
CompilaciónCompilación• more READMEmore README• vi Makefilevi Makefile• ......• gmake headersgmake headers• gmakegmake
Benchmarks Benchmarks
Binarios de entradaBinarios de entrada• Compilados Compilados estáticamenteestáticamente• Con “Con “rellocation rellocation information”information”
Limitaciones de Limitaciones de “Alto”“Alto”• Mejor preparado para código Mejor preparado para código 2116421164
– arch ev5arch ev5
• Global Pointer (GP) Global Pointer (GP) únicoúnico
Compilación de benchmarks Compilación de benchmarks
Opciones de compilaciónOpciones de compilación
• cc -Wl,-r -Wl,-d -Wl,-z -non_sharedcc -Wl,-r -Wl,-d -Wl,-z -non_shared• f77 -Wl,-r -Wl,-d -Wl,-z -non_sharedf77 -Wl,-r -Wl,-d -Wl,-z -non_shared• gcc -Wl,-r -Wl,-d -Wl,-z -staticgcc -Wl,-r -Wl,-d -Wl,-z -static• g++ -Wl,-r -Wl,-d -Wl,-z -staticg++ -Wl,-r -Wl,-d -Wl,-z -static
• chmod +x ...chmod +x ...
Invocando “Alto”Invocando “Alto”
Optimizar un ejecutableOptimizar un ejecutable• alto -i <ifile> -o <ofile>alto -i <ifile> -o <ofile>
Opciones de invocaciónOpciones de invocación• +300+300 “valores” “valores” no documentados!!! no documentados!!!• Ej: Ej: alto -V Phase+Status …alto -V Phase+Status …
OpciónOpción ValorValor ValorValorConcatenadorConcatenadorde valoresde valores
Opciones útilesOpciones útiles
-V Phase+Status+...-V Phase+Status+...
-P Loop+Bbl+Fun+...-P Loop+Bbl+Fun+...
-T Preproc+Postasm+...-T Preproc+Postasm+...
-O Peep+Inline+...-O Peep+Inline+...
-r <number>-r <number>
-C <number>-C <number>
-L Sensitive|...-L Sensitive|...
-M Crit|Path|...-M Crit|Path|...
-p Bbl+Fun+...-p Bbl+Fun+...
Verbose infoVerbose info
Print “what”Print “what”
Print “when”Print “when”
Disable optimizationsDisable optimizations
Number of rounds Number of rounds
Cache size (#instr)Cache size (#instr)
Liveness methodLiveness method
Inline methodInline method
Profile “what”Profile “what”
Talk outlineTalk outline
IntroducciónIntroducción Usando Usando “Alto”“Alto” Fases de Fases de “Alto”“Alto” Modificando Modificando “Alto”“Alto”
Bibliografía… :-)Bibliografía… :-)
Bibliografía básicaBibliografía básica• Aho, Sethi, Ullman.Aho, Sethi, Ullman. Compilers - Principles, Compilers - Principles,
Techniques and Tools. Techniques and Tools. Addison Wesley, 1986.Addison Wesley, 1986.• Muchnick.Muchnick. Advanced Compiler Design and Advanced Compiler Design and
Implementation. Implementation. Morgan Kaufman, 1997.Morgan Kaufman, 1997.
““Alto”Alto” web page web page• Muth, Debray, Watt., De Boss.Muth, Debray, Watt., De Boss. alto: A Link-Time alto: A Link-Time
Optimizer for the DEC Alpha. Optimizer for the DEC Alpha. TR98-14, 1998.TR98-14, 1998.• Muth.Muth. alto: A Platform for Object Code Modification. alto: A Platform for Object Code Modification.
PhD. Dissertation, 1999.PhD. Dissertation, 1999.
Fases del compiladorFases del compilador
LoadingLoading phase phase• Lee el binario y contruye el CFGLee el binario y contruye el CFG
OptimizationOptimization phase phase• Optimizaciones locales/globalesOptimizaciones locales/globales
AssemblyAssembly phase phase• Generación de códigoGeneración de código
CFG: Control flow graphCFG: Control flow graph
Loading phaseLoading phase
LecturaLectura del binario del binario• ““Rellocation information” (func & bbl)Rellocation information” (func & bbl)
ConstrucciónConstrucción del CFG del CFG• Algoritmo clásicoAlgoritmo clásico• Funciones, BBs y aristasFunciones, BBs y aristas• Optimizaciones Optimizaciones trivialestriviales
– Elimina el cálculo del GPElimina el cálculo del GP– Normaliza operacionesNormaliza operaciones– ......
Construcción del CFGConstrucción del CFG
call call nodenode
call call nodenode
init init nodenode
init init nodenode
return return nodenode
return return nodenode
exit exit nodenode
exit exit nodenode
callercaller calleecalleecall call
edgeedge
return return edgeedge
link edgelink edge
““Pseudo” funcionesPseudo” funciones
call call nodenode
call call nodenode
hell hell nodenode
hell hell nodenode
return return nodenode
return return nodenode
callercaller
HELLHELLcall call edgeedge
return return edgeedge
link edgelink edge
jsr r26,(r27)jsr r26,(r27)......
““Pseudo” funcionesPseudo” funciones
HELLHELL HELL-LITEHELL-LITE
CALLCALL PALPAL
jmp r31,(r28)jmp r31,(r28)
jsr r26,(r27)jsr r26,(r27) call_pal callsyscall_pal callsys
relocate relocate basic blockbasic block
relocate relocate functionfunction
Optimization phaseOptimization phase
Easy Easy OptimizationsOptimizations
Easy Easy OptimizationsOptimizations
#rounds#rounds
Hard Hard OptimizationsOptimizations
Hard Hard OptimizationsOptimizations
Easy Easy OptimizationsOptimizations
Easy Easy OptimizationsOptimizations
#rounds#roundsEasyEasy
Optimizaciones Optimizaciones sencillas sencillas iterativamenteiterativamente
HardHard
Optimizaciones Optimizaciones aplicadas una aplicadas una
sola vezsola vez
Easy optimizationsEasy optimizations
Register liveness analysisRegister liveness analysis
Unreacheable code eliminationUnreacheable code elimination
Peephole optimizationsPeephole optimizations
Partial evaluationPartial evaluation
Branch optimizationsBranch optimizations
Constant propagationConstant propagation
Jump table analysisJump table analysis
Copy propagationCopy propagation
Stack usage patternsStack usage patterns
Alias analysisAlias analysis
Load/store avoidanceLoad/store avoidance
Code compressionCode compression
Basic block replicationBasic block replication
Inline small functionsInline small functions
Common subexpression eliminationCommon subexpression elimination
Register renamingRegister renaming
liveness.cliveness.c
opt.misc.copt.misc.c
peephole.cpeephole.c
eval.ceval.c
opt.branch.copt.branch.c
opt.constant.copt.constant.c
opt.switch.copt.switch.c
opt.propagation.copt.propagation.c
opt.stack.copt.stack.c
aliasing.caliasing.c
opt.loadstore.copt.loadstore.c
opt.compress.copt.compress.c
opt.dupbbl.copt.dupbbl.c
opt.inline.copt.inline.c
opt.cse.copt.cse.c
opt.regrealloc.copt.regrealloc.c
Hard optimizationsHard optimizations
Shrink-wrappingShrink-wrapping
CloningCloning
InliningInlining
Value profilingValue profiling
Code compressionCode compression
Stack mergingStack merging
opt.shrinkwrap.copt.shrinkwrap.c
opt.dupfun.copt.dupfun.c
opt.inline.copt.inline.c
opt.inline.indir.copt.inline.indir.c
opt.inline.jumps.copt.inline.jumps.c
opt.valprof.copt.valprof.c
factor.bbl.cfactor.bbl.c
factor.prolog.cfactor.prolog.c
opt.stack.copt.stack.c
Muchas de ellas Muchas de ellas inhibidasinhibidas !!! !!!
Assembly phaseAssembly phase
Code layoutCode layout• Dirigido por profiling (si disponible...)Dirigido por profiling (si disponible...)
SchedulingScheduling• 21164 oriented21164 oriented• Extended basic blocksExtended basic blocks• BB alignmentBB alignment
Generación de códigoGeneración de código
Talk outlineTalk outline
IntroducciónIntroducción Usando Usando “Alto”“Alto” Fases de Fases de “Alto”“Alto” Modificando Modificando “Alto”“Alto”
Code guidelinesCode guidelines
Space-efficientSpace-efficient (vs. speed) (vs. speed)• Preferible recalcular a almacenarPreferible recalcular a almacenar• Evita el uso de punterosEvita el uso de punteros
– Manipulación de elementos sobre listasManipulación de elementos sobre listas– Implementación de listas sobre vectoresImplementación de listas sobre vectores
Uso intensivo de Uso intensivo de macros macros !!!!!!• Aumenta la legibilidad del códigoAumenta la legibilidad del código
Include filesInclude files
Log informationLog information
Fun/BB/Instr flagsFun/BB/Instr flags
Register file definitionsRegister file definitions
All data structures & macrosAll data structures & macros
COFF binary file managementCOFF binary file management
ELF binary file managementELF binary file management
Alpha ISA opcodesAlpha ISA opcodes
(generado automaticamente de (generado automaticamente de table.ctable.c))
error.herror.h
flags.hflags.h
regs.hregs.h
global.hglobal.h
system.coff.hsystem.coff.h
system.elf.hsystem.elf.h
opcode.hopcode.h
Estructuras de datosEstructuras de datos
Fichero Fichero global.hglobal.h Declaración de Declaración de estructurasestructuras
• Todo son arrays globalesTodo son arrays globales– Funciones / BBs / InstruccionesFunciones / BBs / Instrucciones
• Acceso a traves de macrosAcceso a traves de macros Declaración de Declaración de macrosmacros Declaración de límites de arraysDeclaración de límites de arrays
• Mucha memoria - Recompilar ??!!Mucha memoria - Recompilar ??!!
Command line optionsCommand line options
Módulo Módulo cmdline.ccmdline.c Variable globalVariable global
• Valores por Valores por defectodefecto para opciones para opciones Declaración de arrays globalesDeclaración de arrays globales
• Declaración estática !!!Declaración estática !!!• Mejor si sustituimos por “malloc”´s...Mejor si sustituimos por “malloc”´s...
Lectura de comandosLectura de comandos
Alpha ISAAlpha ISA
Modulo Modulo table.ctable.c• Similar al Similar al alpha.defalpha.def del SimpleScalar del SimpleScalar
• wh64wh64 missing!!! missing!!!
0x10,0x10,0x00,0x00,I_addl,I_addl,““addl”,addl”,IT_IOP,IT_IOP,RES_PC,RES_PC,0,0,PIPE_E0|PIPE_E1,PIPE_E0|PIPE_E1,1,1,11
Opcode numberOpcode numberFunction numberFunction numberOpcode nameOpcode nameAssembly nameAssembly nameTypeTypeResource usageResource usageResource definitionResource definitionPipeline usagePipeline usageLatency averageLatency averageLatency highLatency high
Ejemplo: remove NOPsEjemplo: remove NOPs#undef __PROC__#undef __PROC__#define __PROC__ “OptEliminateNoops”#define __PROC__ “OptEliminateNoops”
extern BOOL OptEliminateNoops(FILE *fp)extern BOOL OptEliminateNoops(FILE *fp){{ INDEX iins;INDEX iins; NUMBER kcount = 0;NUMBER kcount = 0; BOOL verbose = HasOption(PRINT_OPT_VERBOSE,”Noop”);BOOL verbose = HasOption(PRINT_OPT_VERBOSE,”Noop”);
FOREACH_LIVE_INS(iins)FOREACH_LIVE_INS(iins) {{ if( AinsIsNoop(iins) ) /* kill noops */if( AinsIsNoop(iins) ) /* kill noops */ {{ if( verbose )if( verbose ) {{ fprintf(fp,”\tKilling: “);fprintf(fp,”\tKilling: “); PrintIns(fp,iins);PrintIns(fp,iins); }}
kcount++;kcount++; AinsKill(iins);AinsKill(iins); }}
......
Ejemplo: remove NOPsEjemplo: remove NOPs
......
/* kill useless moves *//* kill useless moves */
if( AINS_CODE(iins) == I_lda &&if( AINS_CODE(iins) == I_lda && AINS_DATA(iins) == 0 &&AINS_DATA(iins) == 0 && AINS_REG_B(iins) == AINS_REGC(iins) ) )AINS_REG_B(iins) == AINS_REGC(iins) ) ) {{ if( verbose )if( verbose ) {{ fprintf(fp,”\tKilling: “);fprintf(fp,”\tKilling: “); PrintIns(fp,iins);PrintIns(fp,iins); }}
kcount++;kcount++; AinsKill(iins);AinsKill(iins); }} }}
InfoStatus(fp,”\t[OptNoop] Killed Noops %d\n”, kcount);InfoStatus(fp,”\t[OptNoop] Killed Noops %d\n”, kcount);
return (kcount>0);return (kcount>0);}}
The EndThe EndThe EndThe End