La compilation logicielle d’Esterel v5
Gérard Berry
Chaire Algorithmes, machines et langages
Collège de France
Cours 4, 23 avril 2013
G. Berry, Collège de France 23/04/2013 2
Rappel : Esterel noyau
p q p q
p p
p q
nothing
emit !
pause
present then else ? ,
suspend when
; ;
|| |
loop end *
trap in end { }
ex
0
1
T
kT kit
sign
p q
p q
al
s s
s s
s s
s in
p q
p p
p p
p
p end p\s
G. Berry, Collège de France 23/04/2013 3
Rappel : codes de retour
Si deux traps sont levés enmême temps, seul le plus extérieur compte
trap T in trap U in
nothing0
||
pause1
||
exit U2
||
exit T3
end trap||
exit T2
end trap
Code de retour du parallèle
max des codes des branches
(codage de Gonthier)
G. Berry, Collège de France 23/04/2013 4
Rappel : sémantique comportementale
pE
E’ kp’
signaux reçus
signaux émis code de retour
Diffusion : E’ E
0 : terminaison1 : pause2 : sortie d’un niveau de trap3 : sortie de deux niveaux de trap
k
G. Berry, Collège de France 23/04/2013 5
Rappel : les règles problématiques
si une seule règle s’applique => déterminismeMais si les deux s’appliquent, problème !
E's E s E
,,
,\
'E
E '
p p'
p s
k
\p'sk
E
absence
E' {s}s E s E '
E {s}E '
p p
s
'
p
k,
sE,k
,
p'\ \présence
G. Berry, Collège de France 23/04/2013 6
Rappel : cycles de causalité
• if s then emit s ?! ,0 s s s s
• if s else emit s s s ?0, ! s s
contradiction pour la causalité
pas contradictoire, mais deux choix possibles
• if s then emit s else emit s s s s s! ,! s? s
pas contradictoire, un seul choix possiblemais problématique car non constructif !
Hamlet : ToBe ToBe or not ToBe
G. Berry, Collège de France 23/04/2013 7
Propagation constructive : Must et Cannot emit x
|| if not x then emit y
|| if not y then emit z
Must emit x
|| if not x then emit y
|| if not y then emit z
car les émetteursde y ont disparu
Cannot emit x
|| if not x then emit y
|| if not y then emit z
emit x
|| if not x then emit y
|| if not y then emit z
Must
x y z
x y z
x y z
x y z
G. Berry, Collège de France 23/04/2013 8
Règles constructives pour p \ s
p p' pE
s Canno(t ,E)E
E '
k
ks s
E
,
,p\ p'\
absence
E' {s}s Must ,E
E {s}E '
s
(p,
,\
kp' p
pE
k
)
p'\sprésence
Déterministe car Mus(t ,E) Canno(t , )p p E
G. Berry, Collège de France 23/04/2013 9
Acceptation des bons cycles
XY xor YXgrâce au if
if I then if X then emit Yelse if Y then emit Xend
if X then emit Y;pause ;if Y then emit X
XY xor YXgrâce au pause
Comme pour l’analyse constructivedes circuits cycliques, cf. cours 1 et séminaire Ledinot
G. Berry, Collège de France 23/04/2013 10
La sémantique constructive : Must
,Mus(t , ) ( MuE Mus st, ) (t Ep p,E)p
Ce que doit faire une instructiondans un environnement donné
signaux devantêtre émis
code devantêtre retourné
G. Berry, Collège de France 23/04/2013 11
La sémantique constructive : Can
m m m,Can ( , ) ( , ) ( , )
si doit êtr
p p p
p
p
e exécuté
avec m si ne peut pas être exéc
E Can
uté
C
s
EaE n
inon
signaux pouvantêtre émis
codes pouvantêtre retournés
Ce que peut faire une instructiondans un environnement donné
G. Berry, Collège de France 23/04/2013 12
m ,Mus(t , ) Can ( , )k k {k}E E
m ,Mus(t ! , ) Can (s E s E {s, }! {0})
Mus(t , ) si
Mus(t( ? , ), ) Mu
E s E
s(t , ) si
,
p
p q q
si n
E s
n
E
o
s E
m
m m
Can ( , ) si
Can (( ? , ), ) Can ( , )
E s E
s E E s E
E
si
Can ( , ) Can ( , ) s
p
p q q
p E si q E
13G. Berry, Collège de France 23/04/2013
m m
Mus(t , ) Mus(t , )
Can ( , )
ps E
C
E
s E Ea , )
p
p n p(
p p
p q p q
Mus(t , ) si ( , )
Mus(t ; , ) ( , ) ( , ), ( , )
0 MuE E
E Must E Mus
st
Mus
q
p s
t
i
t
( ,0
E
t E)
E
Mus
m
m
m m'
m m m'
m
Can ( , )
si ( , )
( , ) ( , ),
Can ( ; , ) ( , ) ( , )
si ( , )
avec m'
0 Can
( Ca
E
E
Can E Can E
E E
si m
p
p
p q
p q n \0) Can
0
et ( , )
et m' sino
E
Can
0 Must
E
E
p q
p
p
n
G. Berry, Collège de France 23/04/2013 14
m m
Mus(t *, ) Mus(t , )
Can ( *, ) Can
Ep p
)p
E
E E( p,
E Must E Must E
Max M
Mus(t
ust
| , ) ( , ) ( , ),
( ( Mu st, ), ( ,
p
E E
p q
p q ))
q
m m
m
m
m
E Can E Can E
Max Can
Can ( p q p q
p
| , ) ( , ) ( , ),
( ( , ) q , ( , E ECa ))n
avec ( ) { ( Max K,K' max k k' k K, ) | , k' K' }
G. Berry, Collège de France 23/04/2013 15
m mm
Mus(t{ }, ) ( , ), ( , )
Can ({ }, )
E Must E E
E Ca ( ,n E)
Mu
, E( , )
p p st p
p p pCan
m m m
Mus(t , ) ( , ), ( , )
Can ( , )
E Must E E
E C (
p p p
p pan E, ), E
Must
Can ,p( )
16G. Berry, Collège de France 23/04/2013
E { s } s
s Must E { s }
E { s
Mus(t , )\
si ( , )
Mus(t , )\Mus(t \ , )
si ( , )
Mus(t
} ss E
,
p
p
pp
)\
sin
s Can E { s }
E { s } s
on
p
p
mm
m
m
E { s } s
s Must E { s }
E
Can( , )\
si m et ( , )
Can ( , )\ { s } ss E
s Can ECan ( \ , )
si ( , )
p
p
pp
p
pCan
{ s }
E {( , )\
si
s } s
non
G. Berry, Collège de France 23/04/2013 17
Réduction comportementale
nothing; if x then pause else emit y end ; emit z
pause; if x then nothing else emit y en ; emit z
pause; if x then nothing else emit y en ; nothing
pause; if x then pause else emit y end ; emit z
, 1
{x} , 1
{z}, 1
G. Berry, Collège de France
{x} , 1
23/04/2013 18
Marquer l’activité dans l’instruction
{z}, 1
pause; if x then pause else emit y end ; emit z
pause; if x then pause else emit y end ; emit zpause;
pause; if x then pause else emit y end ; emit zpause;
pause; if x then pause else emit y end ; emit zpause;
boot
pause;
, 1
G. Berry, Collège de France 23/04/2013 19
Instructions actives
:instruction inactive
:instruction active, contenant au moins un
:soit soit un
::
| ? ,
| ? , jamais ? ,
p
p̂ ˆp p p
p̂
p̂ qˆ ˆ ˆp q p q
p̂ qˆ ˆ ˆp
| ;
| ; ja
s
1̂
1̂
s
q p q
p̂ˆ
mais ;
| *
|{ }p
p̂
s
*
|
| p̂\ s
G. Berry, Collège de France 23/04/2013 20
Expansion des instructions actives
( ) non marqué
( ) redémarrage de ce point
( ? ,
p p p
ˆ ˆp q p ) ( ) test pas psé, seul actif
( ? , ) ( )
s
s
1̂
ˆ ˆp
0
q q
test passé, seul actif
( ) s ( ( )) test passé, actif
avec { 1 2? , }*(;
q ˆ ˆp p p
p' p'ˆ ˆp q p q
s s s
)
( ; ) ( );
s
p
Ñ
Ñ
ˆp q q p q ˆ ˆp p p
seul actif
( ; ) ( ) terminé, seul actif
( *) ( ); * actif, dépliage de boucle
( ; ) ( ); ( )
p
p q et actifs p q p ou pas
({ }ˆ )
q
p
p̂
ˆ ˆp
{ ( )}
({ } pˆ ˆp\s
) ( )
( ) ( )\p s
G. Berry, Collège de France 23/04/2013 21
Traduction en circuits synchrones
Chaque instruction génère un sous-circuit :
GO
RES
SUSP
KILL
SEL
K0
K1
K2...
E E'
p
– E and E’: signaux reçus et émis
– GO : démarrer p – RES : continuer p depuis son état courant– SUSP: geler p pour le cycle courant– KILL : tuer p en remettant ses registres à 0– SEL : p vivant, au moins un registre à 1
– Ki : code de retour, 1 fil par code• K0 : termine• K1 : pause • K2, K3,… : sortie de trap englobants
abort : RES 0 weak abort : RES 1, KILL 1
Propagation des 1 : MustPropagation des 0 : Cannot
G. Berry, Collège de France 23/04/2013 22
nothing (0), exit (k 2) et emit s (!s)
GO K0
s
emit s
GO Ki
pour i 1 (pause)
i 0 nothing
i k 2 exit Tk
G. Berry, Collège de France 23/04/2013 23
pause (1)
KILL
RES
K0SUSP
GO K1
SEL
G. Berry, Collège de France 23/04/2013 24
present s then p else q end (s?p,q)
s E’
SEL
K0
K1
K2
GO
RES
SUSP
KILL
E
p
q
G. Berry, Collège de France 23/04/2013 25
abort p when s
GO
RES
SUSP
KILL
SEL
K0
K1
K2
...
E E'
RES
SUSP
s
K0
GO
KILL
SEL
K1
K2
E E'
p
G. Berry, Collège de France 23/04/2013 26
suspend p when s
RES
SUSP
s
K0
GO
KILL
SEL
K1
K2
E E'
p
G. Berry, Collège de France 23/04/2013 27
GO
RES
SUSP
KILL
SEL
K0
K1
K2
...
E E'
P
GO
RES
SUSP
KILL
SEL
K0
K1
K2
...
E E'
Q
E'
SEL
K1
K2
GO
RES
SUSP
KILL
K0
E
Séquence p;q
RES
SUSP
K0
GO
KILL
SEL
K1
K2
EE'
p
q
G. Berry, Collège de France 23/04/2013 28
loop p end p*
pRES
SUSP
GO
KILL
E
K0
SEL
K1
K2
E'
Cycles combinatoires interdits !
G. Berry, Collège de France 23/04/2013 29
GO
RES
SUSP
KILL
SEL
K0
K1
K2
E E'
K3
...
P
GO
RES
SUSP
KILL
SEL
K0
K1
K2
E E'
K3
...
Q
LEM
L0
L1
L2
L3
IN_KILL
REM
R0
R1
R2
R3
KILL
K0
K1
K2
K3
S Y N C H R O N I Z E R
E'
K0
K1
K2
K3
SEL
GO
GO
GO
RES
SUSP
E
KILL
Parallèle || (ou |)
K0
SEL
K1K2
E'
RESSUSP
GO
KILL
E
K3
p
q
G. Berry, Collège de France
LEM
REM
L0
R0 R1
L1 L2
R2
L3
R3
K0 K1 K2 K3
IN_KILLKILL
23/04/2013 30
Le synchroniseur 2-adique
En voyant L (left), R (right) et K comme 2-adiques :
K Max(L,R) { max(l, r), lL, rR }K (L L) (R R) (L R)K (L | L) & (R | R) & (L | R) en C unsigned
G. Berry, Collège de France 23/04/2013 31
Max 2-adique malin
L 200011101 {3,4,5,7} R 201110010 {1,2,3,6}
K Max(L,R) { max(l, r) | lL, rR } {3,4,5,6,7}K { k LR | k max(min(L), min(R) }
LL 200011101
LL 200010010LL 200011111
LL { kN | k min(L) }
(LL) & (RR) { kN | k min(L) et k min(R) }
(LL) & (RR) { kN | k max(min(L), min(R)) }
K (LL) & (RR) & (LR) }
G. Berry, Collège de France 23/04/2013 32
Circuit pour trap T in p end {p}
RES
SUSP
GO
KILL
E
K0
SEL
K1
K2
E'
p
G. Berry, Collège de France 23/04/2013 33
signal s in p end (p\ s)
RES
SUSP
GO
KILL
E
K0
SEL
K1
K2
E'
peut provoquer des cycles combinatoires,sains pour les programmes constructifs!
p
G. Berry, Collège de France 23/04/2013 34
ABRO : circuit réseau de preuve
loop abort { await A || await B }; emit O ; halt when R;end loop
optimiséloop { await A || await B }; emit Oeach R
G. Berry, Collège de France 23/04/2013 35
Actions sur les donnéessignal X : integer in sustain ?X <= ?I+1|| loop pause; pause; emit ?Y <= ?X+pre(?X) end loopend signal
dépendances de donnéespour propagation constructive
et tri topologique
G. Berry, Collège de France 23/04/2013 36
La réincarnation
module Reincarnation :output X ;loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module
G. Berry, Collège de France 23/04/2013 37
La réincarnation
module Reincarnation :output X :loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module
G. Berry, Collège de France 23/04/2013 38
La réincarnation
module Reincarnation :output X :loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module
39G. Berry, Collège de France 23/04/2013
module Vishnu-3 :loop trap T1 in signal S1 in pause; emit S1; exit T1 || loop trap T2 in signal S2 in pause; emit S2; exit T2 || loop present S1 and S2 then emit X end; present S1 and not S2 then emit Y end; present not S1 and not S2 then emit Z end; pause end loop end signal end trap end loop end signal end trapend loopend module
G. Berry, Collège de France 23/04/2013 40
Kit pour neuf réincarnations
G. Berry, Collège de France 23/04/2013 41
Séparer les réincarnations par duplication
loop signal S in present S then emit X end ; pause ; pause; pause; emit S end signalend loop
loop signal S in present S then emit X end ; pause ; pause; pause; emit S end signal ; signal S in present S then emit X end ; pause ; pause; pause; emit S end signal ;end loop
Mais dupliquer récursivement des boucles imbriquées explosion exponentielle !
G. Berry, Collège de France
loop signal S in present S then emit X end ; gotopause P1; pause; pause; emit S end signal ; signal S in present S then emit X end ; P1 : pause ; pause; pause; emit S end signal ;end loop
23/04/2013 42
Dupliquer seulement la surface
loop signal S in present S then emit X end ; pause ; pause; pause; emit S end signalend loop
G. Berry, Collège de France 23/04/2013 43
Pire casloop trap ... loop loop trap trap ... loop trap trap
Pire cas quadratique + analyse statique (O. Tardieu) sans problème en pratique
3 incarnations, pas 4 !
G. Berry, Collège de France 23/04/2013 44
Structure du compilateur
foo.strl bar.strl
foo.ic bar.ic
all.lc
all.sc
all1.c all2.c all4.cinterprétationconstructive
équations de circuits triées
automateexplicite
all5.vmodel
checkerscircuit /FPGA
langage noyau
équations de circuit
Traçabilité complète pour debugging
G. Berry, Collège de France 23/04/2013 45
Code équation de circuits triées
E[64] = __WRISTWATCH_R[19]&&!(__WRISTWATCH_R[0]);E[65] = (E[62]&&E[63])||(__WRISTWATCH_R[19]&&E[64]&&!(E[63]));E[66] = E[61]&&E[65];E[67] = __WRISTWATCH_R[19]||__WRISTWATCH_R[20];E[68] = __WRISTWATCH_R[21]||__WRISTWATCH_R[22];E[69] = E[67]||E[68];E[62] = (E[64]&&E[63])||(__WRISTWATCH_R[20]&&E[62]&&!(E[63]));E[67] = (E[69]&&!(E[67]))||E[65]||E[62];E[64] = __WRISTWATCH_R[22]&&!(__WRISTWATCH_R[0]);E[58] = (E[64]&&E[60])||(__WRISTWATCH_R[21]&&E[58]&&!(E[60]));E[64] = (E[61]&&!(E[65]))||(__WRISTWATCH_R[22]&&E[64]&&!(E[60]));E[68] = (E[69]&&!(E[68]))||E[58]||E[64];E[66] = E[66]&&E[67]&&(E[68]||E[66]);if (__WRISTWATCH_R[0]) {__WRISTWATCH_A99;#ifdef TRACE_ACTIONfprintf(stderr, "__WRISTWATCH_A99\n");#endif}
G. Berry, Collège de France
• 1982, Thèse L. Cosserat : première sémantique, compilation v1 par calcul symbolique des résidus
23/04/2013 46
Résumé
• 1985, Thèse Ph. Couronné : Esterel v2 (LeLisp) premier vrai compilateur, lent / explosif
• 1989, Thèse G. Gonthier + équipe : Esterel v3 (C++), causalité par potentiels, réincarnation, rapide / explosif
• 1991, virage circuits : Esterel v4 (C++) premier vrai compilateur, rapide / quasi-linéaire, mais causalité restreinte (tri topologique); vérification formelle
• ~ 1995, causalité constructive générale, Esterel v5 (C++ / TiGeR) : Esterel v4 + interprète constructif + compilation BDD (chère)
• Traduction directe en C rapide :– Stephen Edwards : Synopsys Compiler (Synopsys),
Columbia Compiler (U. Colombia). – Reprise par Dumitru Potop dans Esterel v5+ et Marc Perreaut
dans Esterel v7
23/04/2013 47G. Berry, Collège de France
Travaux reliés
• Automates synchrones hiérarchiques:– Florence Maraninchi (IMAG) : Argos – Charles André (I3S Nice) : SyncCharts Esterel Sudio / Scade 6
• Langages réactifs– Frédéric Boussinot et. al. : Reactive C, Junior, SugarCubes, etc.– Marc Pouzet, Louis Mandel (Paris X1, ENS) : Reactive ML
• Autres langages synchrones– Lustre / SCADE (Verimag), Signal (Rennes)– Quartz / Averest : Klaus Schneider (U. Kaiserslautern)– Timed CCP : Vijay Saraswat (IBM), ECL (Lavagno / Sentovich), etc.
G. Berry, Collège de France 23/04/2013 48
Références
• Compiling Esterel Dumitru Potop-Butucaru, Stephen Edwards et Gérard Berry Springer, 2008
• The Constructive Semantics of Pure Esterel Gérard Berry, web book
• ...et plus sur www-sop.inria.fr/members/Gerard/Berry