LLVM el perspektivo de Go

Disvolvi kompililon estas tre malfacila tasko. Sed, feliĉe, kun la disvolviĝo de projektoj kiel LLVM, la solvo de ĉi tiu problemo estas tre simpligita, kio ebligas eĉ al ununura programisto krei novan lingvon, kiu proksimiĝas je rendimento al C. Labori kun LLVM estas komplikita pro tio, ke ĉi tiu sistemo estas reprezentita per grandega kvanto da kodo, ekipita per malmulte da dokumentado. Por provi korekti ĉi tiun mankon, la aŭtoro de la materialo, kies tradukon ni publikigas hodiaŭ, montros ekzemplojn de kodo skribita en Go kaj montros kiel ili unue estas tradukitaj en Iru SSA, kaj poste en LLVM IR uzante la kompililon tinyGO. La Go SSA kaj LLVM IR-kodo estis iomete redaktita por forigi aferojn, kiuj ne rilatas al la klarigoj ĉi tie donitaj, por igi la klarigojn pli kompreneblaj.

Unua ekzemplo

La unua funkcio, kiun mi rigardos ĉi tie, estas simpla mekanismo por aldoni nombrojn:

func myAdd(a, b int) int{
    return a + b
}

Ĉi tiu funkcio estas tre simpla, kaj, eble, nenio povus esti pli simpla. Ĝi tradukiĝas en la sekvan Go SSA-kodon:

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

Kun ĉi tiu vido, la datumtipaj sugestoj estas metitaj dekstren kaj povas esti ignoritaj en la plej multaj kazoj.

Ĉi tiu malgranda ekzemplo jam permesas al vi vidi la esencon de unu aspekto de SSA. Nome, kiam oni konvertas kodon en SSA-formon, ĉiu esprimo estas dividita en la plej elementajn partojn, el kiuj ĝi estas kunmetita. En nia kazo, la komando return a + b, fakte, reprezentas du operaciojn: aldonante du nombrojn kaj redonante la rezulton.

Krome, ĉi tie vi povas vidi la bazajn blokojn de la programo; en ĉi tiu kodo estas nur unu bloko - la enira bloko. Ni parolos pli pri blokoj sube.

La Go SSA-kodo facile konvertiĝas al LLVM IR:

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

Kion vi povas rimarki estas ke kvankam malsamaj sintaksaj strukturoj estas uzataj ĉi tie, la strukturo de la funkcio estas esence senŝanĝa. La LLVM IR-kodo estas iom pli forta ol la Go SSA-kodo, simila al C. Ĉi tie, en la funkciodeklaro, unue estas priskribo de la datumtipo, kiun ĝi resendas, la argumenttipo estas indikita antaŭ la argumentnomo. Krome, por simpligi IR-analizadon, la nomoj de tutmondaj entoj estas antaŭitaj per la simbolo @, kaj antaŭ lokaj nomoj estas simbolo % (funkcio ankaŭ estas konsiderata kiel tutmonda ento).

Unu afero rimarkinda pri ĉi tiu kodo estas, ke la decido pri tipo reprezentado de Go int, kiu povas esti reprezentita kiel 32-bita aŭ 64-bita valoro, depende de la kompililo kaj la celo de la kompilo, estas akceptita kiam LLVM generas la IR-kodon. Ĉi tio estas unu el la multaj kialoj, ke LLVM IR-kodo ne estas, kiel multaj homoj pensas, platformo sendependa. Tia kodo, kreita por unu platformo, ne povas simple esti prenita kaj kompilita por alia platformo (krom se vi taŭgas por solvi ĉi tiun problemon. kun ekstrema singardemo).

Alia interesa punkto rimarkinda estas ke la tipo i64 ne estas signita entjero: ĝi estas neŭtrala laŭ reprezentado de la signo de la nombro. Depende de la instrukcio, ĝi povas reprezenti kaj signitajn kaj nesignitajn nombrojn. En la kazo de la reprezentado de la aldonoperacio, tio ne gravas, do ne estas diferenco en labori kun signitaj aŭ sensignaj nombroj. Ĉi tie mi ŝatus noti, ke en la C-lingvo, superfluo de signita entjera variablo kondukas al nedifinita konduto, do la Clang-interfado aldonas flagon al la operacio. nsw (neniu subskribita envolvaĵo), kiu rakontas al LLVM ke ĝi povas supozi ke aldono neniam superfluas.

Ĉi tio povas esti grava por iuj optimumigoj. Ekzemple, aldonante du valorojn i16 sur 32-bita platformo (kun 32-bitaj registroj) postulas, post aldono, signo-vastigoperacio por resti en intervalo i16. Pro tio, estas ofte pli efika fari entjerajn operaciojn bazitajn sur maŝinregistraj grandecoj.

