GCC'de Derleyici Optimizasyonları

Merhaba. Bu yazıda düşük seviye bir konuyu ele alacağımı önceden yazmıştım. Yalnız ilkin takip ettiğim iki blog/vlog'dan bahsedeceğim. Biri C++ ile kendi işletim sistemini yazan adam. Web adresi http://www.wyoos.org. Videolarında bütün kodlama adımlarını anlatıyor. Geçen ay bunu takip etmek epey zamanını aldı. İkincisi de Ben Eater, Youtube kanalında 8-bit bilgisayarını tasarlayıp breadboard üzerinde uygulamasını anlatıyor. Bunu istememe rağmen önceki tutorial gibi adım adım takip edemedim. Maalesef zamanım yok. Geçen ay bir de RH442 Performance Tuning eğitimini takip ettiğim için yeni bir yazıya ancak zaman bulabildim.

Ben Eater'ın videoları arasında, kendi bilgisayarında çalıştırmak için assembly'e çevirdiği bir Fibonacci sayısı hesaplama kodu var. Videosunda kodu assembly çıktısıyla karşılaştırıyor ve sonraki videoda bunu kendi bilgisayarında programlayıp çalıştırıyor. Kod oldukça basit:

#include<stdio.h>

int main(void)  {
    int x,y,z;

    while(1)        {
        x = 0;
        y = 1;
        do      {
            printf("%d\n", x);

            z = x + y;
            x = y;
            y = z;
        } while (x < 255);
    }
}

Videoyu izlerken aklıma, bu kodu farklı GCC optimizasyon seviyeleriyle derleyip çıktılarını incelemek geldi.  

Optimizasyon (enilyileme) Seviyeleri Nedir?

Derleyiciler, kaynak kodda olmadığı halde derlendiğinde işlemcide daha iyi çalışmasını sağlayacak kod değişiklikleri yapar. Değişiklikler kodun çıktısını etkilemez ama satır satır incelendiğinde farklı arasonuçlar veren satırlar bulunabilir. Bu kod değişikliklikleri, işlemci pipeline'ını daha verimli kullanmak için birbirinden bağımsız döngü adımlarının açılması, farklı işlemci birimlerini (ALU, memory fetcher, FPU vb.) kullanan komutların yer değiştirilmesi, etkin tampon bellek (cache) kullanımı için bellek adreslerinin yakınlaştırılması/hizalanması (alignment) gibi algoritmaları içerir. Bunların tam listesi Optimizing Compiler maddesinde bulunabilir.

Programcı ne kadar iyi kod yazarsa yazsın bu iyileştirmelerin hepsine hakim olması zordur. C programcısı gözünden bakıldığında, kod hızlı çalışacaksa bir çıkarma işleminin push'tan önce veya sonra olmasının önemi yoktur. Assembly programcısı gözünden, günümüz bilgisayarında çalışacak kodun satır satır optimizasyonu yorucu bir iştir. Intel'in Optimizasyon Reference Manual'ının 672 sayfa olduğu gözönünde bulundurulursa aynı zamanda karmaşık bir iştir ve neredeyse bu kitabı ezbere bilmeyi gerektirir.

2000'lerin başında işlemci mimarisi bu kadar karmaşık değilken bile, bu konuda konuştuğum bir meslektaşım, aynı kodu hem Delphi hem Win32 Assembly'de yazdığını ve Delphi kodunun belirgin şekilde performanslı çalıştığından sözetmişti. Bir de bu konunun Intel'le ilgili olan tarafı var. Intel'in belgelendirmediği işlemci komutları veya özellikleri varsa bunları yalnızca Intel derleyicileri kullanabilir (keza AMD için de).

GCC'nin temelde dört optimizasyon seviyesi var: 

* O0: Optimizasyonlar kapalıdır. Derleyici kodda ne varsa değiştirmeden assembly'e derler. Hata ayıklamak için kod bu seviyede derlenir. 

* O1: Temel optimizasyonlar yapılır. Branch prediction'la ve stack'le ilgili optimizasyonları içerir. 

* O2: O1'den daha agresif optimizasyonları içerir. Önerilen seviyedir. Thread'ler, fonksiyon çağrılarıyla ilgili kontroller ve karakter dizileriyle ilgili optimizasyonları içerir. 

* O3: O2'den daha agresif optimizasyonları içerir ama her zaman önerilmez. Loop unroll'lar assembly çıktısını büyütüp kodun yavaşlamasına veya FPU optimizasyonları nedeniyle sonuçların hassaslığını kaybetmesine neden olabilir. 

