La compilation logicielle dEsterel v5 Gérard Berry Chaire Algorithmes, machines et langages Collège de France Cours 4, 23 avril 2013

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


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)


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


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


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


Propagation constructive : Must et Cannot emit x

|| if not x then emit y

|| if not y then emit z

Must emit x



car les émetteursde y ont disparu

Cannot emit x



emit x



Must

x y z

x y z

x y z

x y z


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


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


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é


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é


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


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' }


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( )


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


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;



boot

pause;

, 1


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


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


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


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


pause (1)

KILL

RES

K0SUSP

GO K1

SEL


present s then p else q end (s?p,q)

s E’

SEL

K0

K1

K2

GO

RES

SUSP

KILL

E

p

q


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


suspend p when s

RES

SUSP

s

K0

GO

KILL

SEL

K1

K2

E E'

p


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


loop p end p*

pRES

SUSP

GO

KILL

E

K0

SEL

K1

K2

E'

Cycles combinatoires interdits !


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


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


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) }


Circuit pour trap T in p end {p}

RES

SUSP

GO

KILL

E

K0

SEL

K1

K2

E'

p


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


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


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


La réincarnation

module Reincarnation :output X ;loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module


La réincarnation

module Reincarnation :output X :loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module


La réincarnation

module Reincarnation :output X :loop signal S in present S then emit X end ; pause ; emit S end signalend loopend module


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


Kit pour neuf réincarnations


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 !


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


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 !


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


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}


• 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.


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

http://www-sop.inria.fr/members/Gerard.Berry/

Documents

La compilation logicielle dEsterel v5 Gérard Berry Chaire Algorithmes, machines et langages Collège de France Cours 4, 23 avril 2013