Ex ensiones sob e el compilado de ci com
Ex ending he ci com compile
T abajo de Fin de G ado
Cu so 2022–2023
Au o
Juan Ca los Díaz Rod íguez
Di ec o
Albe Rubio Gimeno
Codi ec o
Miguel Isabel Má quez
Doble G ado en Ma emá icas e Ingenie ía In o má ica
Facul ad de In o má ica
Uni e sidad Complu ense de Mad id
Ex ensiones sob e el compilado de ci com
Ex ending he ci com compile
T abajo de Fin de G ado en Ingenie ía In o má ica
Au o
Juan Ca los Díaz Rod íguez
Di ec o
Albe Rubio Gimeno
Codi ec o
Miguel Isabel Má quez
Con oca o ia: Junio 2023
Doble G ado en Ma emá icas e Ingenie ía In o má ica
Facul ad de In o má ica
Uni e sidad Complu ense de Mad id
29 de mayo de 2023
Resumen
Ex ensiones sob e el compilado de ci com
En es e p oyec o se ha desa ollado un análisis es á ico pa a el compilado de ci -
com, un Lenguage de Dominio Especí ico pa a el diseño de p o ocolos de Conoci-
mien o Nulo. Su obje i o es de ec a asignaciones de a iables que no juegan ningún
papel en el código gene ado. Bien po que la a iable se sale de scope an es de se
leída o po que hay una nue a asignación de la a iable an es de que el an iguo alo
se haya llegado a examina . Se p opone un algo i mo y se p esen a una demos-
ación de su co eción. Se han lle ado a cabo es s de endimien o an o sob e el
compilado como sob e el código que es e gene a. Los esul ados de dichas p uebas
apa ecen en la sección pos e io a la p esen ación del algo i mo. Al inal del docu-
men o, se expone una discusión de los esul ados y los bene icios que es e análisis
p esen a pa a el compilado .
Palab as cla e
Compilado , Ci com, análisis es á ico, asignación, aza, Rus , segu idad del có-
digo, op imización de código.

Abs ac
Ex ending he ci com compile
In his p ojec , a s a ic analysis is de eloped o he compile o ci com, a Domain
Speci ic Language o design Ze o-Knowledge p o ocols. I aims o de ec assignmen s
o a iables ha play no ole in he gene a ed code. Ei he because he a iable is
ne e ead be o e going ou o scope o because a new assignmen occu s be o e
he a iable has e e been ead. An algo i hm is de eloped o his analysis and
a co ec ion p oo is also gi en. Benchma king es s ha e been conduc ed on he
compile i sel and he code gene a ed by i . The esul s a e p esen ed in he sec ion
ollowing he algo i hm’s explana ion. A discussion o he esul s and he bene i s
his analysis b ings o he compile appea s a he end o he documen .
Keywo ds
Compile , Ci com, s a ic analysis, assignmen , ace, Rus , code sa e y, code op i-
miza ion.
ii
Con en s
1 In oduc ion 1
1.1 Mo i a ion................................. 1
1.2 Objec i es................................. 2
1.3 Wo kdesc ip ion ............................. 2
1.4 In he ollowing chap e s . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 S a e o A 5
2.1 Ze o-Knowledge p oo s . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 A i hme icci cui s ............................ 6
2.3 Ci com................................... 7
2.4 WhyRus ................................. 9
2.5 S a icanalysis............................... 9
3 Assignmen Analysis 11
3.1 Impo ance o he analysis . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Co ec nessp oo ............................. 13
3.2.1 P e ious de ini ions . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 Single Va iable app oach . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Mul iple Va iables app oach . . . . . . . . . . . . . . . . . . . 24
3.3 B inging he analysis o eal code . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Implemen a ion.......................... 27
3.3.2 Disca ded imp o emen s . . . . . . . . . . . . . . . . . . . . . 28
3.3.3 Wa ningsadded.......................... 28
4 Benchma king 31
4.1 P ojec s .................................. 31
4.1.1 Ci com ECDSA and ED25519 . . . . . . . . . . . . . . . . . 31
4.1.2 Rollups .............................. 32
4.1.3 MachineLea ning......................... 33
4.1.4 Da k o es ............................ 33
4.2 E alua ionp ocess ............................ 34
4.3 Pe o mance................................ 35
ix
2Chap e 1. In oduc ion
en i onmen o con ibu e o a eal-wo ld code base.
1.2 Objec i es
The p esen p ojec aims a de eloping addi ional ea u es inside he ci com com-
pile based on s a ic analysis echniques. We can b eak down ha end in o he
ollowing speci ic objec i es:
I) S udy an ongoing code eposi o y. Du ing he whole deg ee, he usual way
o de eloping code has been building i om he g ound up, using lib a ies i
needed. We all know ha is no he case in mos p ojec s. Tha is why i
is impo an o ge used o eading and building on op o o he de elope s’
wo k.
II) Read up on classic s a ic analysis echniques and adap hem o he cu en
code base o he compile .
III) C ea e a seman ic p ese ing algo i hm. I is pa amoun ha he modi ica-
ions o he code sugges ed by he analysis ne e change he seman ics o ou
p og ams.
IV) Imp o e code sa e y o ci com ci cui s and help de elope s o ind po en ial
bugs.
V) Boos he pe o mance o he gene a ed code by he compile . Any mino
pe o mance imp o emen in he compile s ou pu will be help ul as hese
p og ams a e mean o un housands o imes when linked o a blockchain o
c yp og aphic sys em.
1.3 Wo k desc ip ion
The i s hing o do in his p ojec was o ge amilia wi h he code base. A e a
ca e ul s udy o he pa s o he compile ha we e o be deal wi h, a i s a emp
a implemen a ion ollowed. To ack de elopmen a he same ime he compile
e sion was kep up o da e, a o k was c ea ed om he o icial ci com eposi o y.
Pull eques s we e done pe iodically o assu e code compa ibili y. Because he anal-
ysis p o ed o ha e some ca ea s, i was decided o i s comple e he o mal p oo
o he algo i hm. This o mal app oach helped in inding p ope da a s uc u es
and algo i hm p ope ies ha ca ied nicely in o he exis ing code and ixed he
exis ing issues. Once he main de elopmen phase was comple e, we commi ed o a
se ies o es s in ol ing he ci com lib a y and addi ional eposi o ies. Code bugs
we e ixed hanks o his es ing and we made su e ha no seman ics we e al e ed.
Ha ing he code so ed, he e was a las phase o benchma king o check compile
pe o mance as well as ou pu code imp o emen s.
The p ojec ’s code can be ound in he o ked eposi o y (h ps://gi hub.com/
RinconDeJC/s a ic-ci com).