Kio okazas poste kun ĉi tiu IR-kodo ne estas precipe interesa por ni nun. La kodo estas optimumigita (sed en la kazo de simpla ekzemplo kiel la nia, nenio estas optimumigita) kaj poste konvertita en maŝinkodon.

Dua ekzemplo

La sekva ekzemplo, kiun ni rigardos, estos iom pli komplika. Nome, ni parolas pri funkcio kiu sumigas tranĉaĵon de entjeroj:

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

Ĉi tiu kodo konvertas al la sekva Go SSA-kodo:

func sum(numbers []int) int:
entry:
    jump for.loop
for.loop:
    t0 = phi [entry: 0:int, for.body: t6] #n                       int
    t1 = phi [entry: 0:int, for.body: t7] #i                       int
    t2 = len(numbers)                                              int
    t3 = t1 < t2                                                  bool
    if t3 goto for.body else for.done
for.body:
    t4 = &numbers[t1]                                             *int
    t5 = *t4                                                       int
    t6 = t0 + t5                                                   int
    t7 = t1 + 1:int                                                int
    jump for.loop
for.done:
    return t0

Ĉi tie vi jam povas vidi pli da konstruoj tipaj por reprezenti kodon en la SSA-formo. Eble la plej evidenta trajto de ĉi tiu kodo estas la fakto, ke ne ekzistas strukturitaj flukontrolaj komandoj. Por kontroli la fluon de kalkuloj, ekzistas nur kondiĉaj kaj senkondiĉaj saltoj, kaj, se ni konsideras ĉi tiun komandon kiel komandon por kontroli la fluon, revenan komandon.

Fakte, ĉi tie vi povas atenti la fakton, ke la programo ne estas dividita en blokojn uzante buklajn krampojn (kiel en la C-familio de lingvoj). Ĝi estas dividita per etikedoj, rememorigaj pri asemblaj lingvoj, kaj prezentita en formo de bazaj blokoj. En SSA, bazaj blokoj estas difinitaj kiel apudaj sekvencoj de kodo komencanta kun etikedo kaj finiĝantaj kun bazaj blokkompletigaj instrukcioj, kiel ekzemple − return и jump.

Alia interesa detalo de ĉi tiu kodo estas reprezentita per la instrukcio phi. La instrukcioj estas sufiĉe nekutimaj kaj povas preni iom da tempo por kompreni. memori tion S.S.A. estas mallonga por Static Single Assignment. Ĉi tio estas meza reprezento de la kodo uzata de kompililoj, en kiu ĉiu variablo ricevas valoron nur unufoje. Ĉi tio estas bonega por esprimi simplajn funkciojn kiel nia funkcio myAddmontrita supre, sed ne taŭgas por pli kompleksaj funkcioj kiel la funkcio diskutita en ĉi tiu sekcio sum. Aparte, variabloj ŝanĝiĝas dum la ekzekuto de la buklo i и n.

SSA preterpasas la limigon pri asignado de variaj valoroj unufoje uzante tiel nomatan instrukcion phi (ĝia nomo estas prenita el la greka alfabeto). Fakte, por ke la SSA-reprezento de kodo estu generita por lingvoj kiel C, vi devas uzi iujn lertaĵojn. La rezulto de vokado de ĉi tiu instrukcio estas la nuna valoro de la variablo (i aŭ n), kaj listo de bazaj blokoj estas uzata kiel ĝiaj parametroj. Ekzemple, konsideru ĉi tiun instrukcion:

t0 = phi [entry: 0:int, for.body: t6] #n

Ĝia signifo estas jena: se la antaŭa baza bloko estis bloko entry (enigo), do t0 estas konstanto 0, kaj se la antaŭa baza bloko estis for.body, tiam vi devas preni la valoron t6 de ĉi tiu bloko. Ĉi tio povas ĉio ŝajni sufiĉe mistera, sed ĉi tiu mekanismo estas kio igas la SSA funkcii. El homa perspektivo, ĉio ĉi faras la kodon malfacile komprenebla, sed la fakto, ke ĉiu valoro estas atribuita nur unufoje, multe plifaciligas multajn optimumojn.

Notu, ke se vi skribas vian propran kompililon, vi kutime ne devos trakti ĉi tiun specon de aferoj. Eĉ Clang ne generas ĉiujn ĉi tiujn instrukciojn phi, ĝi uzas mekanismon alloca (ĝi similas labori kun ordinaraj lokaj variabloj). Tiam, kiam vi ruliĝas LLVM-optimumiga enirpermesilo nomita mem2reg, instrukcioj alloca konvertita al SSA formo. TinyGo tamen ricevas enigaĵon de Go SSA, kiu, oportune, jam estas konvertita al SSA-formo.