Bunlardan başka Os, Ofast gibi seçenekler de var ama bunları detaylandırmayacağım. Parametrelerle ilgili aşağıdaki kaynaklar incelenebilir:

https://wiki.gentoo.org/wiki/GCC_optimization

https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

İkinci kaynakta belirtildiği üzere bu parametreler farklı, tekil optimizasyon parametrelerini içeren paketlerdir. Örn. O2 ile birlikte fno-lra-remat kullanılırsa, lra-remat hariç O2 optimizasyonlarını uygula anlamı taşır.

Yazıyı uzatmadan assembly çıktısına bakalım. Kodu derlemek için gcc ve disassemble etmek için objdump kullandım. objdump normalde çıktıyı AT&T yazım biçimde verir. Ben Intel yazımını daha iyi bildiğim için -M parametresiyle çıktıyı bu şekilde ürettim.

gcc -O0 -o fib fib.c
objdump -M intel -d fib

İlgilendiğim kısım kodun main bloğu.  

  4004c4:  55                   push rbp
  4004c5:  48 89 e5             mov  rbp,rsp
  4004c8:  48 83 ec 10          sub  rsp,0x10
  4004cc:  c7 45 f4 00 00 00 00 mov  DWORD PTR [rbp-0xc],0x0
  4004d3:  c7 45 f8 01 00 00 00 mov  DWORD PTR [rbp-0x8],0x1
  4004da:  b8 18 06 40 00       mov  eax,0x400618
  4004df:  8b 55 f4             mov  edx,DWORD PTR [rbp-0xc]
  4004e2:  89 d6                mov  esi,edx
  4004e4:  48 89 c7             mov  rdi,rax
  4004e7:  b8 00 00 00 00       mov  eax,0x0
  4004ec:  e8 c7 fe ff ff       call 4003b8 <printf@plt>
  4004f1:  8b 45 f8             mov  eax,DWORD PTR [rbp-0x8]
  4004f4:  8b 55 f4             mov  edx,DWORD PTR [rbp-0xc]
  4004f7:  8d 04 02             lea  eax,[rdx+rax*1]
  4004fa:  89 45 fc             mov  DWORD PTR [rbp-0x4],eax
  4004fd:  8b 45 f8             mov  eax,DWORD PTR [rbp-0x8]
  400500:  89 45 f4             mov  DWORD PTR [rbp-0xc],eax
  400503:  8b 45 fc             mov  eax,DWORD PTR [rbp-0x4]
  400506:  89 45 f8             mov  DWORD PTR [rbp-0x8],eax
  400509:  81 7d f4 fe 00 00 00 cmp  DWORD PTR [rbp-0xc],0xfe
  400510:  7e c8                jle  4004da <main+0x16>
  400512:  eb b8                jmp  4004cc <main+0x8>

İlk üç komut main fonksiyonuna girişteki stack ayarlamalarına ait. C'nin kendi içinde yaptığı bir iş ve bir komut karşılığı yok.

40 04CCh ofsetindeki komut rbp-0Ch adresine 0 yazıyor. Bu, C kodundaki x=0 koduna karşılık geliyor. Buradan x değişkeninin rbp-0Ch adresinde saklandığını bulduk.

Sonraki komut rbp-8h adresine 1 yazıyor ve y=1 ifadesine karşılık geliyor. y değişkeni rbp-08h'da saklanıyor.

40 04DAh'daki komut printf'e ait. eax'e 40 0618h değerini yazıyor. Programın 40 0000h adresine yerleştiği gözönüne alınırsa bunun bir gösterici (pointer) olması muhtemel. Bu adres objdump çıktısında yok çünkü data alanında yer alan bir değer. hexdump -C fib komutuyla dosyanın içeriğine baktığımda 618h ofsetinde şu değerler var:

00000610  00 00 00 00 00 00 00 00  25 64 0a 00 01 1b 03 3b  |........%d.....;|

25h 64h 0Ah printf'e verilen biçem dizisi olan "%d\n"ye karşılık geliyor. eax'in değeri bu dizinin göstericisi oluyor.

Hemen sonraki komutlarda sırayla edx'e x değişkeni atanıyor. edx'teki değer esi'ye ve rax'teki değer rdi'ye atanıyor. Ardından eax sıfırlanıyor. Bunun nedeni biraz karışık ve aslında glibc'in sorunu. Özetle, printf'te kayar noktalı sayılar kullanılırsa bu değer farklı olur. Bununla ilgili ayrıntılı bilgi şurada: https://stackoverflow.com/questions/6212665/why-is-eax-zeroed-before-a-call-to-printf

