TIES448 Luento 11

LLVM

• 'Industrial Strength' välikieli
  • Muistinsisäinen IR
  • Tekstuaalinen IR (.ll)
  • Tavukoodi (.bc)
• Ja se käyttöön tarvittavat työkalut
  • Optimoiva kääntäjä
  • Analysaattoreita
  • ... Laajennettavissa itse

LLVM-IR

; ModuleID = 'HW.c'
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [14 x i8] c"Hello world!\0A\00", align 1

; Function Attrs: nounwind uwtable
define i32 @main(i32 %argc, i8** %argv) #0 {
  %1 = alloca i32, align 4
  %2 = alloca i8**, align 8
  store i32 %argc, i32* %1, align 4
  store i8** %argv, i8*** %2, align 8
  %3 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...) #1

attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final)"}

LLVM-IR

• Verrattain täysverinen ohjelmointikieli:
  • Erikokoiset kokonaisluvut (i1, i8, i32) ja liukuluvut (float,double)
  • 'funktiot(i32 (i32,i32)*`)
  • Osoittimet (i8*)
  • Vektorit (<8 x float>) ja taulukot ([12 x [10 x i8]]])
  • Structit ({i32,float,i32 (i32)*})
  • 'labelit' (beginFor)
  • Käskyjä keskimääräistä kieltä runsaammin
  • Kevyt tyyppijärjestelmä

LLVM-IR

• Static Single Assignment (SSA): Muuttujaan voi sijoitaa vain kerran:

forStart:
  ...
  br label %forBody
forBody:
  %i = phi i32 [0, %forStart], [%i2, %forCheck]
  ...
  br label %forCheck
forCheck:
  %i2 = add   i32 %i, 1
  %10 = icmp ult i32 %i2, %3
  br i1 %10, label %forBody, label %forStop
forStop:
  ret i32 ...

• Muistiin voi toki kirjoittaa

LLVM-IR

• Mystinen getelementptr
• Laskee asioiden paikan muistissa. Ei koske muistiin. (load/store koskee)
• Ottaa tyypin, osoittimen ja indeksejä.
• Kukin indeksi kertoo, kuinka monta 'osoitusta' edetään.
• Esim. 1,0,1 => 'taulukon toinen osoitin, sen päässä oleva otus ja siitä eka kenttä.

LLVM-IR

• Yleensä IR generoidaan rakentamalla muistinsisäinen esitys ja serialisoimalla se
• Merkkijonojen tuottamisen sijaan kutsutaan LLVM-kirjastoja (IRBuilder)
  • Hoitavat kirjanpitoa, kuten tyyppejä, nimeämistä yms.
    
  • Rajapinnat eri kielillä eri (Haskell-poppoo teki mm. oman muistinsisäisen IR:n, kun c++ oli tiellä siinä kohtaa)

• Yksinkertaisissa tapauksissa '.ll' tiedoston generointi merkkijonona on 'iha ok'
  • Kaikki kirjanpito käsityötä
  • Mutta välttää sen, että kirjasto generoikin jotain muuta kuin olettaisi

Vinkki!

• Jos et tiedä miten joku asia tehdään:
  • Tee se c:llä ja clang -S -emit-llvm foo.c

LLVM-IR

Con

• Ts. Jos teet LLVM:ää, joudut opettelemaan uuden ohjelmointikielen
• Jokaista komentoa ei tarvitse tietää, mutta silti verrattain työläs taakka

Pro

• Toisaalta, esimerkiksi naiivikin minipascal llvm:n kautta käännettynä tuottaa suunnilleen yhtä nopeaa koodia kuin Java tai C# (tai c)
• Iso kasa työkaluja! (testaukseen, visualisointiin, analyyseihin, optimointeihin)

Esim. kutsuvuograafi

Esim. dominanssigraafi

LLVM takapää

• Katsotaan miltä minipascal näyttäisi llvm:llä tehtynä
• Isäntäkieli Haskell, koska Ville syö omaa koiranruokaansa.

LLVM IR komennot, joita käytämme:

• Kokonaislukuaritmetiikka
  • add (ja mul, div jne.)
  • icmp -- kokonaislukuvertailut
• Aliohjelma-lokaali muisti
  • alloca -- Varaa muistia pinosta
  • store -- Tallettaa asioita muistiin
  • load -- Lataa muistista muuttujaan
  • getelementptr -- Laskee osoitteita

LLVM IR komennot, joita käytämme:

• LLVM struktit
  • insertvalue -- Sijoittaa struktiin (ja luo strukteja undef:stä)
  • extractvalue -- Ottaa kentän struktista
• Kontrollirakenteet
  • br -- Hyppää toiseen peruslohkoon
  • phi -- Yhdistää muuttujat
  • ret -- Palaa aliohjelmasta
  • call -- Kutsuu aliohjelmaa

Tavoite

• Tein minipascal takapään, jossa on kaikki rakenteet, mutta vain tyypit INTEGER ja SEQUENCE OF INTEGER
• ... 275 riviä, osin haastavaa, koodia.
• Pahimmat haasteet:
  • LLVM-dominojen asettelu jonoon, jossa lopputulos on .o tiedosto.
    
  • SEQUENCE OF INTEGER argumenttien lukeminen.
  • "Mitä tyyppiä tämä on?"

Tavoite

• Nyt:
  • Toteutetaan jokunen valittu pala, sieltä täältä
  • Silmäillään loput läpi.

Yleiskuva

• MiniPascal käännetään ccc aliohjelmaksi ja ohjelman parametrit on sen parametreja
• Sitten generoidaan main, joka lukee argumentit komentoriviltä
• Argumenttien lukemisprimitiivit on toteutettu omalla RTS.c C - kirjastolla. (Hyvä tapa!)
• Varsinainen käännös on suoraviivainen, syntaksiohjautuva, käännös
  • RESULT ja ohjelman paremetrit pidetään LLVM muuttujassa
  • Muuttujat laitetaan esimerkin vuoksi muistiin (ja koska se on helpompaa)
  • Pieni syntaksitaulu muuttujista, joka kertoo miten ne saadaan ladattua ja mikä niistä on SEQUENCE ja mikä ei