1.4. In he ollowing chap e s 3
1.4 In he ollowing chap e s
Once inished wi h he in oduc ion, an o e iew o he main concep s a ound ci -
com will be gi en. We will see wha Ze o-Knowledge p oo s and a i hme ic ci cui s
a e, he compile ’s s uc u e and he classical li e a u e on s a ic analysis s udied.
Nex up, he algo i hm c ea ed will be explained, along wi h i s co ec ness,
comple eness and e mina ion p oo . An o e iew o how his was ansla ed o he
code base will be gi en as well.
In he ou h chap e , he es ing chain will be discussed along wi h he esul s
ob ained. Finally, a discussion o he whole p ojec will be held o ound up his
yea ’s wo k.
Chap e 2
S a e o A
This chap e aims o gi e he eade an idea o he backg ound behind ci com and
i s applica ions. We i s in oduce he concep o Ze o-Knowledge p oo s and a i h-
me ic ci cui s, ollowed by a desc ip ion o he ci com language and i s compile .
A he end, he e is a e iew o he li e a u e on s a ic analysis.
2.1 Ze o-Knowledge p oo s
In he wo ld o c yp og aphy, a e y common p oblem is p o ing you possess some
in o ma ion. One immedia e way o p o e i is by disclosing he knowledge you
claim o ha e. Howe e , ha usually goes agains he whole poin o c yp og aphy.
Ze o-Knowledge p oo s o Ze o-Knowledge p o ocols (ZK) a e a way o assu ing you
ha e some in o ma ion wi hou ha ing o e eal i . A classical example can be ound
in [1].
He e Alice and Bob ha e ound a ca e. The ca e has a single en y o a ci cula
pa h. On he opposi e side o he en y, he e is a doo ha equi es a passwo d.
Bob claims a mys e ious man has e ealed he sec e code o him, bu has p ohibi ed
e ealing i o anyone else. Alice da es him o p o e his claim, and hey design an
expe imen o do so. Bob will go in o he ca e i s and, wi hou Alice knowing,
he will go in a andom di ec ion owa ds he doo . Alice will s and a he en y
and shou a di ec ion she wan s Bob o come ou om. I Bob does no know he
passwo d and canno c oss he doo , he e is a 50% chance ha bo h o hem ha e
chosen he same di ec ion. By epea ing his expe imen n imes, he chance ha
Bob does no know he code bu always comes om he di ec ion Alice ells him
is 2−n. So a e se e al ies, Alice is con inced Bob knows he code, al hough she
does no know he passwo d he sel .
Obse e how hese p oo s a e no a logical p oo as hey a e unde s ood in
ma hema ics. They a e a p obabili y p oo , whe e he e is always a small chance
ha a malicious p o e can con ince he e i ie . This p obabili y can be made as
small as we wan o inc ease he eliabili y o he p o ocol.
In he p e ious example, in e ac ion be ween he p o e Bob and he e i ie
Alice was also equi ed. This aspec is a oided by Ze o-Knowledge Succinc Non-
5
6Chap e 2. S a e o A
In e ac i e A gumen o Knowledge (ZK-SNARKs) and hey a e he ones ci com
ocuses on. In gene al, ZK-SNARKs a e used o p o e he co ec ness o a compu-
a ion. These compu a ions can be ep esen ed by an ai hme ic ci cui .
2.2 A i hme ic ci cui s
One o he mos ecu en languages used o ZK-SNARKs is he language o ci cui
sa is iabili y. This language is NP-comple e and hence equen ly appea s in he
ield o c yp og aphy [2, 3, 4]. An a i hme ic ci cui is composed o a se o ga es
connec ed jus like in elec onic ci cui s ha pe o m a i hme ic ope a ions on hei
inpu s o p oduce hei ou pu . A ci cui is hen said o be sa is iable i i has an
assignmen o i s inpu s ha makes he ou pu ue.
In ou con ex , hese ci cui s will be de ined by ci com p og ams, he inpu s
and ou pu s o he ga es will be e e ed o as signals and he a i hme ic ope a ions
pe o med will only be addi ion and mul iplica ion. Signals will ake alues on a
p ime ini e ield Fp, whe e pis a e y la ge p ime [5]. Ci com de ines ci cui s by
se ing a se o cons ain s on he signals. These cons ain s a e a se o equa ions
o he o m A∗B−C= 0, whe e A, B, C a e linea combina ions o signals o e
a p ime ield Fp, called ank-1 cons ain sys em (R1CS). A ZK-SNARK p o ocol
will hen p o e ha he p o e knows an assignmen o he se o signals ha
mee he R1CS cons ain s, bu wi hou disclosing he alues o he signals ha
a e conside ed sec e . To dis inguish wha is a sec e signal and wha is no , mos
a i hme ic ci cui languages ha e he concep o p i a e and public signals. In
gene al, a public signal will be known by he e i ie , while he p o e will ha e o
know a co ec assignmen o public and p i a e signals. In ci com, signals can
be conside ed inpu ,in e media e o ou pu . In e media e signals will always be
p i a e and ou pu signals public. Inpu signals can ei he be p i a e o public, so
he p o e can hide he in o ma ion ha he does no wan o disclose, bu p o e he
does ha e i . A signal assignmen in a ci cui (public and p i a e) is known as a
wi ness.
s4
s5
s3
s2
s1
s6
s7
s8s9
Figu e 2.1: G aphic ep esen a ion o an a i hme ic ci cui Co e F11 ha ou pu
he exp ession s1×s2×s3+s4×s5mod 11
2.3. Ci com 7
Example 2.2.1. Le Cbe he ci cui om Fig 2.1 o e F11 ha gi en he inpu s
s1, s2, s3, s4and s5ou pu s
s1×s2×s3+s4×s5.
Ou ga es only ha e 2 inpu s each, so we will need in e media e signals s6, s7, s8and
an ou pu signal s9. A alid wi ness w o he se o signals S={si}9
i=1 could be
w1={7,3,4,9,9,10,7,4,0}o w2={5,2,8,7,9,10,3,8,0}.
To ge he R1CS cons ain s, we canno exp ess i as
s1×s2×s3+s4×s5−s9= 0 mod 11,
bu a he we need o spli i in o mo e cons ain s like









s1×s2−s6= 0 mod 11
s6×s3−s7= 0 mod 11
s4×s5−s8= 0 mod 11
s7+s8−s9= 0 mod 11
which can be u he simpli ied in o





s1×s2−s6= 0 mod 11
s6×s3−s7= 0 mod 11
s4×s5+s7−s9= 0 mod 11.
2.3 Ci com
Ci com [6, 7] is a cons ain -based Domain Speci ic Language o design a i hme ic
ci cui s. A much be e o e iew o ci com, i s en i onmen and usages can be
ound in [8], whe e a lo o he in o ma ion in his e iew has been ex ac ed om.
P og amming wi h his language is ai ly low-le el and he design o a i hme ic
ci cui s lands e y close o he design o elec onic ci cui s. Howe e , ci com aims
o make he design o e y la ge ci cui s a simple p ocess wi h a s ong ocus on
modula i y. The language allows he use o c ea e gene ic ci cui s called empla es
ha one can ins an ia e wi h di e en pa ame e s and euse hem o c ea e mo e
complex sys ems. We will e e o a empla e ins an ia ion as a componen .
The ci com ecosys em needs wo main elemen s o be able o wo k wi h Ze o-
Knowledge p oo s. These a e he wi ness and he ci cui in R1CS o ma . The
wi ness is gene a ed wi h he assigned alues o e e y single signal in he a i hme ic
ci cui . The key pa o hese ci cui s is ha i is almos impossible o compu e
he alue o e e y signal, p i a e and public, simply om he alues o he public
inpu s and he ou pu s, which a e always public. This is ue gi en he p og amme
has used ci com o design a obus ci cui , o cou se, i ial ci cui s can be sol ed
jus om he public inpu . To be able o gene a e ou wi ness, ci com ou pu s