Alia novigo de la fragmento de meza kodo konsiderata estas ke aliro al tranĉaĵelementoj per indekso estas reprezentita en la formo de operacio de kalkulado de la adreso kaj operacio de dereferencigado de la rezulta montrilo. Ĉi tie vi povas vidi la rektan aldonon de konstantoj al la IR-kodo (ekzemple - 1:int). En la ekzemplo kun la funkcio myAdd ĉi tio ne estis uzata. Nun kiam ni forigis tiujn funkciojn, ni rigardu, kio fariĝas ĉi tiu kodo kiam ĝi estas konvertita al LLVM IR-formo:

define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
  br label %for.loop

for.loop:                                         ; preds = %for.body, %entry
  %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
  %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
  %2 = icmp slt i64 %1, %len
  br i1 %2, label %for.body, label %for.done

for.body:                                         ; preds = %for.loop
  %3 = getelementptr i64, i64* %ptr, i64 %1
  %4 = load i64, i64* %3
  %5 = add i64 %0, %4
  %6 = add i64 %1, 1
  br label %for.loop

for.done:                                         ; preds = %for.loop
  ret i64 %0
}

Ĉi tie, kiel antaŭe, ni povas vidi la saman strukturon, kiu inkluzivas aliajn sintaksajn strukturojn. Ekzemple, en vokoj phi valoroj kaj etikedoj interŝanĝitaj. Tamen, estas io ĉi tie, al kiu indas atenti speciale.

Komence, ĉi tie vi povas vidi tute malsaman funkciofirmaon. LLVM ne subtenas tranĉaĵojn, kaj kiel rezulto, kiel optimumigo, la TinyGo-kompililo, kiu generis ĉi tiun mezan kodon, dividis la priskribon de ĉi tiu datumstrukturo en partojn. Ĝi povus reprezenti tri tranĉaĵelementojn (ptr, len и cap) kiel strukturo (strukturo), sed reprezenti ilin kiel tri apartajn unuojn permesas kelkajn optimumigojn. Aliaj kompililoj povas reprezenti la tranĉaĵon alimaniere, depende de la vokaj konvencioj de la funkcioj de la celplatformo.

Alia interesa trajto de ĉi tiu kodo estas la uzo de la instrukcio getelementptr (ofte mallongigita kiel GEP).

Ĉi tiu instrukcio funkcias kun montriloj kaj estas uzata por akiri montrilon al tranĉaĵo. Ekzemple, ni komparu ĝin kun la sekva kodo skribita en C:

int* sliceptr(int *ptr, int index) {
    return &ptr[index];
}

Aŭ kun la sekva ekvivalento al ĉi tio:

int* sliceptr(int *ptr, int index) {
    return ptr + index;
}

La plej grava afero ĉi tie estas ke la instrukcioj getelementptr ne faras dereferencajn operaciojn. Ĝi nur kalkulas novan montrilon bazitan sur la ekzistanta. Ĝi povas esti prenita kiel instrukcioj mul и add ĉe la aparatara nivelo. Vi povas legi pli pri la instrukcioj de GEP tie.

Alia interesa trajto de ĉi tiu meza kodo estas la uzo de la instrukcio icmp. Ĉi tio estas ĝeneraluzebla instrukcio uzata por efektivigi entjerajn komparojn. La rezulto de ĉi tiu instrukcio ĉiam estas valoro de tipo i1 — logika valoro. En ĉi tiu kazo, komparo estas farita per la ŝlosilvorto slt (subskribita malpli ol), ĉar ni komparas du nombrojn antaŭe reprezentitajn per la tipo int. Se ni komparus du sensignajn entjerojn, tiam ni uzus icmp, kaj la ŝlosilvorto uzata en la komparo estus ult. Por kompari glitkomajn nombrojn, alia instrukcio estas uzata, fcmp, kiu funkcias en simila maniero.

Rezultoj

Mi kredas, ke en ĉi tiu materialo mi kovris la plej gravajn trajtojn de LLVM IR. Kompreneble, estas multe pli ĉi tie. Aparte, la meza reprezentado de la kodo povas enhavi multajn komentadojn kiuj permesas al optimumigo-enirpermesiloj enkalkuli certajn trajtojn de la kodo konataj al la kompililo kiuj ne povas alie esti esprimitaj en IR. Ekzemple, ĉi tio estas flago inbounds GEP-instrukcioj, aŭ flagoj nsw и nuw, kiu povas esti aldonita al la instrukcioj add. La sama validas por la ŝlosilvorto private, indikante al la optimumiganto ke la funkcio kiun ĝi markas ne estos referencita de ekster la nuna kompilunuo. Ĉi tio permesas multajn interesajn interprocedurajn optimumojn kiel forigi neuzatajn argumentojn.

Vi povas legi pli pri LLVM en dokumentado, kiun vi aludos ofte dum disvolvado de via propra LLVM-bazita kompililo. Jen gvidado, kiu rigardas evoluigi kompililon por tre simpla lingvo. Ambaŭ ĉi tiuj fontoj de informoj estos utilaj al vi kiam vi kreos vian propran kompililon.

Karaj legantoj! Ĉu vi uzas LLVM?

fonto: www.habr.com