Post on 08-Jan-2016
description
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones
Representacin IntermediaGenerador de CdigoHigh-level IRAnalizador Lxico (Scanner)Analizador Sintctico (Parser)Token StreamArbol de ParseoLow-level IRGenerador de Cdigo IntermedioAssembler & linkerEjecutable BinarioProcesador
Overview de un Procesador ModernoALUControlMemoryRegistersMemoryRegistersALUControl
Memory LayoutInicio del StackManejo del Heapfree listsPosicin de inicio en segmento de textStackText segmentHeapObjetosArrayslocales(parmetros)
0x7fffffff0x400000Reserved
StackGuarda parmetros y variables localesCada invocacin obtiene una nueva copiaCaller necesita guardar Todo registro caller-saved que est siendo usadoCualquier parmetro pasadoReturn address (cundo se toman branches)Callee debe guardarDireccin del stack pointer anteriorFrame pointer y global area pointer anterioresTodo registro callee saved que est siendo usado
StackDireccin del n-simo argumento es -(n-4)*4*$fpVariables locales son un offset constante negativo de $fpreturn addressold frame pointerLocal variablesCalliee savedregistersStack temporaries... argument 5argument 4
Dynamic areafpsp
StackAl llamar a un nuevo procedimieto, el caller:Push cualquier t0-t9 que tiene un valor importante al stackPone los argumentos 1-4 en a0-a3Push del resto de argumentos al stack Hace un jal o jalrreturn addressold frame pointerLocal variablesCalliee savedregistersStack temporaries... argument 5argument 4
Dynamic areaCaller saved registers arguments
fpsp
StackEn el procedimiento, el callee al principio:push $fp al stackcopiar $sp a $fppush $ra al stackSi algn s0-s7 es usado en el proc, meterlo al stackCrear espacio para variables locales en el stackEjecutar el callee...return addressold frame pointerreturn addressold frame pointerLocal variablesCalliee savedregistersStack temporaries... argument 5argument 4
Dynamic areaLocal variablesCalliee savedregistersCaller saved registers arguments
Dynamic areafpsp
StackEn el procedimiento, el callee al final:Pone valores de retorno en v0,v1actualizar $sp usando $fp Pop los registros callee-saved del stackrestaurar $ra del stackrestaurar $fp del stackejecutar jr ra y retornar al callerreturn addressold frame pointerLocal variablesCalliee savedregistersStack temporaries... argument 5argument 4
Dynamic areaCaller saved registers arguments
fpsp
StackAl regresar de una llamada a procedimiento, el caller:actualiza $sp para ignorar los argumentospop los registros caller-savedContinuar...return addressold frame pointerLocal variablesCalliee savedregistersStack temporaries... argument 5argument 4
Dynamic areafpsp
Registros9
Sheet1
0zerohard-wired to zero
1atReserved for asm
2 - 3v0 - v1expr. eval and return of results
4 - 7a0 - a3arguments 1 to 4
8-15t0 - t7caller saved temporary
16 - 23s0 - s7calliee saved temporary
24, 25t8, t9caller saved temporary
28gppointer to global area
29spstack pointer
30fpframe pointer
31rareturn address
Programa Ejemploclass auxmath {int sum3d(int ax, int ay, int az, int bx, int by, int bz) {int dx, dy, dz;if(ax > ay)dx = ax - bx;elsedx = bx - ax; retrun dx + dy + dz;}}
int px, py, pz;px = 10; py = 20; pz = 30;auxmath am;am.sum3d(px, py, pz, 0, 1, -1);return addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??)
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
Creacin de ExpresionesAlgoritmo ingenuo de generacin de cdigo para x = y op zElegir un registro Rsrc1 (digamos $t0) para cargar el valor yGenerar instrucciones para copiar, si y es:En otro registro (digamos $t7) add $t0, $t7, zeroUna constante (digamos 1024)li $t0, 1024 Est en memoria (digamos apuntado por $t7) lw $t0, $t7 En una direccin simblica (digamos lab1) la $t0, lab1Elegir registro Rsrc2 (digamos $t1) y cargar el valor zElegir registro Rdest (digamos $t2) para guardar xHacer la operacin (digamos and) and $t2, $t1, $t0
Programa Ejemploclass auxmath {int sum3d(int ax, int ay, int az, int bx, int by, int bz) {int dx, dy, dz;if(ax > ay)dx = ax - bx;
spreturn addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??) add $t0, $a1, zerolw$t1, 0($fp)sub$t2, $t0, $t1sw$t2, -12($fp) addresssrc1src2dest
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
t2??
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
Generacin de Control de FlujoAplanar la estructura de control Usamos una templateCrear etiquetas nicas para los puntos donde se une el control (joins)Luego generar el cdigo apropiado
Template para condicionalesif (test)true_bodyelsefalse_body
boper , lab_truejlab_endlab_true:lab_end:
Programa Ejemplo
if(ax > bx)dx = ax - bx;elsedx = bx - ax;return addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??) addresssrc1src2dest
boper..., ..., lab0
jlab1lab0:
lab1:12
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
t2??
Programa Ejemplo
if(ax > bx)dx = ax - bx;elsedx = bx - ax;return addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??) addresssrc1src2dest
add$t0, $a1, zerolw$t1, 0($fp)bgt$t0, $t1, lab0
jlab1lab0:
lab1:13
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
t2??
Programa Ejemplo
if(ax > bx)dx = ax - bx;elsedx = bx - ax;return addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??) addresssrc1src2dest
add$t0, $a1, zerolw$t1, 0($fp)bgt$t0, $t1, lab0lw$t0, 0($fp) add$t1, $a1, zerosub$t2, $t0, $t1sw$t2, -12($fp)jlab1lab0:
lab1:
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
t2??
Programa Ejemplo
if(ax > bx)dx = ax - bx;elsedx = bx - ax;return addressold frame pointerDynamic areaCaller saved registers Argument 7: bz (-1)fpspArgument 6: by (1)Argument 5: bx (0)Local variable dx (??) Local variable dy (??) Local variable dz (??) addresssrc1src2dest
add$t0, $a1, zerolw$t1, 0($fp)bgt$t0, $t1, lab0lw$t0, 0($fp) add$t1, $a1, zerosub$t2, $t0, $t1sw$t2, -12($fp)jlab1lab0:add$t0, $a1, zerolw$t1, 0($fp)sub$t2, $t0, $t1sw$t2, -12($fp)lab1:15
Sheet1
v0??
v1??
a0this
a1ax (10)
a2ay (20)
a3az (30)
v0??
v1??
t0??
t1??
t2??
Template para loops whilewhile (test)body
Template para loops whilewhile (test)body
lab_cont:boper , lab_bodyjlab_endlab_body:jlab_contlab_end:
Template para loops whilewhile (test)body
lab_cont:boper , lab_bodyjlab_endlab_body:jlab_contlab_end: An optimized template16
Pregunta:Cul es la template para?
dobodywhile (test)
17
Pregunta:Cul es la template para?
dobodywhile (test)
lab_begin:boper , lab_begin
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
Llamada a ProcedimientoDynamic areaCaller saved registers arguments
sp
Llamada a ProcedimientoEn el procedimiento, el callee al principio:push $fp al stackcopiar $sp a $fppush $ra al stackSi algn s0-s7 es usado en el proc, meterlo al stackCrear espacio para variables locales en el stackEjecutar el callee...19
Llamada a ProcedimientoEn el procedimiento, el callee al principio:push $fp al stackcopiar $sp a $fppush $ra al stackSi algn s0-s7 es usado en el proc, meterlo al stackCrear espacio para variables locales en el stackEjecutar el callee...proc_entry:sw$fp, -4($sp)add $fp, $sp, zeroaddi $sp, $sp, -8sw$ra, ($sp)20
Llamada a ProcedimientoEjecutar el cuerpo del procedimiento llamadoAcceso a variables locales y parmetros como offsets del $fp. . .
Llamada a ProcedimientoEn el procedimiento, el callee al final:Pone valores de retorno en v0,v1actualizar $sp usando $fp Pop los registros callee-saved del stackrestaurar $ra del stackrestaurar $fp del stackejecutar jr ra y retornar al caller. . .
Llamada a ProcedimientoEn el procedimiento, el callee al final:Pone valores de retorno en v0,v1actualizar $sp usando $fp Pop los registros callee-saved del stackrestaurar $ra del stackrestaurar $fp del stackejecutar jr ra y retornar al caller. . .add$v0, $t2, zeroadd$sp, $fp, zerolw$ra, -8($Sp)lw$fp, -4($sp)jr$ra22
Llamada a Procedimiento proc_entry:sw$fp, -4($sp)add $fp, $sp, zero addi $sp, $sp, -8sw$ra, ($sp) . . .
add$v0, $t2add$sp, $fp, 0lw$ra, -8($Sp)lw$fp, -4($sp)jr$ra return addressold frame pointerDynamic areaLocal variablesCalliee savedregistersCaller saved registers arguments
Dynamic areasp
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
SmbolosEjecutable es una coleccinCompilaciones separadasLibreras linkeadas esttica y dinmicamentePor lo tanto no podemos crear la imagen de memoria en tiempo de compilacinSe necesita una fase adicional de linker para juntar todo y crear la imagen final de memoria
Salida del CompiladorCrear cdigo objeto con direcciones simblicas que pueden ser reposicionadasLas direcciones simblicas de todos los datos y del principio de procedimientos que otros necesitan accesar son exportadasExportar los nombres de smbolos para referencias externas
Smbolos exportados por el CompiladorSymbols from test.o:
[Index] Value Class Type Section Name[0]| 0| File |ref=6 |Text | test.c[1]| 0| Proc |end=3 int |Text | main[2]| 56| Proc |end=5 int |Text | fib[3]| 0| Global | |Bss | internal_var[4]| 0| Proc |ref=1 |Text | main[5]| 56| Proc |ref=3 |Text | fib[6]| 0| Global | |Undefined| external_var[7]| 0| Proc | |Undefined| foo[8]| 0| Global | |Undefined| _gp_disp
LinkerVe en todos los object files para encontrar smbolos no resueltosHace corresponder los smbolos y saca las partes necesarias de las librerasHace el Layout en una sola imagen de memoriaResuelve todos los nombres simblicos a las direcciones y offsets adecuados de memoria
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
Anatoma de un CompiladorOptimizador de Cdigo IntermedioGenerador de CdigoGenerador de Cdigo IntermedioAnalizador Lxico (Scanner)Analizador Sintctico (Parser)Arbol de Parseo
Programa Ejemplo
int expr(int n){ int d; d = 4 * n * n * (n + 1) * (n + 1); return d;}
Programa Ejemplolda $30,-32($30)stq $26,0($30)stq $15,8($30)bis $30,$30,$15bis $16,$16,$1stl $1,16($15)lds $f1,16($15)sts $f1,24($15)ldl $5,24($15)bis $5,$5,$2s4addq $2,0,$3ldl $4,16($15)mull $4,$3,$2ldl $3,16($15)addq $3,1,$4mull $2,$4,$2ldl $3,16($15)addq $3,1,$4mull $2,$4,$2stl $2,20($15)ldl $0,20($15)br $31,$33$33:bis $15,$15,$30ldq $26,0($30)ldq $15,8($30)addq $30,32,$30ret $31,($26),1
Cdigo Optimizados4addq $16,0,$0mull $16,$0,$0addq $16,1,$16mull $0,$16,$0mull $0,$16,$0ret $31,($26),1
Cdigo No Optimizado
Qu es un Optimizador?Transforma un cmputo a un cmputo equivalente, pero mejorPero nunca ptimoAcelera los programas execution time = instruction count * cycles per instructionMinimiza el nmero de operacionesReemplaza las operaciones caras con operaciones ms baratasMinimiza los cache missesMinimiza el tamao del object codeReduce el consumo de poder28
Por qu usar un Optimizador?Generar cdigo tan bueno como si lo hubiera codificado a mano un buen programadorObtener rendimiento estable y robustoAbstraer la arquitectura del programadorExplotar las fortalezas arquitecturalesEsconder las debilidades arquitecturalesSoporte amplio y eficiente de las facilidades del lenguaje
29
Por qu usar un Optimizador?Los programadores slo tienen que preocuparse de que el algoritmo este correcto
El optimizador del compilador va a:Hacer que el programa sea muy rpidomake the program blazingly fastencargarse de los detalles de la arquitectura30
Las Arquitecturas Modernas asumen un buen soporte del CompiladorCambio de diseo de CISC a RISCCISC tena instrucciones ms cercanas a los lenguajes de alto nivelRISC tiene instrucciones simples (se necesitan un montn para ejecutar construcciones de alto nivel)Arquitecturas SuperescalaresNecesitan calendarizacin de instruccionesCasi imposible de hacer a manoMquinas de Vectores y ParalelasSe necesita que el compilador vectorice/paralelice las aplicaciones31
Problemas al desarrollar un CompiladorVelocidad de CompilacinPuede que los algoritmos no escalenCalidad de los resultadosQue los resultados sean correctosSuposiciones implcitasEstabilidad numricaCompiladores son complejos pueden tener bugsQue se puedan debuggear32
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
Anlisis de ProgramasPara poder optimizar un programa, necesitamos entender el programaEstructura del ProgramaUso de los DatosComportamiento Lgicoreverse engineer del cdigo al algoritmo
Anlisis de ProgramasAnlisis de Control de FlujoAnlisis de Flujo de DatosAnlisis de Dependencia de DatosAnlisis de AliasAnlisis Entre Procedimientos (interprocedural)Profile FeedbackProvee informacin acerca del uso del programa
Optimizaciones a ProgramasLas categorizamos en:Optimizaciones ClsicasEliminacin de RedundanciaOptimizaciones de LoopsOptimizaciones de ProcedimientosAsignacin de Registros y Calendarizacin de InstruccionesSimilar a la clasificacin del libro de la Ballena
Muchas otras Optimizaciones AvanzadasOptimizaciones de Programa CompletoOptimizaciones para Jerarquas de MemoriaParalelizacin y VectorizacinOptimizaciones especficas a la arquitecturaOptimizaciones para Consumo de PoderOptimizaciones para Mejorar/Garantizar SeguridadMucha investigacin en curso
Optimizaciones ClsicasConstant FoldingAlgebraic SimplificationCopy PropagationConstant Propagation
Eliminacin de RedundanciaCommon-Subexpression EliminationPartial Redundancy EliminationCode Hoisting
Optimizaciones de LoopsLoop Invariant Code MotionStrength ReductionBounds Checking Elimination
Optimizaciones de ProcedimientosTail Recursion EliminationMethod InliningLeaf-Routine Optimization
Register Allocation and Instruction Scheduling Register AllocationBasic Block SchedulingList or Trace SchedulingLoop UnrollingSoftware PipeliningSpeculative Scheduling
ResumenOverviewGeneracin de Control de FlujoGeneracin de ProcedimientosLinkingIntroduccin a OptimizacionesTaxonoma de OptimizacionesEjemplo de Optimizaciones5
...lw $t0, 4($fp)# ymul $t1, $t0, a1# b*ylw $t2, 0($fp)# xadd $t2, $t2, $t1# x = x + b*ysw $t2, 0($fp)lw $t0, 8($fp)# iaddui$t0, $t0, 1# i+1sw $t0, 8($fp)ble $t0, $a3, lab1lw $v0, 0($fp)addu $fp, 16b $ra
47
Dead Code Eliminationint sumcalc(int a, int b, int N){ int i; int x, y, t; x = 0;
for(i = 0; i
Dead Code Eliminationint sumcalc(int a, int b, int N){ int i; int x, t; x = 0;
for(i = 0; i
Loop Invariant Removalint sumcalc(int a, int b, int N){ int i; int x, t; x = 0;
for(i = 0; i
Register Allocation
Register Allocation$t9 = X$t8 = t$t7 = u$t6 = v$t5 = i fpLocal variable X Local variable Y Local variable I
test:subu $fp, 16add $t9, zero, zero sll $t0, $a0, 2div $t7, $t0, $a1 add $t6, zero, zero add $t5, zero, zero lab1: addui $t8, $t5, 1 mul $t0, $t8, $t8 addu $t1, $t0, $t6 addu $t9, t9, $t1 addu $6, $6, $7 addui $t5, $t5, 1 ble $t5, $a3, lab1addu $v0, $t9, zeroaddu $fp, 16b $ra
test:subu $fp, 16sw zero, 0($fp) sw zero, 4($fp) sw zero, 8($fp) lab1: mul $t0, $a0, 4 div $t1, $t0, $a1 lw $t2, 8($fp) mul $t3, $t1, $t2 lw $t4, 8($fp) addui $t4, $t4, 1 lw $t5, 8($fp) addui $t5, $t5, 1 mul $t6, $t4, $t5 addu $t7, $t3, $t6 lw $t8, 0($fp) add $t8, $t7, $t8 sw $t8, 0($fp)lw $t0, 4($fp) mul $t1, $t0, a1 lw $t2, 0($fp) add $t2, $t2, $t1 sw $t2, 0($fp)lw $t0, 8($fp) addui $t0, $t0, 1 sw $t0, 8($fp)ble $t0, $a3, lab1lw $v0, 0($fp)addu $fp, 16b $ra
Cdigo No OptimizadoCdigo Optimizado
LecturasLa BallenaCaptulos 7 & 11El DragnCaptulos 10.1, 10.2, 10.3, 10.4