com·pil·er (Webster)


1: one that compiles
2: a computer program that translates
 an entire set of instructions written
 in a higher-level symbolic language
 (as COBOL) into machine language before
 the instructions can be executed

les machines virtuelles

une machine virtuelle'' est une machine qui reconnait un certain nombre d'instructions qui ne sont pas forcémentnative'' pour la machine hardware.
Ex: le compilateur C produit du code assembleur qui suppose l'existence d'un ensemble de fonctions système (ex.: les E/S). Donc il produit du code pour la machine virtuelle définie par les instructions hardware, plus les appels système.
On rencontre souvent les machines virtuelles suivantes

• programmes d'application
  
• Langage de programmation evolué
  
• Langage d'assemblage
  
• Noyau du système d'exploitation
  
• Langage machine
  

• C'est un programme qui prend en entrée un autre programme, écrit pour une quelque machine virtuelle, et l'execute sans le traduire.
  

• l'interpréteur VisualBasic,
• le toplevel Ocaml,
• l'interpreteur PERL,
• etc.

• C'est un traducteur, en général d'un langage évolué vers un langage moins expressif.
  
  Quelques exemples:
  • Compilation des expressions régulières (utilisées dans le shell Unix, les outils sed, awk, l'éditeur Emacs et les bibliothèques des langages C, Perl et Ocaml)
  • Minimisation des automates (compilation d'un automate vers un automate plus efficace)
  • De LaTex vers Postscript ou HTML (latex2html/Hevea)
  • De C vers l'assembleur x86 plus les appels de système Unix/Linux
  • De C vers l'assembleur x86 plus les appels de système Win32
  
  La décompilation: on va dans le sens inverse, d'un langage moins structuré vers un langage évolué. Ex: retrouver le source C à partir d'un code compilé (d'un programme C). Applications: piratage, récupération de vieux logiciels.
  
  

Il ne faut pas tricher... un compilateur ne doit pas faire de l'interprétation...
Pourtant, dans certains cas, il est inevitable de retrouver du code interprété dans le code compilé

• printf("I vaut %d\n",i);

  serait à la limite compilable
  

• s="I vaut %d\n"; printf(s,i);

  est plus dur
  
• alors que

  
  void error(char *s)
       { printf(s,i);}
  

  devient infaisable
  

• analyse lexicale (flot de lexemes)
  théorie: langages réguliers
  outils: automates finis
  logiciels: Lex (et similaires)
  
• analyse syntaxique (flot de reductions)
  théorie: langages algébriques
  outils: automates à pile
  logiciels: Yacc (et similaires)
  

• actions sémantiques (contruction de l'arbre de syntaxe abstrait)
  outils: grammaires attribuées
  logiciels: encore Yacc
  
• analyse sémantique (coherence sémantique: vérification de types, d'usage après définition, mise en place des tables des symboles, gestion des environnements etc.) rend l'arbre de syntaxe abstraite décoré et les tables outils: on peut utiliser des gramamires attribuées, ou à la main
  
• traduction en code intermédiaire (souvent un arbre, independant de l'architecture cible)
• linéarisation du code (transformation en liste d'instructions du code intermediaire)
• séléction d'instructions (passage du code intermédiaire à l'assembleur de la machine cible, eventuellement abstrait par rapport aux noms des registres)

• diffèrentes optimisations
  • analyse de vie des variables et allocation des registres
  • optimisation des boucles (déplacement des invariants, transformations affines)
  • function inlining
  • depliement des boucles
  • etc.
• émission du code (production d'un fichier écrit dans l'assembleur de la machine cible)
• assemblage (production de fichiers contenant le code machine)
• édition des liens (production d'un seul fichier executable)

ranger> cat callfact.c


include <stdio.h>

int fact(int i)
if (i==0) return(1);
 else return(i*fact(i-1));;


main()
 printf ("%d",fact(3)); return(0);

ranger> gcc -o callfact callfact.c
ranger> ls -l callfact
-rwxr-xr-x  1 dicosmo    50784 Oct  5 15:43 callfact
-rw-r--r--  1 dicosmo      139 Oct  5 15:42 callfact.c

ranger> gcc -o callfact -v -save-temps callfact.c
Reading specs from /lib/i386/specs
NeXT Computer, Inc. version cc-437.2.6, gcc version 2.5.8
 /lib/i386/cpp-precomp ... callfact.c callfact.i
NeXT DevKit-based CPP 3.1
 /lib/i386/cc1obj callfact.i -o callfact.s
GNU Objective-C version 2.5.8 (80386, BSD syntax) compiled by GNU C version 2.5.8.
 /lib/i386/as -arch i386 -o callfact-callfact.o callfact.s
 ld -o callfact -lcrt0.o -L/lib/i386 callfact-callfact.o -lsys_s


ranger> ls -l callfact
-rwxr-xr-x  1 dicosmo    50784 Oct  5 15:43 callfact
-rw-r--r--  1 dicosmo      139 Oct  5 15:42 callfact.c
-rw-r--r--  1 dicosmo     4524 Oct  5 15:48 callfact.i
-rw-r--r--  1 dicosmo      634 Oct  5 15:48 callfact.s
  

• preprocesseur: cpp traduit callfact.c en callfact.i
• compilateur: cc1obj traduit callfact.i en callfact.s
• assembleur: as traduit callfact.s en callfact-callfact.o
• éditeur de liens: ld transforme callfact-callfact.o en executable, en résolvant les liens externes

include <stdio.h>

main ()

int i=0;
int j=0;
for (i=0;i<10;i++)
   
    j=6*i;
   ;
printf("Resultat: %d", j);
exit(0);

  

ranger> gcc -o callfact -v -save-temps simplaffine.c

1 "simpleaffine.c"

1 "/NextDeveloper/Headers/ansi/stdio.h" 1

...
extern int printf ( const char * format , ... ) ;
...

1 "simpleaffine.c" 2

main ( )

int i = 0 ;
int j = 0 ;
for ( i = 0 ; i < 10 ; i ++ )

j = 6 * i ;
 ;
printf ( "Resultat: %d" , j ) ;
exit ( 0 ) ;

.cstring
LC0:
    .ascii "Resultat: %d"
.text
    .align 2,0x90
.globl main
main:
    pushl %ebp
    movl %esp,%ebp
    subl $8,%esp
    pushl %ebx
    movl $0,-4(%ebp)
    movl $0,-8(%ebp)
    movl $0,-4(%ebp)
L2:
    cmpl $9,-4(%ebp)
    jg L3
    movl -4(%ebp),%eax
    movl %eax,%ecx
    movl %ecx,%edx
    addl %ecx,%edx
    addl %eax,%edx
    movl %edx,%eax
    addl %edx,%eax
    movl %eax,-8(%ebp)
L4:
    incl -4(%ebp)
    jmp L2
    .align 2,0x90

L3:
    movl -8(%ebp),%ebx
    pushl %ebx
    pushl $LC0
    call printf
    addl $8,%esp
    pushl $0
    call exit
    addl $4,%esp
    .align 2,0x90
L1:
    movl -12(%ebp),%ebx
    movl %ebp,%esp
    popl %ebp
    ret


  

Le compilateur arrive a faire tenire tout dans des registres, et trouve une façon plus efficace pour multiplier par 6.

.cstring
LC0:
    .ascii "Resultat: %d"
.text
    .align 2,0x90
.globl main
main:
    pushl %ebp
    movl %esp,%ebp
    xorl %edx,%edx
    .align 2,0x90
L5:
    leal (%edx,%edx,2),%eax
    addl %eax,%eax
    incl %edx
    cmpl $9,%edx
    jle L5
    pushl %eax
    pushl $LC0
    call printf
    pushl $0
    call exit
    .align 2,0x90

.cstring
LC0:
    .ascii "Resultat: %d"
.text
    .align 2,0x90
.globl main
main:
    pushl %ebp
    movl %esp,%ebp
    xorl %eax,%eax
    xorl %ecx,%ecx
    .align 2,0x90
L5:
    movl %ecx,%edx
    leal 6(%edx),%ecx
    incl %eax
    cmpl $9,%eax
    jle L5
    pushl %edx
    pushl $LC0
    call printf
    pushl $0
    call exit
    .align 2,0x90

• analyse lexicale, usage de (Ocaml)Lex
• analyse syntaxique, usage de (Ocaml)Yacc
• generation de l'arbre de syntaxe abstraite
• analyse semantique
• blocs d'activation pour fonctions/variables locales
• traduction en code intermediaire
• optimisations
• emission de code

TD

: Antonio Bucciarelli, buccia@pps.jussieu.fr

Contrôle continu

: partiel sous forme de projet à rendre pour le 15 decembre

Langage utilisé

: Ocaml 2.04 ou plus recent (disponible librement par ftp depuis l'Inria ftp.inria.fr)

Machine cible

: à decider, soit le 486, utilisé en mode RISC, soit un emulateur MIPS; ce choix n'est pas essentiel pour la première partie du cours.

• Modern Compiler Implementation in ML, Andrew W. Appel, Cambridge University Press, 1998 (disponible en bibliotheque)
• Notes de cours: Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, Mass. 1986
• Manuel Ocaml en ligne.
• Livre "Développement d'applications avec Objective Caml" sur Ocaml: (disponible en bibliotheque)

This document was translated from L^AT_EX by H^EV^EA et modifié à la main.