40 04ECh ofsetinde printf çağrısı gerçekleşiyor.

40 04F1h'de y değişkeni rbp-8h adresinden eax'e alınıyor, sonraki komutta x değişkeni edx'e alınıyor ve ardından lea ile rdx ve rax toplanarak eax'e yazılıyor. z=x+y ifadesinin toplama kısmı lea ile yapılmış oluyor. 40 04FAh ofsetinde eax'teki bu değer rbp-4 adresinde -z değişkeni- depolanıyor. Dikkat edilirse değişkenler kodda tanımlandıkları sıranın tersine (sağdan sola) bellekte tutuluyorlar.

40 04FDh adresindeki komutla y değişkeni eax'e alınıyor ve 40 0500h adresindeki komutla eax'teki değer x'i tutan adrese yazılarak x=y ataması yapılıyor.

Benzer şekilde, sonraki iki komutla y=z ataması yapılıyor.

40 0509h adresinde x değeri 254'le karşılaştırılıyor. x bir tamsayı ve C kodunda karşılaştırma x<255 olduğundan bu eşitsizlikte x'in en büyük değeri 254 olabilir. 40 0510h ofsetindeki jle (jump if less or equal) x'in en çok 254 olduğu durumda doğrudur. Main'in ofseti 40 04C4h olduğundan; x, 254'ten küçükse dallanma 40 04DAh adresine yani do ile başlayan satıra yapılacak. Bu komut do döngüsünü bitiren komut. x, 254'ten büyükse altındaki koşulsuz dallanma (jmp) çalışacak ve 40 04CCh adresine gidecek. Bu adres kodun başı olduğuna göre bu jmp while(1) ifadesine karşılık geliyor.

Derleyici optimizasyonundan önce x değişkenini register (yazmaç) olarak tanımladım:

        int y,z;

        register x;

Kodu aynı parametrelerle derleyip assembly çıktısını aldım. 

  4004c4:  55                   push rbp
  4004c5:  48 89 e5             mov  rbp,rsp
  4004c8:  53                   push rbx
  4004c9:  48 83 ec 18          sub  rsp,0x18
  4004cd:  bb 00 00 00 00       mov  ebx,0x0
  4004d2:  c7 45 e8 01 00 00 00 mov  DWORD PTR [rbp-0x18],0x1
  4004d9:  b8 08 06 40 00       mov  eax,0x400608
  4004de:  89 de                mov  esi,ebx
  4004e0:  48 89 c7             mov  rdi,rax
  4004e3:  b8 00 00 00 00       mov  eax,0x0
  4004e8:  e8 cb fe ff ff       call 4003b8 <printf@plt>
  4004ed:  89 d8                mov  eax,ebx
  4004ef:  03 45 e8             add  eax,DWORD PTR [rbp-0x18]
  4004f2:  89 45 ec             mov  DWORD PTR [rbp-0x14],eax
  4004f5:  8b 5d e8             mov  ebx,DWORD PTR [rbp-0x18]
  4004f8:  8b 45 ec             mov  eax,DWORD PTR [rbp-0x14]
  4004fb:  89 45 e8             mov  DWORD PTR [rbp-0x18],eax
  4004fe:  81 fb fe 00 00 00    cmp  ebx,0xfe
  400504:  7e d3                jle  4004d9 <main+0x15>
  400506:  eb c5                jmp  4004cd <main+0x9>

Bu değişiklikle, x değişkeninin göstericisi kodda bulunmadığından hem kod 12 byte kısaldı hem de belleğe erişim azaldı. 40 04C8h adresinde rbx stack'e atılıyor. Stack'te öncekinden farklı olarak rbx de (64 bit) olduğundan, rsp'den 10h yerine 18h çıkarmak gerekiyor. rbx, x değişkeni için kullanılacak. Program sonlanıyor olsaydı en altta bu push'a karşılık gelen bir pop görecektik. 40 04CDh'da ebx'e sıfır atanması x=0'a karşılık geliyor. Bir sonraki komutta y değişkenine (rbp-18h) 1 atanıyor. printf için değişkenin esi'de olması gerekiyordu, 40 04DEh'deki komutla bu yapılıyor. Geri kalan kod bir önceki printf bloğuyla aynı.