8Chap e 2. S a e o A
a p og am, ei he in C++ o WebAssembly ha e icien ly compu es hese alues
gi en e e y inpu o he ci cui . A he same ime, he se o R1CS cons ain s is
gene a ed om he speci ica ions in he ci com p og am. The compile will ou pu
hese in he o ma ha he use asks o . These cons ain s a e ex ac ed by he
compile om he p og am by pe o ming a symbolic execu ion o he code. I is
symbolic because he compile does no know he alue o he signals a compile
ime, so he ope a ions pe o med on signals a e e y much like he ones we would
do wi h a iables in a ma hema ical equa ion. The cons ain s he p og amme
speci ies wi h hei code mus ollow he R1CS s uc u e desc ibed, o he compile
will issue an e o code.
Al hough ci com is a Domain Speci ic Language, he e is a wide a ie y o
p ojec s whe e his is used han one migh hink a i s . Al hough mos o hem
a e ela ed o c yp og aphy in some way, he e a e e y in e es ing ways o apply
hese echniques. Some o hese p ojec s will be e iewed in Chap e 4.
The compile has ou main phases. The i s pa has o do wi h he pa se .
The e is no hing oo special abou i , o he han saying i is an LR(1) g amma
pa sed by he lal pop ool. The e is a side e ec he pa se has, and ha is in-
oducing ini ializa ion assignmen s. This will be discussed in Chap e 3 in mo e
de ail.
Then, a se ies o s a ic analyses a e pe o med on he code. This is he pa
whe e his p ojec is ocused on. The ci com compile includes he usual binding
and yping analysis, as well as looking o a e u n s a emen in e e y unc ion’s
pa h. O he unc ionali ies he compile includes a e a bi mo e speci ic o ci com.
A lis o hem, al hough no exhaus i e, is:
•Signal decla a ion. Signals can only be decla ed in empla es a he op scope.
This means ha we ha e o check empla es o no decla e signals inside an
inne block and unc ions o no decla e signals a all.
•Re u n s a emen s in empla es. These a e no allowed in a empla e, so
much like we did in unc ions, we now ha e o check ha no a single pa h in
a empla e ca ies one o hese s a emen s.
•Unknown Known analysis. In ci com, e e y componen pa ame e mus be
known a compile ime. In his analysis, each exp ession in he p og am is
classi ied as Known o Unknown a compile ime. I a componen pa ame e
is Unknown o he size o an a ay (which is always s a ic), an e o is issued.
•Cons an p opaga ion. As we ha e said, cons an alues a e e y impo an in
ci com. Fo his and pe o mance easons, a iables de ec ed o be cons an
a e compu ed and p opaga ed h ough he AST .
A e he s a ic analysis phase, he e is a a he special symbolic execu ion o
he code. He e, he compile will compu e he alues o he pa ame e s o he
empla es, which ha e been checked o be known a compile ime. No e ha any
exp ession in ol ing a signal is immedia ely conside ed an unknown alue. While
his in e p e a ion o he code is being done, Di ec ed Acyclic G aph (DAG) is
c ea ed. I will con ain in o ma ion on e e y componen and i s associa ed empla e.
2.4. Why Rus 9
This is impo an because each componen will gene a e i s own cons ain s and he
DAG helps he compile o educe he memo y space aken up by e e y componen
in he p og am. No e ha o some ci cui s, he numbe o componen s can be huge,
bu many o hem will ha e he same empla e and pa ame e s. Once he DAG is
c ea ed and he cons ain s ex ac ed, hey a e simpli ied o educe he size o he
ou pu , bu wi hou e e changing he seman ics.
In he inal pa , an in e media e ep esen a ion is c ea ed om which he code
ha gene a es he wi ness is w i en o he a ge language.
2.4 Why Rus
The ci com compile was o iginally w i en in Ja aSc ip in e sions 0.0 and 0.5
[9]. The o icial compile , Ci com 2.0, was ew i en in Rus [10], a gene al-pu pose
p og amming language ocused on pe o mance and sa e y. I also has s ong con-
cu en applica ions, bu his aspec is no exploi ed in his p ojec . Sa e y in Rus
mainly has o do wi h memo y sa e y. This means making su e ha all e e ences
poin o alid memo y. I is achie ed no by a ga bage collec o o e e ence coun -
ing, which ha ms pe o mance, bu a concep called bo ow checke . The bo ow
checke , owne ship and li e imes a e e y impo an concep s ha shape he way
one can p og am wi h Rus , bu we will no go in o de ail. A e y good guide o
Rus can be ound in he Rus handbook [11] o in Rus by examples [12]. All o
hese ancy Rus concep s do come wi h hei d awbacks, mainly when i comes o
mu able e e ences. Some ex a e o has been done o wo k a ound hese issues
du ing he p og amming made in his p ojec , bu once o e come, code sa e y is
nea ly assu ed when i comes o memo y issues.
2.5 S a ic analysis
S a ic analysis plays a c i ical ole in compile s, helping o de ec and p e en p o-
g amming e o s be o e he p og am is execu ed. In simple e ms, s a ic analysis
e e s o he p ocess o analyzing code wi hou execu ing i . This analysis can help
de ec a wide ange o issues, om basic syn ax e o s o mo e complex issues like
da a low p oblems and secu i y ulne abili ies.
In oduc o y cou ses on compile s s a by aking a look a he classical lexi-
cal, binding and yping analysis, which a e all s a ic. Howe e , many mo e hings
can be de i ed om hese echniques ha ange om de ec ing mis akes om he
p og amme such as unini ialized a iables, o a a ie y o code op imiza ions. Al-
hough hese ea u es do come oge he in mode n compile s, back in he 1980s he e
was a dis inc ion be ween debugging compile s and op imizing compile s, depending
on whe he o no hey included some so o op imiza ion on he code gene a ed
[13]. Two o he i s compile s ha included a powe ul op imiza ion chain a e
Alpha [14] and Fo an H [15].
One o he mos common applica ions o s a ic analysis is in he a ea o code
quali y. Fo example, s a ic analysis ools can be used o de ec code smells, which
10 Chap e 2. S a e o A
a e indica o s o po en ial p oblems in he code. Some common code smells include
long me hods, duplica e code, and excessi e b anching. By iden i ying hese issues,
de elope s can make hei code mo e main ainable and easie o unde s and. In his
p ojec , we will ocus on unused assignmen s when i comes o e o -p one de ails
in he code.
In summa y, s a ic analysis is a c i ical ool o ensu ing he quali y and secu i y
o so wa e code. By analyzing code wi hou execu ing i , s a ic analysis ools can
iden i y po en ial issues be o e hey become signi ican p oblems. These ools can
be in eg a ed in o he compile , p o iding au oma ic analysis du ing he compila-
ion p ocess. Howe e , he mo e powe ul and cos ly analyses a e usually ound in
ex e nal applica ions, so hese hea ie compu ing checkings a e no un e e y ime
he code is compiled. Some o hese ools can be ound in [16].
S a ic analysis plays a cen al ole in code op imiza ion as well. In gene al,
inding he op imal ins uc ion selec ion and o de o he op imal ew i e o he AST
is an NP-comple e p oblem [17, 18]. S a ic analysis can ackle some op imiza ion
echniques ha , al hough hey migh no gene a e he absolu e op imal code, can
imp o e i s e iciency a polynomial cos . The cen al aspec o op imiza ion in s a ic
analysis is making seman ic-p ese ing ans o ma ions. In [19, 20] an o e iew o
some s a ic analysis echniques conce ning op imiza ion is gi en. Howe e , a mo e
in-dep h s udy can be ound in [21, 22].
An app oach ha will come o ou in e es is ha o Con ol Flow G aph and
Da a Flow G aph. The i s akes ad an age o a ans o ma ion o he AST ocused
on he di e en b anches he code can ollow o examine he code [19]. The la e
is used a a la e s age in op imizing compile s a e he CFG has been c ea ed.
Now he ocus is on he ela ions ha he da a p esen when a e sing he gi en
pa hs. This echnique da es back o he ea ly 1960s, om Vysso sky a Bell Labs
[23]. Howe e , his analysis usually equi es ha alues a e compu ed i possible,
and a he momen we will apply ou analysis, his in o ma ion is s ill no compu ed.
Howe e , i can be in e es ing o he eade as simila ideas will be applied.
Ou side o he classical li e a u e on compile s, he e is a lo o wo k being done
ela ed o unused a iable de ec ion and unini ialized a iable usage. In [24], a de-
elope o RedHa desc ibes how he is imp o ing -Wuni ialized o gcc, a speci ic
wa ning [25] om he amous C compile . Mo e mode n compile s a e including
hese echniques as well. Solang, a compile o he Solidi y en i onmen is imple-
men ing unused a iable elimina ion and unde ined a iable de ec ion [26]. E en
da a low g aph is helping o imp o e Psalm 4 compile in [27].
Chap e 3
Assignmen Analysis
In his chap e , we will co e he s a ic analysis de eloped o his p ojec . We s a
by discussing why his analysis is impo an o he ci com compile . A e wa ds, a
co ec ness, comple eness and e mina ion p oo is gi en making some abs ac ions
o simpli y he logic equi ed. Finally, some aspec s o he implemen a ion a e
e iewed.
3.1 Impo ance o he analysis
To gene a e a p ope wi ness ha can c ea e a co ec alidi y p oo , ci com p o-
g ams mus be de e minis ic. This de e minism ex ends o he alue o e e y single
a iable and signal. P og ams w i en in o he languages migh be able o a o d o
ha e ga bage in hei memo y, bu in his con ex , his unde ined beha io is e y
ha m ul. In an ideal wo ld, no one ha made a ci com p og am would use any-
hing wi h ga bage in i , bu because bad p og amming p ac ices a e e e ywhe e,
he ci com compile had o inco po a e a manda o y ini ializa ion in e e y a iable
in case he p og amme has no speci ied an ini ial alue o a a . This is done a
he pa se le el, so a e his phase, a a iable assignmen in oduced a i icially is
essen ially he same as an assignmen manually coded. Howe e , a simple ag has
been added o he compile o ha e use ul in o ma ion in he analysis o come. In
Lis ing 3.1 we can see he e ec he pa se has o e he code gi en. Wha Pa se Ge s
ep esen s wha he p og amme would ha e yped. The pa se will hen p ocess i ,
elimina ing syn ac ic suga and simpli ying some s uc u es. One o hose simpli i-
ca ions is he one we ha e men ioned abou b eaking decla a ions in o a single ype,
ha is, a decla a ion wi hou ini ializa ion ollowed by a manda o y independen
assignmen . Bo h possibili ies o his e ec can be seen in a iables unini ializaed
and ini ialized in he Wha Pa se Gi es empla e.
This manda o y ini ial alue came wi h an addi ional execu ion ime cos o
he code gene a ed. We need o keep in mind ha , while a language like C++
can e y easily emo e unnecessa y ini ializa ions, ha is no he case in he code
gene a ed by ci com in o C++. The signals and a iables’ alues a e implemen ed
as poin e s o FieldValue objec s, so he C++ compile will no be able o de ec
ini ializa ions a i icially added by he ci com pa se . The e is no need o say ha
11
18 Chap e 3. Assignmen Analysis
39: unc ion Me geB anches((x, id), S a e1, S a e2)
40: i S a e1=Use ul o S a e2=Use ul hen
41: e u n Use ul
42: end i
43: i S a e1=Unknown o S a e2=Unknown hen
44: e u n Unknown
45: end i
46: i S a e1=Useless o S a e2=Useless hen
47: e u n Useless
48: else
49: e u n No Appea ed
50: end i
51: end unc ion
52: unc ion I Else((x, id),I ElseG aph, S a e)
53: S a e =analyse ((x, id),I ElseG aph.condi ion, S a e)
54: S a ei =analyse ((x, id),I ElseG aph.i , S a e)
55: S a eelse =analyse ((x, id),I ElseG aph.else, S a e)
56: e u n Me geB anches ((x, id), S a ei , S a eelse)
57: end unc ion
58: unc ion Loop((x, id),LoopG aph, S a e)
59: S a e0=analyse ((x, id),LoopG aph.condi ion, S a e)
60:
61: S a e1.1=analyse ((x, id),LoopG aph.body, S a e0)
62: S a e1.2=analyse ((x, id),LoopG aph.condi ion, S a e1.1)
63:
64: S a e2.1=analyse ((x, id),LoopG aph.body, S a e1.2)
65: S a e2.2=analyse ((x, id),LoopG aph.condi ion, S a e2.1)
66:
67: S a e0and1=Me geB anches ((x, id), S a e0, S a e1.2)
68: S a e0and1and2=Me geB anches ((x, id), S a e0and1, S a e2.2)
69: e u n S a e0and1and2
70: end unc ion
P oposi ion 3.2.4. analyse ((x, id),ASTG aph,No Appea ed) = Useless i and
only i he assignmen wi h his id is useless in e e y ace in he Call G aph. Mo e-
o e , he call always e mina es, i.e. he algo i hm is co ec and comple e.
P oo . We i s ocus on he e mina ion o he algo i hm and la e on he co ec ness
and comple eness.
Te mina ion
The algo i hm is ollowing he AST wi h wo un olds on he loops, so i is a ini e
g aph. Fo his eason, he algo i hm always e mina es.
Co ec ness and comple eness
I is impo an o ema k on he ollowing when alking abou scope. The e is a node

