IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 1
An OpenMP Ex ension ha Suppo s
Th ead-Le el Specula ion
Se gio Aldea, Al a o Es ebanez, Diego R. Llanos, Senio Membe , IEEE, and A u o Gonzalez-Esc ibano
Abs ac —OpenMP di ec i es a e he de- ac o s anda d o sha ed-memo y pa allel p og amming. Howe e , OpenMP does no
gua an ee he co ec ness o he pa allel execu ion o a gi en loop i un ime da a dependences a ise. Consequen ly, many highly-
pa allel egions canno be sa ely pa allelized wi h OpenMP due o he possibili y o a dependence iola ion. In his pape , we p opose o
augmen OpenMP capabili ies, by adding Th ead-Le el Specula ion (TLS) suppo . Ou con ibu ion is h ee old. Fi s , we ha e de ined
a new specula i e clause o a iables inside pa allel loops. This clause ensu es ha all accesses o hese a iables will be ca ied ou
acco ding o sequen ial seman ics. Second, we ha e c ea ed a new, so wa e-based TLS un ime lib a y o ensu e co ec ness in he
pa allel execu ion o OpenMP loops ha include specula i e a iables. Thi d, we ha e de eloped a new GCC plugin, which seamlessly
ansla es ou OpenMP specula i e clause in o calls o ou TLS un ime engine. The esul is he ATLaS C Compile amewo k, which
akes ad an age o TLS echniques o expand OpenMP unc ionali ies, and gua an ees he sequen ial seman ics o any pa allelized
loop.
Index Te ms—Pa allelism and concu ency, code gene a ion, h ead-le el specula ion, op imis ic pa alleliza ion
F
1 INTRODUCTION
THE ad en o mul ico e echnologies in he new
cen u y made pa allel p ocessing ubiqui ous. Many
pa allel languages and pa allel ex ensions o sequen ial
languages ha e been p oposed o exploi he capabili ies
o mode n mul ico e sys ems. The mos success ul p o-
posal is OpenMP [1], a di ec i e-based pa allel ex ension
o sequen ial languages (such as C, Fo an o C++) ha
allows pa allel execu ion o use -de ined code egions.
Figu e 1 shows an example o (a) a sequen ial C loop,
and (b) i s pa alleliza ion wi h OpenMP di ec i es. As
can be seen, all a iables inside he loop body should
be classi ied as p i a e o sha ed. In o mally speaking,
a iables whose alues a e always se in a gi en i e a ion
be o e hei use should be labeled as p i a e, while a i-
ables ha ha e alues isible by all h eads execu ing
he loop in pa allel should be classi ied as sha ed. In ou
example, a[] is a ead-only sha ed ec o , while [] is
a sha ed ec o ha is modi ied by each i e a ion.
As OpenMP is a simple and powe ul mechanism
o code pa alleliza ion, i s use has se e al limi a ions.
Fi s , he classi ica ion o all a iables inside he c i ical
egion, acco ding o hei use, is a ime-consuming,
e o -p one ask. Second, OpenMP does no ensu e he
pa allel execu ion o he code acco ding o sequen ial
seman ics, as he p og amme is esponsible o such a
ask. In he example shown in Fig. 1, he p og amme is
esponsible o ensu ing ha each h ead modi ies a di -
e en elemen o []. Thi d, in many cases, po en ially-
•S. Aldea, A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano a e wi h
Dp o. In o má ica, Uni e sidad de Valladolid, Campus Miguel Delibes,
47011, Valladolid, Spain.
E-mails: {se gio,diego,a u o}@in o .u a.es, [email p o ec ed]
#p agma omp pa allel o
p i a e (i,b) sha ed (a, )
o (i=0; i<MAX; i++) { o (i=0; i<MAX; i++) {
b = unc(i); b = unc(i);
[i] = b *a[i]; [i] = b *a[i];
} }
(a) (b)
Fig. 1. Example o loop pa alleliza ion wi h OpenMP.
#p agma omp pa allel o
p i a e (i,b) sha ed (a,k)
specula i e( )
o (i=0; i<MAX; i++) { o (i=0; i<MAX; i++) {
b = unc(i); b = unc(i);
i (b==k) i (b==k)
[i] = [i-b]; [i] = [i-b];
else else
[i] = b *a[i]; [i] = b *a[i];
} }
(a) (b)
Fig. 2. A loop ha canno be sa ely pa allelized wi h
cu en OpenMP clauses (a), and i s pa alleliza ion wi h
ou new specula i e clause (b).
pa allel egions canno be sa ely pa allelized because
hei con ol low depends on un ime da a. Conside
he code depic ed in Fig. 2. Suppose ha he alue o k
is no known a compile ime. Assuming b>0 o a gi en
i, i he pa allel execu ion o he loop calcula es i e a ion
ibe o e i e a ion i-b, access o [i-b] may e u n an
ou da ed alue, b eaking sequen ial seman ics. The only
way o gua an ee a co ec beha io would be o se ialize
he execu ion o i e a ions i−band i, a di icul ask in
he gene al case.
Sa ely pa allelizing loops ha may p esen un ime
dependence iola ions can ha e a signi ican impac in
e ms o pe o mance. We ha e p e iously measu ed he
amoun o loop-le el pa allelism ha could be ex ac ed
om he SPEC CPU 2006 benchma k, wi h di e en
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 2
echniques [2]. Ou esul s show ha , while a ound
48% o he loops p esen in he applica ions analyzed
( ep esen ing a ound 13% o hei agg ega e execu ion
ime) a e po en ially pa allelizable wi h exis en pa allel
p og amming models such as OpenMP, an addi ional
38% o loops ( ep esen ing a ound 20% o he execu ion
ime) could be un in pa allel wi h he help o un ime
specula i e pa alleliza ion echniques.
Ou p oposal consis s in augmen ing OpenMP wi h
so wa e-based, Th ead-Le el Specula ion (TLS) ech-
niques o ensu e ha de ini ions and uses o sha ed a i-
ables a e ca ied ou acco ding o sequen ial seman ics.
This solu ion allows he OpenMP p og amming model
o be used e en when dependence iola ions may a ise
a un ime. To do so, we de ine a new specula i e clause.
Va iables labeled as specula i e will be accessed ollowing
wo simple ules:
•All eads o a specula i e a iable will e u n he
mos up- o-da e alue o his a iable. This alue
can ei he be gene a ed p e iously by his h ead
o by any o i s p edecesso s, de ined as h eads
ha execu e ea lie i e a ions acco ding o sequen ial
seman ics. This is called a o wa ding ope a ion.
•All w i es o a specula i e a iable will s o e he
alue in a local copy, and will check whe he a
successo h ead ( ha is, h eads ha a e execu -
ing “ u u e” i e a ions) has consumed an ou da ed
alue o his a iable. In his case, he o ending
h ead (and possibly some o i s successo s) will be
s opped and e-s a ed, in o de o o ce hem o
consume he upda ed alue o he a iable. This is
called a squash ope a ion.
As long as a dependence iola ion o ces he alues o
specula i e a iables o be disca ded, all h eads main ain
e sion copies o he specula i e a iables being accessed.
When a non-specula i e h ead ( ha is, a h ead wi h no
ali e p edecesso s) success ully inishes he execu ion
o i s block o consecu i e i e a ions, all changes a e
commi ed o he main copy o all specula i e a iables.
A e his commi ope a ion, he h ead will become he
mos specula i e one, since i will execu e he ollowing
block o i e a ions ha emains unassigned.
The h ee main con ibu ions o his pape a e he
ollowing:
1) We ha e de ined an ex ension o OpenMP spec-
i ica ions, adding a clause o suppo specula i e
accesses o da a in omp pa allel o cons uc s. This
clause ollows he guidelines p oposed by Aldea e
al. [3].
2) We ha e c ea ed a b and-new TLS un ime lib a y
ha handles he pa allel execu ion o loops ha
includes specula i e a iables, including suppo o
specula i e access o poin e -based da a o any
size wi hou he need o a compile- ime analysis.
This un ime lib a y no only manages accesses o
specula i e da a, bu also handles he scheduling o
i e a ions among h eads and ensu es co ec ness in
he pa allel execu ion o he loop.
3) Finally, we ha e de eloped a new plugin-based
compile pass o he GCC OpenMP implemen a-
ion o suppo he specula i e clause. This pass
ans o ms he loop o be pa allelized, inse ing he
un ime TLS calls needed o (a) dis ibu e blocks o
i e a ions among p ocesso s, (b) pe o m specula-
i e loads and s o es o specula i e a iables, and
(c) pe o m pa ial commi s o he co ec esul s
calcula ed so a .
The esul is ATLaS, a comple e amewo k ha allows
OpenMP o execu e loops in pa allel wi hou he need
o a p io dependence analysis. Ou pe o mance e alua-
ion, using bo h syn he ic and eal-wo ld applica ions on
a eal mul ico e sys em, shows ha his app oach leads
o pe o mance speedups.
The es o he pape is o ganized as ollows. Sec ion 2
in oduces TLS key concep s. Sec ion 3 desc ibes some
ela ed wo k. Sec ion 4 b ie ly desc ibes ou p oposal o
a new OpenMP specula i e clause. Sec ion 5 desc ibes in
de ail he a chi ec u e o ou new TLS un ime lib a y.
Sec ion 6 shows how we ha e added suppo o handle
ou new clause in he GCC OpenMP compile . Sec ion 7
p esen s he expe imen al e alua ion. Finally, Sec . 8
summa izes ou conclusions.
2 THREAD-LEVEL SPECULATION
Specula i e pa alleliza ion (SP), also called Th ead-Le el
Specula ion (TLS) o Op imis ic Pa alleliza ion [4], as-
sumes ha sequen ial code can be op imis ically exe-
cu ed in pa allel, and elies on a un ime moni o o
ensu e ha no dependence iola ions a e p oduced.
A dependence iola ion appea s when a gi en h ead
gene a es a da um ha has al eady been consumed by
a successo in he o iginal sequen ial o de . In his case,
he esul s calcula ed so a by he successo (called he
o ending h ead) a e no alid and should be disca ded.
Ea ly p oposals [5], [6] s op he pa allel execu ion and
es a he loop se ially. O he p oposals s op he o -
ending h ead and all i s successo s, e-execu ing hem
in pa allel [7], [8], [9], [10]. A hi d op ion (see e.g.
[11], [12], [13]) is o only e-s a he o ending h ead
and subsequen h eads ha ha e ac ually consumed
any alue om i , leading o a no iceable pe o mance
imp o emen in some cases.
Figu e 3 shows an example o h ead-le el specula ion.
The igu e ep esen s ou h eads execu ing agmen s
o ou consecu i e i e a ions o he same loop. The alue
o xwas no known a compile ime, so he compile
was no able o ensu e ha accesses o he SV s uc u e
do no lead o dependence iola ions when execu ing
hem in pa allel. Howe e , he ac ual alues o x o
each i e a ion a e known a un ime.
Unde specula i e execu ion, each h ead main ains
a e sion copy o he da a s uc u e ha is accessed
specula i ely (he e, he SV ec o ). A compile ime,
he o iginal code is augmen ed o pe o m specula i e
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 3
5
8
10
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
6
7
9
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
2
4
6
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
(c) In−o de commi o da a om success ully− inished h eads
0
1
3 SV[x] = LocalVa 2
Time
LocalVa 1 = SV[x]
Th ead 1 (non spec)
(i e a ion 1, x = 1) (i e a ion 2, x = 1)
Th ead 2
(i e a ion 3, x = 2)
Th ead 3 Th ead 4 (mos −spec)
(i e a ion 4, x = 2)
Re e ence
copy o
s [2]
(Time 4: Th ead 2 o wa ds upda ed alue o s [1] om h ead 1)
(Time 3: h ead 1 de ec s no dependence iola ions)
(Time 6: h ead 1 de ec s no dependence iola ions)
(Time 8: Th ead 3 o wa ds alue o s [2] om e e ence copy)
(Time 7: Th ead 4 o wa ds alue o s [2] om e e ence copy)
(Time 10: Th ead 3 de ec s iola ion: h ead 4 squashed)
(b) Specula i e loads wi h mos − ecen alue o wa ding
(a) Specula i e s o es plus de ec ion o dependence iola ions
Fig. 3. Example o specula i e execu ion o a loop and summa y o ope a ions ca ied ou by a un ime TLS lib a y.
s o es, specula i e loads, and in-o de commi s. In addi-
ion, he loop s uc u e is ea anged in o de o allow
he e-execu ion o squashed i e a ions. The ollowing
pa ag aphs desc ibe hese ope a ions in mo e de ail.
Specula i e s o es A compile ime, all w i e ope a ions
o he da a s uc u e being specula i ely accessed should
be eplaced wi h a specula i e s o e unc ion. This unc ion
w i es he da um in he e sion copy o he cu en
h ead, and ensu es ha no h ead execu ing a subse-
quen i e a ion has al eady consumed an ou da ed alue
o his s uc u e elemen , a si ua ion called “dependence
iola ion”. I such a iola ion is de ec ed, he o ending
h ead and i s successo s a e s opped and es a ed. In
he example depic ed in Fig. 3, he checks o depen-
dence iola ions pe o med by Th eads 1 and 2 do no
ind any successo ha has consumed an ou da ed alue
o SV[1]. Howe e , a ime 10, Th ead 3 disco e s
ha Th ead 4 has al eady consumed an ou da ed alue
o SV[2], so a dependence iola ion has been ound.
The e o e, Th ead 4 should be s opped and es a ed, in
a so-called squash ope a ion. When Th ead 4 is es a ed,
i will o wa d he upda ed alue o SV[2] om Th ead
3, being able o con inue he execu ion o he i e a ion
assigned o i .
Specula i e loads A compile ime, all eads o he
specula i e da a s uc u e a e eplaced by a unc ion
ha pe o ms a specula i e load. This unc ion ob ains he
mos up- o-da e alue o he elemen being accessed.
I a p edecesso ( ha is, a h ead execu ing an ea lie
i e a ion) has al eady ead o w i en ha elemen , he
alue is o wa ded (as Th ead 2 does in Fig. 3). I no , he
unc ion ob ains he alue om he e e ence copy o he
da a s uc u e (as Th ead 3 does in he igu e).
Commi -o -disca d ope a ion I no dependence iola-
ion a ises du ing he execu ion o a gi en h ead, i s
changes o he specula i e da a s uc u e should be com-
mi ed o he e e ence copy o he da a s uc u e. No e
ha commi s should be done in o de , o ensu e ha
he mos up- o-da e alues a e s o ed. In he case o a
dependence iola ion, he in e media e esul s calcula ed
by his h ead should be disca ded, an ope a ion known
as h ead squash. In bo h cases, he scheduling un ime
sys em should assign a new block o i e a ions o he
h ead o con inue he pa allel wo k.
Scheduling i e a ions unde TLS The scheduling
me hod used wi h specula i e pa alleliza ion is di e en
om classic scheduling me hods, e.g. [14], [15], [16].
Unde TLS, he execu ion o an i e a ion o chunk o
i e a ions can be disca ded, so he scheduling me hod
should be able o e-assign he squashed i e a ion o he
same o a di e en h ead. The loop s uc u e should be
changed o allow e-execu ion o i e a ions.
3 RELATED WORK
So wa e-based TLS (STLS) p oposals Se e al wo ks
p opose specula i e pa alleliza ion mechanisms ha
bene i om di e en deg ees o code ans o ma-
ions. Tian e al. [17] p opose he use o he Copy-
o -Disca d (Co D) execu ion model o a oid expensi e
s a e- eco e ing mechanisms in case o misspecula ion.
This p oposal equi es an in-dep h analysis o he o igi-
nal loop, and he use o code ans o ma ion echniques
ha educe he p obabili y o misspecula ion. Specula-
i e loads in his p oposal always ge he non-specula i e
e sion o he da a, so successo s o he o ending h ead
a e no a ec ed by misspecula ions. In [18], a so wa e-
based TLS sys em is p oposed o help in he manual
pa alleliza ion o applica ions. The sys em equi es he
p og amme o ma k “possibly pa allel egions” (PPR)
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 4
in he applica ion o be pa allelized. The sys em elies on
a so-called “ ou namen ” model, wi h di e en h eads
coope a ing o execu e he egion specula i ely, while an
addi ional h ead uns he same code sequen ially. I a
single dependence a ises, specula ion ails en i ely and
he sequen ial execu ion esul s a e used ins ead. The
use ulness o his sys em is based on he assump ion
ha he code chosen by he p og amme will likely
no p esen any dependencies. An imp o emen o his
scheme is desc ibed in [19], elying on dependence hin s
p o ided by he p og amme o allow explici da a
communica ion be ween h eads, hus educing un ime
dependence iola ions. In [9], a model ha combines
di e en echniques such as h ead-le el specula ion,
helpe h eads and un-ahead execu ion is p oposed o
dynamically choose he mos app op ia e combina ion a
un ime. A wo k o he Co D g oup [20] aims o educe
he cos o misspecula ion, by eco ding in e media e
s a es du ing he specula i e execu ion. In his way,
ins ead o abo ing a comple e ask, only a po ion o
he ask is e-execu ed. This solu ion comes a he cos
o a mo e complex code analysis, in o de o inse
in e media e checkpoin s whe e he ea lies eads o he
specula i e a iables a e ound.
Oancea e al. de eloped SpLIP [21], an STLS app oach
cen e ed on dec easing o e heads o specula i e op-
e a ions. In his wo k, load and s o e ope a ions di-
ec ly wo k wi h he main copy o he a iables, and
dependences a e managed h ough excep ions. They
ex ac many o he ideas om so wa e T ansac ional
Memo y (STM), implemen ing non-locking ope a ions
whe e possible, and p ese ing a log o a iables and
imes amps o handle he execu ion. ATLaS’ un ime
lib a y and SpLIP a e bo h STLS implemen a ions ha
can ex ac speed-up om sequen ial applica ions wi h
complex dependences. Concep ually, he main di e ence
be ween ATLaS’ un ime lib a y and SpLIP is he way
hey manage hei ope a ions, since ATLaS manages
e sion copies, while SpLIP wo ks wi h he main e sion
o specula i e da a. ATLaS also inco po a es a compile-
ime phase ha g ea ly simpli ies he use o specula ion
o p oduc ion pu poses. To ake ad an age o SpLIP,
he use has o ew i e he en i e applica ion almos
om sc a ch, since he code o be pa allelized and he
unde lying lib a y a e ex emely highly coupled. ATLaS
compile- ime and un ime ea u es a e ma u e enough
o be used in p oduc ion en i onmen s wi h almos no
e o .
Finally, an adap i e app oach o specula i e loop
execu ion, which handles nes ed loops, has ecen ly been
p oposed [10]. Ou p oposal does handle nes ed loops
anspa en ly, in he same way s anda d OpenMP does.
TLS and So wa e T ansac ional Memo y Bo h TLS
and so wa e T ansac ional Memo y (STM) [22] a e so-
lu ions ha use specula i e echniques o imp o e he
p og ammabili y and pe o mance o p og ams. TLS has
se e al ea u es in common wi h TM, such as he use
o specula i e eads and w i es ha can be olled back.
Howe e , and despi e hei implemen a ion simila i ies,
hey sol e di e en p oblems. The goal o TM is o help
in explici pa allel p og amming by educing he cos s
o he locks equi ed o a oid ace condi ions in c i ical
sec ions [23], [24]. On he o he hand, TLS depa s om
a sequen ial p og am, b eaks i in o asks and ies o
execu e hem op imis ically in pa allel, while p ese ing
sequen ial seman ics.
The main di e ence be ween TLS and TM is ha TLS
ensu es a o al o de in he commi ope a ion, which is
always ca ied ou sequen ially om he non-specula i e
o he mos -specula i e h ead. As long as TM does
no p ese e any o de in he commi ope a ions, STM
lib a ies canno be used di ec ly o mimic he beha io
o loop-based specula i e pa alleliza ion whene e se-
quen ial seman ics should be p ese ed. Sec ion 1 o he
Supplemen al Ma e ial u he discusses his issue.
Finally, he e a e se e al in e es ing TLS-TM hyb id
app oaches. These solu ions a e e iewed in Sec . 2 o
he Supplemen al Ma e ial.
TLS ex ensions o OpenMP Ea ly wo ks, such as [25],
p opose he use o OpenMP di ec i es o enable specula-
i e pa allelism, he de ails o he implemen a ion being
anspa en o he p og amme . In a simila way, [26]
exposes he ad an ages o using OpenMP o gi e explici
hin s o he compile and he unde lying ha dwa e o
ex ac specula i e pa allelism.
O he p oposals aim o in eg a e T ansac ional Mem-
o y echnologies in o OpenMP (see [27], [28], [29], [30],
[31], [32], [33], [34], [35]). These p oposals a e e iewed
in Sec . 3 o he Supplemen al Ma e ial.
4 SEMANTICS OF OUR specula i e CLAUSE
The p oblem o adding specula i e pa alleliza ion sup-
po o OpenMP can be handled using wo app oaches.
The i s one equi es he addi ion o a new di ec i e,
such as p agma omp specula i e o . Howe e , he e a e
many OpenMP ela ed componen s ha should be mod-
i ied in o de o add a new di ec i e. A simple solu ion
is o add a new OpenMP clause o he lis o a ailable
pa allel cons uc s, which allows he p og amme o
enume a e which a iables should be handled specula-
i ely. The syn ax o his clause is:
specula i e( a iable[, a _lis ])
In his way, i he p og amme is unsu e abou he
use o a ce ain da a s uc u e, he can simply label i as
specula i e. In his case, a ailo ed OpenMP implemen-
a ion should eplace all de ini ions and uses o his da a
s uc u e wi h he co esponding specload() and spec-
s o e() unc ion calls. An addi ional commi _o _disca d()
unc ion will be au oma ically inse ed once each h ead
has inished i s chunk o i e a ions, o ei he commi he
esul s, o o es a he execu ion i he h ead has been
squashed due o a un ime dependence iola ion.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 5
Ou new TLS un ime lib a y, desc ibed in he ol-
lowing sec ion, was indeed de eloped using s anda d
OpenMP clauses. In o de o in eg a e ou lib a y in o
an expe imen al OpenMP amewo k ha includes a
new specula i e clause, wo pa icula i ies o ou TLS
lib a y should be aken in o accoun . Fi s , since ou TLS
un ime lib a y has also been de eloped using OpenMP,
some p i a e and sha ed con ol a iables should be
added o he a ge loop in o de o use i . The e o e,
i a specula i e clause is ound by he compile , his
occu ence, which implies he use o ou specula i e
lib a y, should igge he inclusion o se e al p i a e and
sha ed a iables o he exis ing lis s. As long as OpenMP
allows he epe i ion o clauses, so he compile ime
suppo o his new specula i e clause can add addi ional
p i a e and sha ed clauses ha will la e be expanded by
he compile .
Second, he s anda d scheduling me hods imple-
men ed by OpenMP a e no enough o handle spec-
ula i e pa alleliza ion. These me hods assume ha he
execu ion o a chunk o i e a ions will ne e ail, so hey
do no conside he possibili y o es a ing a chunk ha
has ailed due o a dependence iola ion. The e o e, i
is necessa y o use a specula i e scheduling me hod.
Ins ead o di iding he i e a ion space, we ha e ollowed
he solu ion adop ed in [7], eplacing he o iginal loop
s uc u e wi h a new loop composed by Ni e a ions,
Nbeing he numbe o h eads. A he beginning o
he loop, each h ead is assigned a di e en chunk o
i e a ions o be execu ed. I a h ead has success ully
inished a chunk, i will ecei e a new chunk ha has
no ye been success ully execu ed. In he case o a de-
pendence iola ion ha igge s a squash ope a ion, he
scheduling me hod will y o eassign o ha h ead he
chunk whose execu ion has ailed, in o de o imp o e
locali y and cache eu iliza ion.
5 A NEW RUNTIME LIBRARY FOR TLS
We ha e de eloped a new TLS un ime lib a y ha
suppo s he specula i e execu ion o o loops. The
lib a y a chi ec u e ollows he design p inciples o he
specula i e pa alleliza ion lib a y de eloped by Cin a
and Llanos [7], [36]. In o de o unde s and ou solu ion,
a b ie desc ip ion o ha p oposal is needed.
In [7], [36], Cin a and Llanos de eloped a un ime
lib a y ha uses a sliding window mechanism ha al-
lows he pa allel execu ion o Wconsecu i e chunks o
i e a ions. Each ime he non-specula i e h ead inishes,
a pa ial commi akes place; he h ead execu ing he ol-
lowing chunk becomes he new, non-specula i e h ead;
and he window ad ances, allowing he execu ion o
new chunks o i e a ions. Despi e i s good pe o mance
igu es, he un ime lib a y de eloped by Cin a and
Llanos su e s om se e e limi a ions. Fi s , hei lib a y
equi es all specula i e a iables o be packed in a single,
one-dimensional ec o be o e he s a o he specula i e
loop. Second, all specula i e a iables should sha e a
single da a ype. Thi d, specula i e a iables can only be
accessed by name inside he loop (no e e ences by ad-
d esses o poin e s we e allowed). Finally, his un ime
lib a y c ea es W e sion copies o he en i e specula i e
da a s uc u e, being W he size o he sliding window
being used, ins ead o jus keeping e sion copies o
he da a elemen s ac ually accessed. These limi a ions
p e en he use o his un ime lib a y o suppo a
specula i e clause, whe e a iables and da a s uc u es
labeled as specula i e may be o di e en da a ypes, can
be accessed by name o add ess, and whe e specula i e
da a s uc u es can be o any size.
Ou TLS un ime lib a y o e comes all hese limi a-
ions. I allows a iables o any da a ype o be specula-
i ely accessed, bo h by name o add ess, and managing
he space needed o e sion copies on demand. In his
sec ion, we will b ie ly show he gene al a chi ec u e o
he lib a y. A mo e de ailed desc ip ion o he design
decisions aced can be ound in [37].
5.1 Loop ans o ma ion o specula i e execu ion
Figu e 4 b ie ly shows he ans o ma ion o a pa allel
loop o specula i e execu ion. This ans o ma ion is
igge ed by ou p oposed specula i e clause, and i is
au oma ically ca ied ou by ou compile plugin. The
changes a e b ie ly desc ibed below:
•Line 1: Addi ional, in e nal a iables a e de ined.
•Line 2: Be o e he loop, he omp_se _num_ h eads()
unc ion is called o de ine he numbe o h eads
o be used.
•Line 3: Aspecbegin() unc ion is called o ini ialize
he execu ion o he ollowing pa allel loop. I i is
he i s loop being pa allelized, his unc ion also
ini ializes he un ime specula i e lib a y.
•Line 4: All a iables labeled as specula i e a e au o-
ma ically eclassi ied as sha ed. Besides his change,
all eads and s o es inside he loop body on hose
specula i e a iables (see below) a e eplaced wi h
calls o specload() and specs o e() unc ions, in o -
de o keep sequen ial consis ency, as desc ibed
in Sec . 2. Ou compile plugin also labels o he
in e nal a iables needed by he un ime sys ems
as p i a e and sha ed, such as id and h eads in ou
example.
•Line 5: The o iginal loop s uc u e is eplaced wi h
a pa allel o loop wi h jus “ h eads” i e a ions. This
launches he numbe o desi ed h eads.
•Line 6: Awhile( ue) loop ensu es ha each h ead
epea edly equi es a chunk o i e a ions om he
o iginal loop o be p ocessed. I no chunks a e le ,
ab eak s a emen exi s his loop, hus eaching he
end o he h ead (see line 12).
•Line 7: Inside he loop, each h ead ecei es he
index o he i s i e a ion o i s assigned chunk and
p oceeds wi h he o iginal loop body.
•Lines 8-10: The ead o b a iable in line 8 o
Fig. 4(a) is eplaced wi h a call o he specload()

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 6
1: cha a; loa b; 1: cha a; loa b; cha emp; loa alue, in id, h eads; ...
2: omp_ge _num_ h eads( h eads);
3: specbegin(MAX);
4: #p agma openmp pa allel o 4: #p agma openmp pa allel o
p i a e (i) specula i e (a,b) p i a e (i, id, emp, alue,...)sha ed (a,b, h eads,...)
5: o (i=0; i<MAX; i++) { 5: o ( id=0; id< h eads; id++) {
6: while( ue) {
7: i = assign_ ollowing_chunk( id, MAX,...);
O iginal loop code, pa 1 O iginal loop code, pa 1
8: a = (b); 8: specload(&b, sizeo (b),..., & alue);
9: emp = ( alue);
10: specs o e(&a, sizeo (a),..., & emp);
O iginal loop code, pa 2 O iginal loop code, pa 2
11: commi _o _disca d_da a( id,...);
12: i (no_chunks_le ( id, MAX,...)) b eak;
13: }
14: } 14: }
(a) (b)
Fig. 4. Loop ans o ma ion o allow i s specula i e execu ion: O iginal (a) and ans o med (b) code.
unc ion, which eco e s he mos up- o-da e alue
o his a iable. The exac beha io o specload() is
desc ibed la e in his sec ion. The alue is s o ed in
a p i a e, empo al loca ion. Line 8 o Fig. 4(a) also
pe o ms a w i e on a. This w i e is eplaced wi h a
call o specs o e() (line 9), which i s s o es he alue
in a local e sion copy and hen checks whe he a
successo has al eady consumed an ou da ed alue
o a. I so, he o ending h ead and some o all o
i s successo s (depending on he squash policy being
de ined [13]) a e squashed.
I is impo an o highligh ha only he lines o he
o iginal loop body ha in ol e specula i e a iables
a e changed in his way: he emaining code is le
wi h no changes.
•Line 11: Once he o iginal loop body is inished, a
call o commi _o _disca d_da a() checks whe he he
h ead has been squashed o no . I a squash op-
e a ion was issued by a p edecesso , local copies
o specula i e da a will be disca ded. I he h ead
has no been squashed and i is he no -spec one,
a pa ial commi will occu . Pa ial commi s will be
desc ibed in Sec . 5.4.
•Line 12: A e inishing hei asks ela ed o he
cu en chunk, all h eads check whe he he e a e
no pending chunks o be execu ed. I he e is no
pending wo k, h eads lea e he while loop.
When all h eads ha e exi ed he while( ue) loop, he
end o he pa allel sec ion has been eached and (despi e
he numbe o needed a emp s) all chunks o i e a ions
ha e been success ully execu ed, and hei esul s com-
mi ed o he specula i e a iables.
5.2 Da a s uc u es
The da a s uc u es needed by he new specula i e
lib a y a e depic ed in Fig. 5(a). The sliding window
mechanism is implemen ed by a ma ix wi h Wwindow
slo s ( ou in he igu e). Each slo ac s as a “sc a chpad”
used o handle he specula i e execu ion o a pa icula
chunk o i e a ions. Two global a iables, non-spec and
mos -spec, indica es he slo assigned o he execu ion
o he non-specula i e and mos -specula i e chunks o
i e a ions a each pa icula momen . These a iables a e
used as limi s o s op he sea ch o p edecesso e -
sions and he sea ch o possible dependence iola ions,
espec i ely. The STATE ield indica es he s a e o he
execu ion being ca ied ou in each slo .
The igu e ep esen s he pa allel execu ion o a loop.
The loop has been di ided in o h ee chunks o i -
e a ions, and will be execu ed in pa allel using h ee
h eads. I is e y impo an o unde s and ha he e is
no ixed associa ion be ween h eads and slo s. When-
e e a h ead is assigned a new chunk o i e a ion, i
is also assigned he co esponding slo o wo k in. This
allows an o de ela ionship o be main ained be ween
he chunks being execu ed.
In ou example, he h ead wo king in slo 1 is execu -
ing he non-specula i e chunk o i e a ions (as indica ed
by i s RUNNING s a e); he ollowing chunk has al eady
been execu ed and i s da a has been le he e o be
commi ed a e he non-spec chunk inishes (since i
is in he DONE s a e), while he las one, he mos -
specula i e chunk launched so a , is also RUNNING. In
o he wo ds, he h ead in cha ge o he second chunk
has al eady inished, while he non-spec and mos -spec
h eads a e wo king. I mo e chunks we e pending, he
eed h ead would be assigned he ollowing chunk,
s a ing i s execu ion in slo 4. Slo 2 canno be e-used
ye , because he execu ion o chunk 2 le changes o
specula i e a iables ha a e ye o be commi ed. As
we will see in Sec . 5.4, when he non-specula i e h ead
wo king in slo 1 inishes, i will commi i s esul s and
he esul s s o ed in all subsequen DONE slo s, since
commi s should be ca ied ou in o de . A e ha , in
ou example, he non-spec poin e will be ad anced o
slo 3 o e lec he new si ua ion.
In addi ion o i s STATE, each slo poin s o a da a
s uc u e ha holds he e sion copies o he da a being
specula i ely accessed. Figu e 5(a) ep esen s a si ua ion
whe e he p og amme decla ed h ee a iables wi hin
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 7
1
Non−spec window slo
3
Mos −spec window slo
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
18.997
b1
9
a1
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
7
a3 b3
25.8
&a 1 EXPLD
MOD&b 4 &b3
&a3
18.997
b2 c2
128.215 7
a2
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
8&c ELUP&c2
&b 4 EXPLD&b2
&a 1 &a2 MOD
Running Done Running F eeSTATE
Poin e o e sion copy
Sliding window
loa bcha a
double c
9 23.4
32.88
specula i e
a iables
Use −labeled
&a
&b &b1 MOD
EXPLD&a11
4
Ve sion copy da a s uc u es
Slo 1 Slo 2 Slo 3 Slo 4
Exp. Loaded and Upda ed
(ELUP)
Exposed Loaded
(EXPLD)
No Accessed
Modi ied
(MOD)
s o e
load
s o e
Spec.
Spec.
Spec.
Spec. load / spec. s o e
Spec. load
Spec. load / spec. s o e
(a) (b)
Fig. 5. Da a s uc u es o ou new specula i e lib a y (a) and s a e ansi ion diag am o specula i e da a (b).
ou specula i e clause. A a gi en momen , he h ead
execu ing he non-specula i e chunk has specula i ely
accessed a iables aand b. Each ow o he e sion copy
da a s uc u e keeps he in o ma ion needed o manage
he access o a di e en specula i e a iable. The i s
column indica es he add ess o he o iginal a iable,
known as he e e ence copy. The second one indica es he
da a size. No e ha , al hough en i e da a s uc u es may
be labeled as specula i e, specula i e eads and w i es
a e always ca ied ou o e scala a iables. The e o e,
he maximum size o he da a being specula i ely ac-
cessed will be he size o he bigges scala a iable
in he a chi ec u e conside ed. This alue is 8 by es
in 64-bi a chi ec u es. The hi d column indica es he
add ess o he local copy o his a iable associa ed o
his window slo . Finally, he ou h column indica es
he s a e associa ed o his local copy. Once accessed by
a h ead, he e sion copies o he specula i e da a can
be in h ee di e en s a es: Exposed Loaded, indica ing ha
he h ead has o wa ded i s alue om a p edecesso o
om he main copy; Modi ied, indica ing ha he h ead
has w i en o ha a iable wi hou ha ing consumed i s
o iginal alue; and Exposed Loaded and Upda ed, whe e a
h ead has i s o wa ded he alue o a a iable and
has la e modi ied i . The ansi ion diag am o hese
s a es is shown in Fig. 5(b).
Figu e 5(a) ep esen s a si ua ion whe e he h ead
wo king in slo 1 has pe o med a specula i e load
om a iable a(ob aining i s alue om he e e ence
copy) and a specula i e s o e o a iable b. Rega ding
a, he igu e shows ha he h ead wo king in slo s 3
has o wa ded i s alue. Wi h espec o a iable b, he
in o ma ion in he igu e shows ha bwas o e w i en
by bo h h eads wo king in slo s 1 and 3.
5.3 Specula i e loads and s o es
The in e ace o ou implemen a ion o specload() is as
ollows:
specload(VOID* add , UINT size, UINT chunk_numbe , VOID*
alue)
The i s pa ame e is he add ess o he specula i e
a iable; he second one is he size o he a iable; he
hi d one is he numbe o he chunk being execu ed
(needed o in e he slo being used); and he ou h one
is a poin e o a place o s o e he da um eques ed.
Recall ha specload() should e u n he mos up- o-
da e alue a ailable o he specula i e a iable. Figu e 6
shows how he specula i e load wo ks. Suppose ha he
h ead wo king in slo 2 has only accessed o a iable c
so a , and i hen calls specload(&b, sizeo (b), 2, & alue)
o ob ain a alue o b. The sequence o e en s is he
ollowing:
1) The h ead wo king in slo 2 scans i s e sion copy
da a s uc u e o check whe he a alue o bhas
been al eady s o ed he e. As long as he only
specula i e a iable accessed so a is c, his sea ch
p oduces no esul s.
2) Ou h ead goes o i s p edecesso e sion copy
da a s uc u e and scans i in o de o ind a alue
o b. I s p edecesso has s o ed a alue o i , so
ou h ead copies i s alue o a new loca ion. No e
ha , i no alue o bwe e ound he e, ou h ead
would go o he nex p edecesso , un il he non-
specula i e h ead is ound. I no p edecesso had
used he alue, ou h ead would ge he alue
om he e e ence copy.
3) A e s o ing a copy o b’s alue, he h ead wo k-
ing in slo 2 adds a new ow o i s e sion copy da a
s uc u e, s o ing he add ess o b, i s da a size, he
add ess o he e sion copy o bbeing managed by
he h ead, and he new s a e o his e sion copy,
EXPLD. The call o specload() inishes by e u ning
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 8
2
1E
F
A
B
D
G
C3
1
Non−spec window slo
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
18.997
b1
9
a1
9
a3 b3
25.8
18.997
b2 c2
128.215 7
a2
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
Slo 1 Slo 2 Slo 3 Slo 4
RunningSTATE
Poin e o e sion copy
Sliding window
loa bcha a
double c
9 23.4
32.88
specula i e
a iables
Use −labeled
&a
&b &b1 MOD
EXPLD&a11
4 &a 1 EXPLD
MOD&b 4 &b3
&a3
8&c ELUP&c2
&b 4 EXPLD&b2
Running
Ve sion copy da a s uc u es
&a 1 &a2 MOD
F eeRunning
SQUASHED
Mos −spec window slo
23
Fig. 6. S eps o a specula i e load (1..3) and specula i e s o e (A..F).
he alue 18.997 in he add ess indica ed by i s
ou h pa ame e .
The in e ace o specs o e() is he same as specload(), bu
in his case he las pa ame e is a poin e o he alue
o be s o ed. Recall ha specs o e() should no only s o e
he new alue, bu also check whe he a successo has
consumed an ou da ed alue o i .
Figu e 6 shows he sequence o e en s ela ed o a
specula i e s o e. Suppose ha he h ead wo king in
slo 2 execu es specs o e(&a, sizeo (a), 2, & emp), whe e
emp holds he alue 7. The sequence o e en s is he
ollowing:
A) The h ead wo king in slo 2 sea ches o a local
e sion copy o a. A his momen , only copies o c
and ba e s o ed in i s e sion copy da a s uc u e,
so he sea ch p oduces no esul s. I awe e ound,
his h ead would upda e i s s a us acco ding o he
s a e diag am o Fig. 5(b), and i would p oceed o
s ep D.
B) The h ead wo king in slo 2 c ea es a local copy
o a, s o ing alue 7 on i .
C) A new ow is added o he e sion copy da a
s uc u e, wi h a poin e o a, i s size, he poin e
o he local copy and he s a us, which, in his case,
will be MOD (see Fig. 5(b)).
D) A e s o ing he alue locally, he h ead wo king
in slo 2 should check whe he any successo has
consumed an ou da ed alue. To do so, ou h ead
would scan (in inc easing o de o specula i eness)
o any successo slo ha holds a copy o ain
he EXPLD o ELUP s a es. These s a es would
indica e ha he successo has used he alue. In
ou example, he sea ch inds ou ha he h ead
wo king in Slo 3 has consumed an inco ec alue
o a. I no dependence iola ion was de ec ed, he
call o specs o e() would inish he e.
E) A dependence iola ion has been de ec ed. Th ead
wo king in slo 3 should be squashed. To do so, he
h ead wo king in slo 2 changes he s a e o slo 3
om Running o Squashed. Since all h eads check
hei own s a e a he beginning o each specload(),
specs o e(), and a he end o he execu ion o
each chunk o i e a ions, h ead wo king in slo 3
will e en ually disco e ha i has been squashed,
and will execu e a call o commi _o _disca d() o be
assigned a new chunk (possibly he same) and s a
he p ocess again.
F) Finally, he h ead wo king in slo 2 ma ks i sel
as he mos -specula i e h ead, since da a s o ed in
associa ion wi h slo 3 is no longe alid. The mos -
spec poin e will be ad anced la e by he h ead
ha ecei es he ask o e-execu ing chunk 3.
I , a e hese e en s, he h ead wo king in slo 2
inishes i s execu ion, while he h eads associa ed o
slo s 1 and 3 a e s ill wo king, we each he si ua ion
shown in Fig. 5(a). No e ha , a ha poin , he h ead
wo king in slo 3 has al eady been e-s a ed and i has
o wa ded he mos up- o-da e alue o a( ha is, 7)
om slo 2.
5.4 Pa ial commi ope a ion
The pa ial commi ope a ion is exclusi ely ca ied ou
by he non-specula i e h ead. E e y ime a h ead exe-
cu es commi _o _disca d(), i i s checks i i has no been
squashed and i i is he non-specula i e one. I he
h ead is specula i e, he slo is le o be commi ed by
he non-spec h ead.
Suppose ha we a e in he si ua ion depic ed in
Fig. 5(a), and he non-spec h ead wo king in slo 1
inishes. As long as i is he non-spec one, i will scan i s
da a s uc u e o a iables in he ELUP o MOD s a es.
In ou example, bhas been modi ied, so i copies he
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, YEAR MONTH 9
con en o b1 in o b. A e commi ing he e sion copy
da a s uc u e associa ed o slo 1, i changes i s s a e o
FREE and ad ances he non-spec poin e o 2. As long as
slo 2 is ma ked as DONE, i s da a should be commi ed
as well. In ou example, da a s o ed in c2 and a2 should
be commi ed o he use -de ined a iables. A e his,
he s a e o he slo is also changed o FREE and he non-
spec poin e is ad anced as well. The h ead wo king in
slo 3 is s ill unning: When i inishes, i will be in cha ge
o commi ing i s own da a. These commi ope a ions a e
ca ied ou wi h he help o auxilia y da a s uc u es ha
s o e a lis o elemen s in he ELUP o MOD s a es (no
shown in ou examples), in o de o a oid a e sing he
local copies en i ely only o commi ew da a elemen s.
I is in e es ing o no e ha each h ead only w i es
on i s local e sion copy da a s uc u e, so no c i ical
sec ions a e needed o p o ec hem. The only c i ical
sec ion used p o ec s he sliding window da a s uc u e,
o a oid ha a h ead o e w i es ano he h ead’s s a e.
5.5 Pe o mance hu dles
One o he main ad an ages o ou new specula i e
pa alleliza ion lib a y is ha each h ead only alloca es
he memo y needed o s o e local copies o he spec-
ula i e da a ac ually being accessed (see s ep (3) o he
specula i e load ope a ion and s ep (B) o he specula i e
s o e, abo e). In con as , Cin a e al.’s solu ion keeps T
copies o he en i e lis o specula i e a iables. As will
be seen in Sec . 7.2, he numbe o po en ially-specula i e
a iables can be huge, so Cin a e al.’s solu ion se e ely
limi s scalabili y.
Ou imp o emen in e ms o memo y oo p in
comes a he cos o longe imes o ind he mos -up-
o-da e alue in specula i e loads, and longe imes o
de ec dependence iola ions in specula i e s o es, since
bo h ope a ions should a e se all he alues accessed
by all he p edecesso s and successo s, espec i ely. T
being he numbe o h eads, in [7], he ime complexi y
o his ope a ion was in T×O(1) = O(T), since all he
memo y needed o any da a ha migh be accessed was
alloca ed in ad ance. In ou scheme, Nbeing he numbe
o da a elemen s s o ed locally, he sea ch is done in
T×O(N) = O(T N). The e o e, he pe o mance igu es
o ou lib a y wi h his mechanism a e somewha lowe
han he ones desc ibed in [7].
One way o speed up hese sea ches is o swi ch o
a di e en da a s uc u e o hold local e sion copies
o da a. Ins ead o using a single able pe h ead as
e sion copy da a s uc u e, we ha e de eloped an
al e na i e s uc u e wi h X ables, de ined by he p o-
g amme (see [38] o mo e de ails). Be o e accessing
he da a, a module ope a ion on he add ess o he use -
de ined specula i e a iable ob ains a hash H, in he
ange 0. . . (X−1). This hash is used o look in o he
H h ables o all p edecesso s and successo s, e ec i ely
speeding up he sea ch by an a e age ac o o Hwi h-
ou inc easing he ime needed o add a new ow o he
co esponding able, leading o O(T.N
H)sea ch imes. We
a e also e alua ing o he solu ions, such as dicho omic
sea ch, which can be used o each sea ch alues in
O(T. log(N)), bu i comes a he cos o spending mo e
ime inding he place o s o e he da a locally.
6 COMPILER SUPPORT FOR THE specula i e
CLAUSE
The compile phase o ou sys em is implemen ed on he
GCC C compile [39], ex ending i s unc ionali y h ough
a plugin. Be o e desc ibing he implemen a ion o he
plugin, i is necessa y o in oduce he GCC a chi ec u e.
GCC a chi ec u e in a nu shell Figu e 7 shows he
scheme o he GCC a chi ec u e [40], [41]. In basic
e ms, GCC is a big pipeline ha con e s one p o-
g am ep esen a ion in o ano he , in di e en s ages.
Each s age gene a es a lowe -le el ep esen a ion, un il
he assembly code is gene a ed a he las s age. GCC
a chi ec u e has h ee clea ly-de ined blocks: F on End,
Middle End and Back End. The e is one on end o each
p og amming language. The pa se o each language
con e s sou ce iles in o a uni ied ee o m, called
GENERIC, which is a high-le el ee ep esen a ion.
When i inishes, he F on End emi s a GENERIC in-
e media e ep esen a ion (IR) o he code, which se es
as he in e ace be ween he on end and he es o he
compile .
The Middle End wo ks on GIMPLE, which is a 3-
add ess language wi h no high-le el con ol low s uc-
u es. In GIMPLE, each s a emen does no con ain mo e
han h ee ope ands (excep unc ion calls); con ol low
s uc u es a e combina ions o condi ional s a emen s
and go o ope a o s; and he e is a single scope o a i-
ables. This kind o ep esen a ion is con enien o op i-
mize he sou ce code. Once he sou ce code is in GIMPLE
o m, an in e p ocedu al op imize is called, whe e inlining
ope a ions, cons an p opaga ion, o s a ic a iable analysis
a e pe o med. We ha e inse ed ou plugin a his poin .
The ollowing s ep is he ans o ma ion om GIMPLE
in o SSA (S a ic Single Assignmen ) ep esen a ion. In
SSA o m, each a iable is assigned o w i en only
once, c ea ing new e sions o each assignmen o he
same a iable, which can be ead many imes. When
di e en e sions o he same a iable a e w i en in o
bo h b anches o a condi ional exp ession, a φ- unc ion
is added jus a e he condi ional block, allowing he
selec ion o he co ec e sion o he a iable, depending
on he b anch execu ed. SSA ep esen a ion is used o
se e al op imiza ions, such as o wa d exp ession subs i-
u ion, loop in e change, ec o iza ion o pa alleliza ion,
among o he s. These op imiza ions a e pe o med in
a ound 100 passes.
A e hese op imiza ions, he SSA ep esen a ion is
con e ed back o he GIMPLE o m, which is ans-
o med in o a egis e - ans e language (RTL) o m, in
which he Back End wo ks on. RTL was he o iginal
p ima y in e media e ep esen a ion used by GCC. I is a