40 04EDh ve bir sonraki komut x+y işlemini yapıyor ve altındaki komut da z değişkenine (rbp-14h) bu toplamın sonucunu yazıyor.

40 04F5h adresinde x=y ifadesi var. x register tanımlandığından bu ifade tek komuta indi.

40 04F8h ve bir sonraki komutla y=z ifadesi çalışıyor. Sonraki komutlar önceki örnekle aynı.

Register tanımlaması gerçek anlamda bir derleyici optimizasyonu değil. Sağlıklı bir karşılaştırma için O1'e geçmeden x'in tanımını tekrar int'e döndürdüm. Zaten O1 optimizasyonunda x'i derleyici kendiliğinden yazmaçta tutuyor olacak. Kodu gcc -O1 -o fib fib.c komutuyla derleyip objdump çıktısı aldım.

  4004c4:  41 55             push r13
  4004c6:  41 54             push r12
  4004c8:  55                push rbp
  4004c9:  53                push rbx
  4004ca:  48 83 ec 08       sub  rsp,0x8
  4004ce:  bb 01 00 00 00    mov  ebx,0x1
  4004d3:  bd 00 00 00 00    mov  ebp,0x0
  4004d8:  41 bc 01 00 00 00 mov  r12d,0x1
  4004de:  41 bd 00 00 00 00 mov  r13d,0x0
  4004e4:  eb 06             jmp  4004ec <main+0x28>
  4004e6:  44 89 e3          mov  ebx,r12d
  4004e9:  44 89 ed          mov  ebp,r13d
  4004ec:  89 ee             mov  esi,ebp
  4004ee:  bf 08 06 40 00    mov  edi,0x400608
  4004f3:  b8 00 00 00 00    mov  eax,0x0
  4004f8:  e8 bb fe ff ff    call 4003b8 <printf@plt>
  4004fd:  81 fb fe 00 00 00 cmp  ebx,0xfe
  400503:  7f e1             jg   4004e6 <main+0x22>
  400505:  8d 04 2b          lea  eax,[rbx+rbp*1]
  400508:  89 dd             mov  ebp,ebx
  40050a:  89 c3             mov  ebx,eax
  40050c:  eb de             jmp  4004ec <main+0x28>

Bu kod x'i register tanımladığım koddan 6 byte daha uzun. r12, r13 gibi "scratch" yazmaçlar x ve y'nin ilk değerlerini tutuyor. Böylece sabitler bellekte değil işlemcide tutuluyor. İlk dört push komutu yazmaçların değerini fonksiyonun çıkışında korumak için ama fonksiyon sonlanmadığından bunlara ait pop yok.

40 04CAh'daki sub komutu stack ayarlaması için.

40 04CEh'daki komut y=1 ifadesine, 40 04D3h'daki komut x=0 ifadesine karşılık geliyor.

40 04D8h ve 40 04DEh'daki komutlar yine y=1 ve x=0 ifadelerine karşılık geliyor ama kod boyunca bu yazmaçların değeri değişmiyor. Bunlardan yalnız okuma yapılıyor.

40 04E4h'deki jmp, printf'in karşılığı olan 40 04ECh - 40 04FCh arasındaki dört komutun ilkine dallanıyor.

40 04FDh'daki karşılaştırma y değerini tutan ebx'le yapılıyor. Bu biraz kafa karıştırıcı çünkü koddaki döngüde karşılaştırma x'le yapılıyordu. Tam emin olamamakla birlikte karşılaştırmadan (while'dan) iki satır üstteki x=y nedeniyle x yerine y kullanılabilir gibi bir mantığı olmalı. Karşılaştırmada y (aslında x) 254'ten büyük değilse döngüden çıkılmıyor.

40 0505h'da rbp ile rbx toplanarak eax'e yazılması z=x+y ifadesine karşılık geliyor.

40 0508h'daki komut x=y ifadesine; 40 050Ah'daki komut y=z ifadesinin karşılığı.

Bu işlemlerden sonra tekrar döngünün ilk komutu olan printf'e dallanılıyor.

Eğer 40 0503h'daki karşılaştırmanın sonucunda ebx, 254'ten büyük olsaydı bu durumda r12'deki y'nin ilk değeri (bir) ebx'e ve r13'te olan x'in ilk değeri (sıfır) ebp'ye aktarılarak tüm işlemler tekrarlanıyor.

Bu kod O0 ile karşılaştırıldığında hiç bellek erişiminin olmaması dikkat çekicidir.