3.2. Co ec ness p oo 19
a he end o e e y block. A a iable whose scope ends wi h ha block is conside ed
o be inside o scope in said node and ou o scope in he nex one. This de ail is
mino , bu necessa y o be able o make he nex p edica e mu ually exclusi e and
always hold du ing he p oo .
Le Abe he se o assignmen s in he AST and N he se o nodes in he Call
G aph. Then, we de ine S:A×N → {No Appea ed,Useless,Use ul,Unknown}such
ha
S((x, id), node) = No Appea ed i ∀ = 1, node, 2; (x, id)/∈ 1
S((x, id), node) = Useless i
∃ = 1, node, 2: (x, id)∈ 1
∧
∀ = 1,(x.id), 2, node, 3,















∀node0∈ 2, node0does no ead x
∧xis ou o scope in [node, 3]
∨
∃(x, id0)∈((x, id), node) :
∀node0∈((x, id),(x, id0)] , node0does no ead x
S((x, id), node) = Use ul i
∃ = 1,(x.id), 2, node, 3:∃node0∈ 2:









xis ead in node0
∧
@(x, id0)∈((x, id), node0) :
xis no ead in (x, id0).
S((x, id), node) = Unknown any o he case
By de ining Unknown his way we make su e all cases a e co e ed. One could de elop
he logic algeb a o he las condi ion, bu i ends up being oo long o w i e he e.
I is enough o he eade o know ha he e a e cases whe e Scan ake he alue
Unknown. In ui i ely, i means ha he assignmen has appea ed in a ace, bu
we canno say o now whe he i is useless in e e y ace ha eaches his node o
i i is use ul in a single ace. In pa icula , in he aces whe e ha assignmen
has appea ed i has no been ead ye . I can be seen, wi h a li le wo k, ha all o
hese cases a e mu ually exclusi e. This is e y impo an as i allows S o be a well-
de ined unc ion. Because i is a unc ion, we will ob ain he p oo o comple eness
o ee when p o ing co ec ness.
We p o e by induc ion on he s uc u e o he AST ha , o e e y g aph asso-
cia ed wi h a node om he AST, called G aph, we ha e
analyse ((x, id), G aph, S((x, id), P (G aph))) = S((x, id), L (G aph))
Reading be ween lines, wha P(G aph)and L(G aph)a e doing is ex ending
he esul o S o he nex node in he AST . No e how i wo ins uc ions a e
consecu i e in a block L(G aph1) = P(G aph2), o how P(G aphi ) = nodecondi ion
and LG aphi /else=nodeme ge in and I /Else s uc u e.
20 Chap e 3. Assignmen Analysis
We now dis inguish cases on he ype o g aph and he a gumen S a e:
•Reade node.
–S a e =No Appea ed. I he assignmen has no appea ed ye , hen i
will no ha e appea ed a e his node as i is no an assignmen , so he
esul No Appea ed is co ec .
–S a e =Use ul. Because he e was al eady a node0whe e xwas ead
a e he assignmen , whe he xis ead he e o no does no change he
logic alue, so he esul Use ul is co ec .
–S a e =Useless. The e exis s a ace whe e (x, id)appea ed, so i will
s ill be he e, and in hose whe e i appea ed he e is al eady an assign-
men ha o e w i es o i canno be ead anymo e. In he i s case
whe he xis ead he e o no will no change he u h alue, and in he
second one, we know i canno be ead he e by he p econdi ion because
i is ou o scope, so i would s ill be ue.
–S a e =Unknown. I xis ead he e, hen we know ha , because he e ex-
is s a ace whe e (x, id)appea s, ha same ace will hold ha ∃node0∈
2, node:xis ead in node0and @(x, id0)∈((x, id), node0) : xis no ead
in (x, id0). This las pa we know om S a e 6=Useless and his node
no being an assignmen . Then he Use ul e u n alue is co ec . I x
is no ead, hen he S a e =Unknown p ope y can be ex ended o his
node.
•Assignmen node.
–S a e =No Appea ed. I he assignmen has no appea ed ye and nei he
is his assignmen he one wi h ha id, hen i will no ha e appea ed
a e his node, so he esul No Appea ed is co ec . Now suppose we
ha e jus ound he co ec assignmen . Then ce ainly he esul canno
be No Appea ed anymo e. I canno be Use ul, as 2is emp y and i
canno be Useless because i s ly, xcanno be ou o scope on he nex
node as i has jus been used and, a mos , he nex node could be he
end o he block which we cla i ied coun ed as pa o he scope o x(This
is he pa o he p oo whe e ha cla i ica ion was impo an ). Secondly,
he in e al ((x, id), node]is emp y. Then, he only alid esul mus be
Unknown.
–S a e =Use ul o S a e =Useless. Same as in he p e ious case, no
ma e wha happens in his node, he S a e =Use ul o S a e =Useless
p ope y will ex end nicely.
–S a e =Unknown. I xis ead he e, his is he same case as in a Reade
node, and he only alid esul is Use ul again. I i is no ead he e, bu
o e w i en, hen ake = 1,(x, id), 2,(x, id0), 3any ace whe e he as-
signmen appea ed and whe e (x, id0)is e e ing o his node. We know
xhas no been ead since, hen ∃(x, id0)∈((x, id),(x, id0)] : ∀node0∈
3.2. Co ec ness p oo 21
((x, id),(x, id0)] , node0does no ead x. Then Useless is he co ec e-
sul . I xis no ead, no o e w i en, hen he S a e =Unknown p op-
e y can be ex ended o his node.
•Block. We s udied how he Induc ion Hypo hesis simply ex ends co ec
alues o Sone node u he . Wi h i , he looping we a e doing o e consecu i e
s a emen s makes hem ha e he p ope a gumen and e u n alues. Then,
a e he loop we ha e S a e =S((x, id), L (G aphn)).
–S a e 6=Unknown. A he end o he block no a iable can be ead, o e -
w i en o any assignmen can appea , so all o he alues bu Unknown
ex end pe ec ly o his node and would hold he de ini ion o S.
–S a e =Unknown. Take any ace = 1,(x, id), 2, end_block, 3. We
know xhas no been ead since (x, id). Suppose xis going ou o scope in
his node. This means ha xis in scope in end_block bu no in (node, 3].
Then ∀node0∈((x, id), end_block], node0does no ead x∧xis ou o
scope in (end_block, 3]. This means ha he Useless alue is holding
he e. I xis no going ou o scope, hen no hing changes abou he es
o he condi ions, so he Unknown alue ex ends o his node.
Be o e con inuing wi h he o he wo nodes, le us see how S a e wo ks when me ging
b anches. Suppose he e is a node whe e he aces can ei he be = 1, 2, node, 4
o = 1, 3, node, 4, meaning 2and 3a e he supposed di e en b anches an
execu ion ace could ha e aken. We wan o see wha is he p ope S a e a e
node, so he alue o S e u ned is he one de ined abo e.
Suppose he S a e a he end o 2is Use ul. Then, he ace ha exis s in
1, 2, node, 3will s ill exis in he se o aces made by he union, so he esul a
node will s ill be Use ul.
Suppose now ha he S a e a he end o 2is Useless and he esul a he end
o 3is ei he Useless o No Appea ed. We know he e is a b anch whe e (x, id)has
appea ed, so we do no need o wo y abou he i s p oposi ion o he and. Focus
on he second one. Take any ace ha goes h ough node. I ha ace does no
con ain (x, id)we ha e no hing o wo y abou . I = 1,(x, id), 0, node, nodeme ge, 3
hen i comes om a b anch whe e he S a e was Useless. Then o ha ace he
p oposi ion
∀node0∈((x, id), node], node0does no ead x
∧xis ou o scope in (node, 3]
∨
∃(x, id0)∈((x, id), node] :
∀node0∈((x, id),(x, id0)] , node0does no ead x
22 Chap e 3. Assignmen Analysis
holds. Then, as no assignmen o eading happens a a me ge node he p oposi ion
∀node0∈((x, id), nodeme ge], node0does no ead x
∧xis ou o scope in (node, 3]
∨
∃(x, id0)∈((x, id), nodeme ge] :
∀node0∈((x, id),(x, id0)] , node0does no ead x
holds. By uni e sal gene aliza ion, he S a e mus be Useless a e nodeme ge.
I is immedia e o see ha he only case whe e he S a e can be No Appea ed is
when bo h s a es a e 2and 3a e No Appea ed.
Rema k ha he p e iously desc ibed cases a e he only ones whe e hose esul s
could hold p ope ly. This lea es us wi h he only op ion o he emaining cases o
be Unknown.
This beha io is desc ibed in his a he pleasing able o he esul o
Me geB anches.
Me geB anches Use ul Unknown Useless No Appea ed
Use ul Use ul Use ul Use ul Use ul
Unknown Use ul Unknown Unknown Unknown
Useless Use ul Unknown Useless Useless
No Appea ed Use ul Unknown Useless No Appea ed
Table 3.1: Resul o me ging b anches
The only hing le o do is check ha he code does exac ly his wi h he esul s,
which is immedia e oo.
Now ha we know ha calling Me geB anches allows us o keep he pos condi-
ions e e ing o wo b anches, and by induc ion can be ex ended o any numbe o
b anch me ging, we con inue wi h he p oo .
•I /Else node. We can see how he calling p ope ly p opaga es he alue o
Sas in he Block case and how P(G aphi ) = P(G aphelse) = nodecondi ion.
Then by he beha io o Me geB anches ha we jus saw, we p o e ha he
alue e u ned ollows Sde ini ion.
•While node. Same as in I /Else case, only ha we a e now me ging he
b anches wi h ze o, one and wo loops as we ep esen ed in he Call G aph.
We ha e hen p o ed ha , gi en he p ope alue o S a e, he esul ollows S
de ini ion. Now we check ha he S a e alue o No Appea ed is he co ec one in
he i s call and check wha is he alue o S((x, id), L (AST))
Because we a e he beginning o he AST ,S a e =No Appea ed makes pe ec
sense. Because hese s a es a e mu ually exclusi e we do no need o check any hing
else, Sde ini ion hold. Now ake he esul is Useless a he las node, which we
will call nodeEND. This node, by he cons uc ion o he AST ends e e y possible
3.2. Co ec ness p oo 23
a iable’s scope. So, by subs i u ing, and ha ing in mind ha any se o nodes a e
nodeEND is an emp y se , we ge
∃ = 1, nodeEND : (x, id)∈ 1, nodeEND
∧
∀ = 1,(x.id), 2, nodeEND,















