L a compilation logicielle d’Esterel v5

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