Aynı kodu -O2'yle tekrar derleyip çıktısını aldım:

  4004d0:  55                push rbp

  4004d1:  31 ed             xor  ebp,ebp
  4004d3:  53                push rbx
  4004d4:  bb 01 00 00 00    mov  ebx,0x1
  4004d9:  48 83 ec 08       sub  rsp,0x8
  4004dd:  0f 1f 00          nop  DWORD PTR [rax]
  4004e0:  31 c0             xor  eax,eax
  4004e2:  89 ee             mov  esi,ebp
  4004e4:  bf 08 06 40 00    mov  edi,0x400608
  4004e9:  e8 ca fe ff ff    call 4003b8 <printf@plt>
  4004ee:  81 fb fe 00 00 00 cmp  ebx,0xfe
  4004f4:  7f 0a             jg   400500 <main+0x30>
  4004f6:  8d 04 2b          lea  eax,[rbx+rbp*1]
  4004f9:  89 dd             mov  ebp,ebx
  4004fb:  89 c3             mov  ebx,eax
  4004fd:  eb e1             jmp  4004e0 <main+0x10>
  4004ff:  90                nop
  400500:  bb 01 00 00 00    mov  ebx,0x1
  400505:  31 ed             xor  ebp,ebp
  400507:  eb d7             jmp  4004e0 <main+0x10>

İlk göze çarpan, bu kod önceki iki koddan çok daha kısa. Main 40 04D0h ofsetinden başlıyor ve diğerlerinden daha önce bitiyor ve yine hiç bellek erişimi yok. İkinci göze çarpan O0 ve O1'dekinin aksine mov <register>,0 işlemi hiç yok, yerine xor <register>,<register> işlemi var.

40 04D1h'da x=0'ın karşılığı olarak ebp sıfırlanıyor.

40 04D4h'da y=1'in karşılığı olarak ebx'e bir atanıyor.

Koddaki nop'lardan emin değilim ama hizalama amaçlı olabilir. (Kaynak - Asıl kaynak: http://www.agner.org/optimize/optimizing_assembly.pdf )

40 04E0h'dan 40 04EDh'ya kadar olan dört komut printf.

40 04EEh'da bir önceki örnekle aynı şekilde y, 254 ile karşılaştırılıp değer büyük değilse dallanmadan devam ediliyor.

40 04F6h'daki lea, z=x+y'nin, sonraki komutlar da sırayla x=y ve y=z'nin karşılığı.

jmp komutu döngüyü yeniden başlatmak için printf'in başına dallanıyor. Buradan anlaşılıyor ki döngünün mantığı aynı kalmak üzere yapısı değişiyor.

Eğer 40 04EEh'deki karşılaştırmanın sonucu doğruysa içteki do..while döngüsü bitmiştir. Bu durumda 40 04F4h adresindeki koşullu dallanma 40 0500h adresine dallanıyor. Bu adreste değişkenlerin içerikleri karşılık gelen yazmaçlara yeniden yazılıp (ofset 40 0500h - 40 0506h) tekrar kodun başına dallanılıyor (ofset 40 0507h).

Bu örnek O3 ile derlendiğinde O2'den farklı bir kod üretmiyor. Başka bir deyişle O3'ün içerdiği ama O2'de olmayan optimizasyon parametrelerinin* bu koda etkisi olmuyor.

Yazının başlarında O'lu optimizasyon parametrelerinin, tek tek uygulanabilir parametrelerin bir kümesi olduğunu belirtmiştim. Örn. O1, -fomit-frame-pointer adında bir parametre içeriyor. Bunu içermemesi için kod, gcc -O1 -fno-omit-frame-pointer -o fib fib.c komutuyla derlendiğinde main fonksiyonunun (ve diğer tüm fonksiyonların da) başı şöyle oluyor:

  4004c4:  55            push   rbp
  4004c5:  48 89 e5      mov    rbp,rsp
  4004c8:  41 56         push   r14

frame-pointer rbp yazmacı. Bu, fonksiyona girişte saklanıyor ve sonra stack erişimi bu yazmaç üzerinden yapılması için rsp'nin değeri rbp'ye yazılıyor. Derleyiciye omit-frame-pointer parametresi verildiğinde push ve mov ikilisi tüm fonksiyonlardan siliniyor. Bu durumda rbp'nin değeri fonksiyona girişte saklanmadığından, belleğe erişim rbp üzerinden değil rsp üzerinden yapılıyor.