∀node0∈((x, id), nodeEND], node0does no ead x
∧xis ou o scope in (nodeEND, nodeEND]
∨
∃(x, id0)∈((x, id), nodeEND] :
∀node0∈((x, id),(x, id0)] , node0does no ead x.
I we de ine ha a scope is ou o scope in he emp y se , hen we can jus igno e
ha pa and see how his says ha he e is a ace whe e (x, id)appea s, and in
hose ha i happens I o II hold. So (x, id)is useless in e e y single ace. Because
a piecewise de ini ion o a unc ion is, essen ially, a double implica ion, i (x, id)
appea s in a ace and i is useless in e e y single one o hem, hen he esul will
be Useless, and hence we ha e p o ed comple eness as well.
We ha e p o ed he co ec ness o he algo i hm, bu ou call g aph only co e s
execu ion aces wi h a maximum wo un oldings o a loop. Ou analysis aims o
co e e e y possible execu ion ace, so we need o show ha his le el o un olding
co e s all possible execu ion aces.
P oposi ion 3.2.5. An assignmen is useless in e e y ace o he Call G aph i
i is useless in e e y execu ion ace.
P oo . The only di e ence in s uc u e be ween ou call g aph and he execu ion
aces g aph is he dep h o un olding o he loops. I we p o e by induc ion o e
he numbe o i e a ions ha an assignmen is useless in a ace wi h ni e a ions
i i is useless in a ace wi h n+ 1 i e a ions o n≥2, hen we ha e p o en
by induc ion on he s uc u e o he g aphs ha he call g aph con empla es e e y
execu ion aces as i eaches a ixed poin on he analysis esul wi h 2 i e a ions
o a loop.
Deno e by nex a ace ha s a s jus a e he loop, by body a pa h on he call
g aph ha ep esen s he body o he loop, by condi ion he node whe e he con-
di ion o he loop is e alua ed and by ag a agmen o body ha eaches he end
( his ep esen s an assignmen ha happens inside he loop).
We wan o p o e he ollowing:
•I∨II holds on he aces condi ion, nex and condi ion, body, condi ion,
nex i i holds on he aces condi ion, {body, condi ion }∗, nex .
•I∨II holds on he aces ag, condi ion, nex and ag, condi ion, body,
condi ion, nex i i holds on he aces ag, condi ion {body, condi ion }∗,
nex .

24 Chap e 3. Assignmen Analysis
We p o e i o he i s case only, as he o he is comple ely analogous. The igh -
o-le implica ion is ob ious. Suppose I ∨II holds o he ace condi ion, {body,
condi ion }n
i=0, nex o n≥2. I II holds, xis no ead in condi ion,body o nex ,
so i will no be ead in condi ion, {body, condi ion }n+1
i=0 , nex . I I holds, he new
assignmen could be in {body, condi ion }n
i=0 o in nex . I i is in body, hen I s ill
holds o {body, condi ion }n
i=0 body, condi ion, and i i is in nex , I implies ha x
is no ead in {body, condi ion }n
i=0 so nei he will i be ead in {body, condi ion
}n+1
i=0 making I s ill hold o condi ion, {body, condi ion }n+1
i=0 , nex
3.2.3 Mul iple Va iables app oach
The p e ious algo i hm has o un he analysis o e e y single a iable in he
p og am. Now we will do all ha p ocessing a he same ime o e e y assignmen
in he p og am. Fo ha , ins ead o ha ing a S a e, we will ha e se s whe e belonging
o hem means ha ing ha equi alen s a e. The special case o No Appea ed will
be ep esen ed by no being in any o hose se s. See how ha wo ks nicely o an
easy ini ializa ion. In his algo i hm, i will be easie o see how hey a e disjoin
and so, he condi ions ha hey ep esen a e mu ually exclusi e.
Algo i hm 2 Mul iple a iables app oach
1: unc ion Reade (Reade G aph,Unknown,Use ul,Useless)
2: NewUse ul ={(x, id)∈Unknown:x∈Reade G aph.L}
3: Unknown =Unknown NewUse ul
4: Use ul =Use ul ∪NewUse ul
5: end unc ion
6: unc ion Assignmen (AssigG aph,Unknown,Use ul,Useless)
7: NewUse ul ={(x, id)∈Unknown:x∈AssigG aph. he}
8: Unknown =Unknown NewUse ul
9: Use ul =Use ul ∪NewUse ul
10:
11: NewUseless ={(AssigG aph.y, id)∈Unknown}
12: Unknown =Unknown NewUseless
13: Useless =Useless ∪NewUseless
14:
15: i (AssigG aph.y,AssigG aph.id)/∈Unknown ∪Use ul ∪Useless hen
16: Unknown =Unknown ∪ {(AssigG aph.y,AssigG aph.id)}
17: end i
18: end unc ion
3.2. Co ec ness p oo 25
19: unc ion Block(BlockG aph,Unknown,Use ul,Useless)
20: o each G aph ∈BlockG aph.SubG aphs do
21: analyse (G aph,Unknown,Use ul,Useless)
22: end o
23: NewUseless ={(x, id)∈Unknown:x∈BlockG aph.Ou ingVa iables}
24: Unknown =Unknown NewUseless
25: Useless =Useless ∪NewUseless
26: end unc ion
27: unc ion Me geB anches(Un1, Un2, Ful1, Ful2, Less1, Less2)
28: Use ul =Ful1∪Ful2
29: Unknown = (Un1∪Un2) Use ul
30: Useless = (Less1∪Less2) (Use ul ∪Unknown)
31: e u n Unknown,Use ul,Useless
32: end unc ion
33: unc ion I Else(I ElseG aph,Unknown,Use ul,Useless)
34: analyse (I ElseG aph.condi ion,Unknown,Use ul,Useless)
35: Makes copies o Unknown,Use ul,Useless
36: analyse I ElseG aph.i ,Unknowni ,Use uli ,Uselessi 
37: analyse (I ElseG aph.else,Unknownelse,Use ulelse,Uselesselse)
38: Unknown,Use ul,Useless =Me geB anches 


Unknowni ,Unknownelse,
Use uli ,Use ulelse,
Uselessi ,Uselesselse



39: end unc ion
40: unc ion Loop(LoopG aph,Unknown,Use ul,Useless)
41: analyse (LoopG aph.condi ion,Unknown,Use ul,Useless)
42:
43: Makes copies o Unknown,Use ul,Useless
44: analyse (LoopG aph.body,Unknown1,Use ul1,Useless1)
45: analyse (LoopG aph.condi ion,Unknown1,Use ul1,Useless1)
46:
47: Makes copies o Unknown1,Use ul1,Useless1
48: analyse (LoopG aph.body,Unknown2,Use ul2,Useless2)
49: analyse (LoopG aph.condi ion,Unknown2,Use ul2,Useless2)
50:
51: Unknown,Use ul,Useless =Me geB anches 


Unknown,Unknown1,
Use ul,Use ul1,
Useless,Useless1



52: Unknown,Use ul,Useless =Me geB anches 


Unknown,Unknown2,
Use ul,Use ul2,
Useless,Useless2



53: end unc ion
26 Chap e 3. Assignmen Analysis
P oposi ion 3.2.6. Le Unknown =∅,Use ul =∅,Useless =∅, hen he ollowing
s a emen s a e equi alen :
•(x, id)∈Useless a e analyse (ASTG aph,Unknown,Use ul,Useless)has been
execu ed.
•(x, id)is useless in e e y ace o he Call G aph.
Mo eo e , he algo i hm always e mina es.
P oo . Te mina ion is he same as he p e ious algo i hm. We ocus on co ec ness
and comple eness. All we ha e o do is check ha we a e keeping he same condi ions
on he elemen s (x, id)as we did in he algo i hm o one assignmen a a ime.
Suppose we a e always alking abou he same s age o he analysis, i.e. i we say
ha in he call analyse (G aph,Unknown,Use ul,Useless),(x, id)∈Unknown ⇐⇒
S a e =Unknown in he call analyse ((x, id),G aph, S a e), we mean ha bo h
g aphs a e he same g aph in he Call G aph and he same logic applies o he es
o se s, esul s, e c.
So we wan o check ha
•(x, id)∈Unknown ⇐⇒ S a e =Unknown
•(x, id)∈Use ul ⇐⇒ S a e =Use ul
•(x, id)∈Useless ⇐⇒ S a e =Useless
•(x, id)/∈Unknown ∪Use ul ∪Useless ⇐⇒ S a e =No Appea ed
As we s a he call wi h all emp y se s, he i s call is cohe en be ween bo h
algo i hms.
Fo he es o he calls, we suppose ha hose p ope ies a e espec ed in he
a gumen se s and show ha he same is ue o he alue e u ned by he i s
algo i hm and he changes made on hese se s du ing he unc ion. To ligh en he
p oo , we will compa e each unc ion in a kind o in o mal way.
The easies one o compa e is he Me geB anches wi h he Table3.1 and see ha
hose se s c ea ed do espec he me ge ope a ion.
Now we compa e he di e en kinds o nodes unc ion:
•Reade node. The only di e ence be ween S a e alue and e u ned alue
occu s when an Unknown assignmen has i s a iable appea ing in he ead
a iables. Tha is exac ly he change made in he second algo i hm, making
su e ha bo h se s s ay disjoin .
•Assignmen node. The i s change happens i he S a e is Unknown. We
ake assignmen s in Unknown ha a e ead and swap hem o Use ul se and
a e ha swap elemen s in he emaining Unknown se o Useless se when
he a iable o e w i en is he same as he assignmen in Unknown. The o he
di e ence be ween he a gumen S a e and e u ned alue in he i s algo i hm
happens when S a e is No Appea ed. In ou unc ion ha means no being in
3.3. B inging he analysis o eal code 27
any o he se s, which is he i condi ion. Inside he e, when he ids coincide,
we swap i om No Appea ed s a e o Unknown se . See how ha is he same
hing ha is done in he i s app oach. I is easy o check how assignmen s
ha we e al eady in Use ul o Useless se s s ay in hem, as he i s algo i hm
does when he a gumen S a e is any o he equi alen ones.
•Block. Same as be o e, looping like his h ough s a emen s ca ies nicely he
p ope ies. I we u n ou a en ion o he Ou ingVa iables pa , we see how
we a e swapping elemen s in Unknown whose a iables a e going ou o scope
o he Useless se , whose equi alence was done in he o he app oach.
•I /Else node. See how making a copy o hese se s is he same as s o ing
he alue o he S a e and no ouching i un il he me gings occu . This also
applies o he nex case. A e p opaga ing he p ope ies h ough he eade
node o he condi ion and he blocks o he i and else pa , Me geB anches
does he same as we ha e seen, so p ope ies a e ca ied o he me ging node.
•While node. In he same way we ha e jus shown, we a e me ging he
p ope ies o ze o, one and wo loop i e a ions.
I we ocus on wha (x, id)∈Useless a e he execu ion means, ha ing in mind
he analogy made be o e, we see how i is equi alen o ha ing ob ained Useless in
he i s analysis, so he same p ope ies o co ec ness and comple eness hold.
3.3 B inging he analysis o eal code
The algo i hm desc ibed needs o be adap ed o he ac ual code. To ha end,
some unc ionali ies need o be added by eusing exis ing code when possible. We
will eco e he e he AST s uc u es we e le behind in he p oo , discuss some
imp o emen s ha we e conside ed a he ime and desc ibe he wa nings added.
3.3.1 Implemen a ion
The i s hing we need o do is make su e ha a iables ha e a unique iden i ie .
We ga e his o g an ed when speci ying he pseudocode, bu in eali y, we need o
espec a iable shadowing, which makes a iable names no a unique cha ac e iza-
ion o a posi ion o memo y. To sol e his we ha e used a ci com En i onmen
ha maps a iable names o an in ege aking ca e o block logic. All we ha e o
do is make su e we a e in oducing a block in he Block unc ion and popping i a
he end. This s uc u e has been ligh ly modi ied o be able o ob ain he Ou ing
Va iables se be o e popping he uppe block.
Assignmen s a e no longe ep esen ed jus by hei id and hei a iable name,
hey also include in o ma ion abou he ins uc ion o add a wa ning. This makes
he analysis use ul o build on op o i u u e unc ionali ies ha a e easily de i ed
om knowing which assignmen s a e ne e used.
34 Chap e 4. Benchma king
Figu e 4.1: Game e en in Da k Fo es . Sou ce [37]. Gubsheep & Da k Fo es ©
despi e being a e y simple game by nowadays s anda ds, i is played by housands
o people.
4.2 E alua ion p ocess
We a e in e es ed in assessing i elimina ing unnecessa y assignmen s in he wi ness
code imp o es i s execu ion ime. To e alua e hese imes in a signi ican amoun
o ci cui s some bash and Py hon sc ip s ha e been de eloped. They help us in
collec ing he da a, o e ed by he compile , measu ing execu ion imes and pu ing
all esul s oge he in a common di ec o y.
A i s , only a bash sc ip was used o measu e execu ion imes. This means ha
a lo o noise om p epa ing he execu able by he sys em is in oduced, making
he imes less eliable. To educe he noise in he execu ions only C++ code was
assessed, lea ing WebAssembly ou o he ques ion. An imp o emen in C++ will
aduce in o WebAssembly, al hough no in he same o de gi en all ha su ounds
web p og amming languages. Because we we e dealing only wi h C++ and we
wan ed o elimina e he ime i akes o call a bina y, he inside common code o
e e y C++ ou pu ha ci com gene a es has been modi ied so i measu es ime
inside he p og am wi h a high- esolu ion clock and ou pu s ha in o ma ion in o
a ile, common among di e en execu ions.
We ha e es ed he analysis agains he compile wi h he same e sion bu
wi hou any modi ica ion om his p ojec , i.e he code om he o icial eposi o y,
always up- o-da e. Bea in mind ha his p ojec has been de eloped while me ging
e e y upda e om he pa en o he o k, so he code ou side his analysis is always

4.3. Pe o mance 35
common. A e compiling bo h e sions wi h di e en names we could execu e
a signi ican amoun o imes he code w i en by each compile , sa ing execu ion
imes in sepa a e iles. We accoun ed o a es as alid when he s anda d de ia ion
o he measu emen s was simila and ook he mean as he esul .
All o he p e ious p ojec s ha e mo e han jus ci com ci cui s. They ha e
uni a y es s, sna kjs in eg a ion, e c. We we e only in e es ed in ci cui s ha ha e a
se o inpu s, ei he as a JSON ile o inside he es ing code. We ha e also excluded
he smalle ci cui s as hei execu ion imes end o be a bi mo e uns able. The
numbe o imes each p og am was un a ied be ween 40 and 2000, depending on
how long i ook o execu e once.
Some smalle ci cui s e en appea ed o be slowe wi h he new code. To de e -
mine whe he some hing s ange was happening, we p o iled he code wi h Valg ind
and compa ed he ou pu code. The only di e ence wi h he olde code was he
disappea ance o he useless assignmen s. The bina ies we e checked o be di e -
en a e g++ compiled hem wi h O3 op imiza ion. The conclusion was ha due
o compile op imiza ion and small execu ion imes, uns able execu ion imes we e
bound o appea , bu he code was comple ely ine.
E e y es included a inal bash command (di ) o see whe he he wi ness
c ea ed we e he same. I is mos impo an o ema k ha no a single p og am
c ea ed by his p ojec ’s compile c ea ed a wi ness di e en om ha compu ed
by he o icial e sion o ci com. This eassu es he ac ha he implemen a ion
done ma ches ha desc ibed in Chap e 3.
4.3 Pe o mance
All o he ollowing es s we e un on a Linux Min 20.2 (5.4.0 ke nel e sion)
machine, wi h an In el i5-6600K (3.9 GHz), 16GB o RAM and 32 GB o swap
memo y.
We i s s a by assessing he impac on he compile i sel . We wan o see
whe he unning his analysis ha ms he compile ’s pe o mance. The analysis check-
ings done a each node a e linea in he numbe o a iables ead in he node and
he amoun o assignmen s in he whole p og am. This is hanks o using HashMaps
and HashSe s. Al hough hese s uc u es’ pe o mance can decay in he wo s o
ways i hei size is e y la ge, we a e su e ha no ci com p og am will e e each
ha numbe o assignmen s o show his p ope y. I his was e e o happen, much
bigge p oblems would a ise. Bea ing in mind ha he wo k a each node is linea ,
we now ocus on he pa h ollowed in ecu sion calls. A node is a e sed once unless
i is pa o a loop. In ha case, a loop is analysed wice. Tha means ha in he
wo s case, he numbe o nodes a e sed scales as a powe o 2 o he nes ing le el
o loops. Because no p og am e e has a nes ing le el oo high, his will nei he
ha m he pe o mance.
Once he heo e ical aspec s a e clea , we ocus on some eal es ing. To p o ile
he compile , a common ool o Rus p og ams has been used. This is Flameg aph
[40], a isual ool ha c ea es an in e ac i e s g ile. I can be opened wi h a web
b owse o explo e whe e he execu ion ime was spen . I calcula es hese imes by
36 Chap e 4. Benchma king
aking pe iodic samples while he code is unning and assessing whe e i is a he
momen . To illus a e how much his analysis hu he compile , we should say ha
he mos di icul ask wi h his p ocess o he han ins alling he ool, was o ind
an execu ion whe e a single sample had landed on he analysis so i could be shown
in he diag ams. In o he wo ds, he analysis akes i ually no ime compa ed o
he es o he compila ion, in line wi h he es o he s a ic analysis o ci com,
which akes a minimal ac ion o he compu a ional e o .
Figu e 4.2: Flameg aph ou pu . Pu ple ac ion co esponds o he ype analysis o
he compile
In Figu e 4.2, he imes b eakdown o he whole execu ion can be seen. This
p o iling was done by compiling an a e aged size ci cui om he ci com ECDSA
lib a y (pubkeygen.ci com). No ou pu was asked o , so hese execu ion imes
do no e en include code gene a ion and cons ain s ou pu . I only akes in o
accoun pa sing, s a ic analysis, code in e p e a ion and cons ain s simpli ica ion.
The s a ic analysis is highligh ed in pu ple in Figu e 4.2. In Figu e 4.3, he s a ic
analysis (called ype analysis in he code) has been zoomed and he assignmen s
analysis highligh ed in pu ple again. We can see how i akes he same e o as
he es o he s a ic analysis p e iously de eloped. Wi h 5 samples landing in ou
analysis, i means a 0.04% o he o al execu ion ime.
Figu e 4.3: Zoom in o ype analysis. Pu ple ac ion co esponds o he implemen ed
analysis
On he pe o mance o he wi ness calcula o s, he esul s a e no ha egula .
Many ac o s play a pa in he execu ion ime o a p og am, and al hough elimina -
4.3. Pe o mance 37
ing useless ins uc ions should dec ease he compu a ional e o , in eali y, he e is
no a clea co ela ion be ween he numbe o ins uc ions elimina ed and he im-
p o emen in pe o mance gained. I is ema kable, howe e , ha wi h a i ually
ee-o -cos analysis, we can achie e up o a 3% imp o emen in he bigge wi nesses.
Resul s ha e been especially good in he ECDSA eposi o y, whe e ou pu p og ams
a e much bigge . In Table 4.1 he e is a lis o he ci cui s es ed.
Ci cui Assignmen s
Elimina ed
Pe o mance
Imp o emen
To al
Execu ion Time
ECDSA-e h_add 4.3% 1.6% 183 seconds
ECDSA-g oupsig 4.5% 3.0% 180 seconds
ECDSA-pubkeygen 3.2% 3.1% 171 seconds
ECDSA- e i y 2.6% 3.4% 577 seconds
ED25519-ba ch e i y 10.5% 0.0% 115 seconds
ED25519-scala mul 9.6% 0.6% 81 seconds
ED25519- e i y 9.5% 0.4% 223 seconds
o es -ini 14.5% 0.0% 18 seconds
o es -mo e 14.5% 0.7% 19 seconds
o es -mo e 14.5% 0.1% 19 seconds
o es -whi elis 21% -0.5% 16 seconds
ML-mnis 5.7% 0.2% 160 seconds
ML-mnis _p ecision 3.4% 0.1% 1193 seconds
Rollup-16 10.8% 0.2% 99 seconds
Rollup-16_1 10.8% 0.5% 117 seconds
Table 4.1: Pe o mance imp o emen s o di e en ci cui s
F om he pe cen age o assignmen s elimina ed, he majo i y o hem we e a -
i icially added assignmen s by he ci com pa se . The o he ac ion o useless
assignmen s we e usually made useless by he cons an p opaga ion phase, so he
p og amme hemsel es had no done any hing w ong. Al hough his seems o de-
c ease he impo ance o some aspec s we deemed use ul, we ha e o keep in mind
ha hese ci cui s a e mos ly de eloped by expe s and hei w i ing p ocess is al-
mos o e . Ha ing a ea u e in he compile ha poin s ou useless assignmen s
in oduced by he p og amme is much mo e use ul du ing he de eloping s ages o
ci cui s.
Chap e 5
Conclusions
In his las chap e , he conclusions d awn om his p ojec will be p esen ed. To
ha end, we summa ize he de elopmen done and wha has been achie ed wi h i .
The i s hing ha was done in he p ojec was o s udy an unknown code
base. Gi en ha a compile ’s code is no always he easies o unde s and and he
p og amming language i is w i en in was also unknown a i s , he p ocess was
slow. I is clea now ha one o he bes app oaches ound wi h his p ojec was
an ini ial ead on he p og amming language basics ollowed by an example-d i en
lea ning pe iod. To achie e Objec i e I, ac i e communica ion wi h he de elope s
eased he p ocess. I is howe e c ucial o ge a i s imp ession o he p ojec ’s
s uc u e and begin aking no es om ea ly imp essions so one can eco e hose
ideas la e . The ask o unde s anding a whole code eposi o y is long, so one will
ine i ably o ge wha was deduced p e iously unless i is w i en down.
A ele an aspec o he p ojec has been lea ning o p og am in Rus . As men-
ioned in Chap e 2, Rus has some special ea u es ega ding memo y usage. Along
wi h i s ma ching s uc u es make he lea ning cu e qui e s eep one. Once o e -
come, some o he aspec s o he language make i look ad an ageous. Fo ins ance,
he compile gi es e y good hin s on wha is w ong in he code. Pa e n ma ch-
ing and enume a es allow o e y lexible s uc u e c ea ion, which i s pe ec ly
he AST componen s, o example. The ca e he compile places o e code sa e y
comes as a nuisance a i s , bu i can be help ul when i comes o being su e ha
no undesi ed side e ec s o da a aces a e p esen in he code once i compiles. In
he ligh o p esen Rus up ising popula i y, ge ing o know his p og amming
language will hope ully come as use ul in he u u e oo.
Ful illing Objec i e II, i has come clea he impo ance o s a ic analysis. I
is a cheap way, compu a ion wise, o de ec e o s in he de elopmen p ocess.
De ec ing his kind o e o in he compiling p ocess helps p og amme s sa e a lo
o ime debugging and ge ing un ime e o s. S a ic analysis also plays a huge
ole in code op imiza ion. No e e y op imiza ion can be le o lowe le el code o
CPU le el dynamic op imiza ion. Some abs ac ions a e use ul when i comes o
unde s anding he seman ics o a p og am, and no using his in o ma ion in s a ic
analysis is neglec ing a big oppo uni y o be e code pe o mance. Al hough he
echniques s udied in classic books in Sec ion 2.5 we e no implemen ed exac ly in
39

40 Chap e 5. Conclusions
he p ojec , he ideas gi en by he mos popula e e ences in compile s can always
be ound in one’s app oach o hese p oblems.
Seman ic p o ing has always been an elusi e aspec in Compu e Science. While
ha ing wonde ul ma hema ical p ope ies and p o iding wi h he igo and sa e y
ma hema ical ools gi e, i s complexi y scales e y apidly wi h a p og am’s size.
No only ha , e en he cons uc ions allowed by a p og amming language can make
seman ic p o ing a i anic ask. In his p ojec , a ligh e app oach was aken. The
algo i hm’s p oo was b oken down in o wo phases. The second one made hea y
use o he p ope ies gi en by he i s p oposi ion and hus showed how o ca y a
simple p og am’s ea u es in o a mo e complex one ha ollows a simila schema.
Gene al seman ic p o ing has no been ound any easie in his p ojec , and ha
is why i was no he desi ed app oach. I has howe e bo n ou use ul o make a
speci ic p oo o he analysis. I no only assu ed he p ope ies sough bu helped
o clean he code and i s da a s uc u es. The e is no be e way o assu ing we
ha e ul illed Objec i e III han a p ope ma hema ical p oo .
Being mo e speci ic abou ci com, code sa e y has been imp o ed. No using
a iables which we e assigned a signal is a e y common e o among ci com de el-
ope s. Al hough no an e o i sel , i is a e y s ong indica o o a p og amme ’s
mis ake. This analysis has p o en e ec i e in de ec ing his si ua ion, and he hope
is i will sa e de elope s aluable ime when building hei ci cui s. Falling back o
ou objec i es, his clea ly co e s Objec i e IV.
Al hough his was no an objec i e on i s own, de eloping a small sui e o sc ip s
o help benchma k he compile has p o ed a good way o inally lea ning bash.
Ha ing o es wi h a ious eposi o ies, each wi h i s own s uc u e, led o he
c ea ion o hese sc ip s. The il e ing, edi ec ion o ou pu and easy managemen
o di ec o ies ha e come in e y handy o cen e he benchma king esul s. This has
made he p ocessing and analysis o he es s’ da a an easie ask. I has also p o en
a sui able use o a sc ip ing language like Py hon. Hence, an addi ional lea ning
ou come o he p ojec has been ha sc ip ing language can au oma e day- o-day
compu e asks wi h li le e o .
On a las no e, Objec i e V has been comple ed o a ce ain deg ee. I was a
i s hough ha his addi ional ime o e head c ea ed by he pa se was signi ican
enough o be wo h ge ing id o . While i has p o en i egula a imes, and no oo
wo ying a o he s, we ha e been able o elimina e his o e head in e e y p og am
in case he e was any. The pe cen age o imp o emen migh no seem much a
i s , bu aking in o accoun ha we can each up o a 3.5% imp o emen wi h
an analysis ha only cos s a ound 0.05% o he compile ’s ime, i is ega ded as
a wo hy in es men . Due o his, i is planned o include he analysis de eloped
in he o icial ci com eposi o y in he nea u u e. The e o e, his p ojec will be
pa o a compile used by housands o de elope s.
Bibliog aphy
[1] J.-J. Quisqua e , M. Quisqua e , M. Quisqua e , M. Quisqua e , L. Guillou,
M. A. Guillou, G. Guillou, A. Guillou, G. Guillou, and S. Guillou, “How o
explain ze o-knowledge p o ocols o you child en,” in Ad ances in C yp ol-
ogy—CRYPTO’89 P oceedings, pp. 628–631, Sp inge , 2001.
[2] B. Pa no, J. Howell, C. Gen y, and M. Rayko a, “Pinocchio: Nea ly p ac ical
e i iable compu a ion,” Communica ions o he ACM, ol. 59, no. 2, pp. 103–
112, 2016.
[3] J. Boo le, A. Ce ulli, P. Chaidos, J. G o h, and C. Pe i , “E icien ze o-
knowledge a gumen s o a i hme ic ci cui s in he disc e e log se ing,” in
Ad ances in C yp ology–EUROCRYPT 2016: 35 h Annual In e na ional Con-
e ence on he Theo y and Applica ions o C yp og aphic Techniques, Vienna,
Aus ia, May 8-12, 2016, P oceedings, Pa II 35, pp. 327–357, Sp inge , 2016.
[4] E. Ben-Sasson, A. Chiesa, E. T ome , and M. Vi za, “Succinc non-in e ac i e
ze o-knowledge o a on neumann a chi ec u e,” in 23 d {USENIX}Secu i y
Symposium ({USENIX}Secu i y 14), pp. 781–796, 2014.
[5] B. Whi eHa , J. Baylina, and M. Bellés, “Baby jubjub ellip ic cu e,” E he eum
Imp o emen P oposal, EIP-2494, ol. 29, 2020.
[6] iden3, “Ci com documen a ion.” A ailable a h ps://docs.ci com.io/
(27/04/2023).
[7] iden3, “Ci com eposi o y.” A ailable a h ps://gi hub.com/iden3/ci com
(27/04/2023).
[8] M. Bellés-Muñoz, M. Isabel, J. L. Muñoz-Tapia, A. Rubio, and J. Baylina, “Ci -
com: A ci cui desc ip ion language o building ze o-knowledge applica ions,”
IEEE T ansac ions on Dependable and Secu e Compu ing, 2022.
[9] iden3, “Old ci com eposi o y.” A ailable a h ps://gi hub.com/iden3/
ci com_old (27/04/2023).
[10] H. Ga cía Na a o, “Design and implemen a ion o he ci com 1.0 compile ,”
UCM ep in s, 2020.
41
42 BIBLIOGRAPHY
[11] Rus Founda ion, “The us handbook.” A ailable a h ps://doc. us -lang.
o g/s able/book/ (27/04/2023).
[12] Rus Founda ion, “Rus by examples.” A ailable a h ps://doc. us -lang.
o g/ us -by-example/ (27/04/2023).
[13] L. T. Kei h D. Coope , Enginee ing a Compile . ACADEMIC PRESS, sec-
ond ed., 2012.
[14] A. P. Ye sho , “Alpha—an au oma ic p og amming sys em o high e iciency,”
Jou nal o he ACM (JACM), ol. 13, no. 1, pp. 17–24, 1966.
[15] E. S. Low y and C. W. Medlock, “Objec code op imiza ion,” Communica ions
o he ACM, ol. 12, no. 1, pp. 13–22, 1969.
[16] Wikipedia, “Lis o ools o s a ic code analysis.” A ailable a h ps:
//en.wikipedia.o g/wiki/Lis _o _ ools_ o _s a ic_code_analysis
(2/05/2023).
[17] J. B uno and R. Se hi, “Code gene a ion o a one- egis e machine,” J. ACM,
p. 502–510, 1976.
[18] A. V. Aho, R. Se hi, and J. D. Ullman, Compile s: p inciples, echniques, and
ools. Addison-wesley Reading, second ed., 2007.
[19] A. V. Aho, R. Se hi, and J. D. Ullman, Compile s: p inciples, echniques, and
ools, ch. 8 and 9. Addison-wesley Reading, second ed., 2007.
[20] L. T. Kei h D. Coope , Enginee ing a Compile , ch. 8 and 9. ACADEMIC
PRESS, second ed., 2012.
[21] K. Kennedy and J. R. Allen, Op imizing compile s o mode n a chi ec u es: a
dependence-based app oach. Mo gan Kau mann Publishe s Inc., 2001.
[22] R. Mo gan, Building an op imizing compile . Digi al P ess, 1998.
[23] V. Vysso sky and P. Wegne , “A g aph heo e ical o an sou ce language an-
alyze . a & bell labo a o ies, mu ay hill, nj,” Manusc ip , 1963.
[24] D. Malcolm, “The s a e o s a ic analysis in he gcc 12 com-
pile .” A ailable a h ps://de elope s. edha .com/a icles/2022/04/
12/s a e-s a ic-analysis-gcc-12-compile # (2/05/2023).
[25] gcc GNU, “Op ions o eques o supp ess wa nings.” A ailable a h ps://
gcc.gnu.o g/onlinedocs/gcc/Wa ning-Op ions.h ml (2/05/2023).
[26] L. S eue nagel, “Implemen ing unused a iable elimina ion and un-
de ined a iable de ec ion o he solang compile .” A ailable a
h ps://medium.com/coinmonks/implemen ing-unused- a iable...
(2/05/2023).
BIBLIOGRAPHY 43
[27] M. B own, “Be e unused a iable de ec ion in psalm 4.” A ailable a h ps:
//psalm.de /a icles/be e -unused- a iable-de ec ion (2/05/2023).
[28] A. Sanka , “Classical and quan um algo i hms o isogeny-based c yp og aphy,”
Mas e ’s hesis, Uni e si y o Wa e loo, 2015.
[29] C. Cos ello, P. Longa, and M. Naeh ig, “E icien algo i hms o supe singula
isogeny di ie-hellman,” in Ad ances in C yp ology–CRYPTO 2016: 36 h An-
nual In e na ional C yp ology Con e ence, San a Ba ba a, CA, USA, Augus
14-18, 2016, P oceedings, Pa I 36, pp. 572–601, Sp inge , 2016.
[30] A. J. Di Scala, A. Gangemi, G. Romeo, and G. Ve ne i, “Special subse s o
add esses o blockchains using he secp256k1 cu e,” Ma hema ics, ol. 10,
no. 15, p. 2746, 2022.
[31] “ci com-ecdsa eposi o y.” A ailable a h ps://gi hub.com/0xPARC/
ci com-ecdsa/ ee/mas e (18/05/2023).
[32] S. Nako , P ac ical C yp og aphy o de elope s, ch. Digi al signa u es, EdDSA
and Ed25519. online, 2018.
[33] E. Labs, “ci com ed25519 eposi o y.” A ailable a h ps://gi hub.com/
Elec on-Labs/ed25519-ci com (20/05/2023).
[34] “He mez 1..0 documen a ion.” A ailable a h ps://docs.he mez.io/He mez_
1.0/abou /scalabili y/ (20/05/2023).
[35] H. Pan, F. Ho, and H. Palacci, “Zk machine lea ning.” A ailable a h ps:
//0xpa c.o g/blog/zk-mnis (20/05/2023).
[36] B. Gu, “Da k o es eposi o y.” A ailable a h ps://gi hub.com/
da k o es -e h/da k o es - 0.6/ ee/main (20/05/2023).
[37] R. Khan, “da k o es : a one-o -a-kind sci- i blockchain
game buil on cu ing-edge c yp og aphy.” A ailable a
h ps://www.designboom.com/ echnology/da k- o es -one-o -a-kind...
(20/05/2023).
[38] R. Das, “How o play da k o es , he zksna k powe ed mmo game.” A ail-
able a h ps://medium.com/coinmonks/how- o-play-da k- o es - he...
(20/05/2023).
[39] B. Gu, “Da k o es webpage.” A ailable a h ps://zkga.me/ (20/05/2023).
[40] B. G egg, “Flameg aph eposi o y.” A ailable a h ps://gi hub.com/
b endang egg/FlameG aph (20/05/2023).