Dallanma

Dallanma (İngilizce: branch), bir bilgisayar programında denetim akışının sıralı gidişten ayrılıp başka bir adrese yönlendiği noktadır. Bu yönlendirmeyi gerçekleştiren buyruklara dallanma buyrukları (ya da atlama buyrukları) denir; bir dallanma buyruğu yürütüldüğünde program sayacı, sıradaki buyruk yerine yeni bir bellek konumunu gösterecek biçimde değiştirilir.

Üst düzey programlama dillerindeki if-else, while, for gibi koşul ve döngü yapıları ile işlev çağrıları, derlendiğinde alt düzeyde dallanma buyruklarına dönüşür. Dallanma, sıralı yürütmeyi kıran temel denetim akışı düzeneğidir ve neredeyse tüm buyruk kümelerinde bulunur.

Dallanma, boru hattına alınmış işlemcilerin başarımını sınırlayan başlıca etkenlerden biridir; sonucun ancak boru hattının ileri bir aşamasında belli olması, o ana kadar getirilen buyrukların boşa gitmesine yol açar. Bu kaybı azaltmak için geliştirilen dallanma öngörüsü çağdaş işlemcilerin temel bileşenlerindendir ve öngörünün yan etkileri 2018'de duyurulan Spectre saldırılarının dayanağını oluşturmuştur.

Dallanma türleri

Dallanma buyrukları çeşitli ölçütlere göre sınıflandırılır.

Koşullu ve koşulsuz dallanma

Koşulsuz dallanma, hiçbir şarta bağlı olmadan her zaman gerçekleşir (örneğin atla/jump buyruğu). Koşullu dallanma ise yalnızca belirli bir koşul (genellikle önceki bir işlemin sonucuna ya da bayrak yazmacına bakılarak) sağlandığında gerçekleşir; sağlanmazsa yürütme sıradaki buyrukla sürer. Üst düzey dillerdeki karar yapıları çoğunlukla koşullu dallanmalara çevrilir.

Doğrudan ve dolaylı dallanma

Hedef adresin nasıl belirtildiğine göre ayrım yapılır. Doğrudan dallanmada hedef, buyruğun içinde (sabit ya da program sayacına göreceli bir değer olarak) kodlanmıştır. Dolaylı dallanmada ise hedef buyrukta yazılı değildir; çalışma anında bir yazmaçtan veya bellek konumundan okunur. Dolaylı dallanma; işlev işaretçileri, sanal yöntem çağrıları ve atlama (switch/case) tablolarının gerçeklenmesini sağlar, ancak hedefi önceden bilinemediğinden öngörülmesi zordur.

Göreceli ve mutlak dallanma

Göreceli dallanmada (program sayacına göreceli) hedef, program sayacının o anki değerine bir uzaklık (offset) eklenerek bulunur; bu, kodun bellekte herhangi bir adrese yüklenebilmesini (yer değiştirebilirliği) kolaylaştırır. Mutlak dallanmada ise hedef adres tam olarak verilir.

Çağrı ve dönüş

Altyordam çağrısı (call), bir alt programa dallanırken geri dönüş adresini de saklar; altyordamın sonundaki dönüş (return) buyruğu, saklanan bu adrese (genellikle dolaylı olarak) geri dallanır. Böylece aynı altyordam farklı yerlerden çağrılabilir.

Koşulun üretilmesi

Koşullu bir dallanmanın gerçekleşip gerçekleşmeyeceğine bir karşılaştırmanın sonucuna bakılarak karar verilir. Bu sonucun nerede tutulduğu, buyruk kümesi mimarilerini birbirinden ayıran temel tasarım kararlarından biridir.

Koşullu dallanmanın farklı mimarilerde kuruluşu

Mimari	Koşul nerede tutulur	Örnek dizi
x86-64	Bayrak yazmacı	cmp rax, rbx je hedef
Arm (AArch64)	Bayrak yazmacı	cmp x0, x1 b.eq hedef
RISC-V	Dallanma buyruğunun içinde	blt a0, a1, hedef
MIPS	Eşitlik buyrukta, sıralama ayrı buyrukla	slt t0, t1, t2 bne t0, zero, hedef
PowerPC	Ayrı koşul yazmacı alanları	cmpw cr0, r3, r4 beq cr0, hedef

Çizelgedeki beş mimari üç aileye ayrılır. x86 ile Arm'da karşılaştırma ve dallanma iki ayrı buyruktur; aradaki bilgi bayrak yazmacında taşınır. RISC-V'de tek buyruk hem karşılaştırır hem dallanır. PowerPC ise arada durur: karşılaştırma sonucu bayrak yazmacına değil, sekiz ayrı alandan birine yazılır, dallanma buyruğu da hangi alana bakacağını söyler; böylece birden çok karşılaştırma aynı anda canlı tutulabilir ve derleyici bunları buyruk sırasına serbestçe dağıtabilir.

MIPS ile RISC-V arasındaki fark, aynı ailenin içinde de seçim bulunduğunu gösterir. MIPS'te dallanma buyruğu yalnızca eşitliği ve eşitsizliği sınar; iki yazmaçtan hangisinin küçük olduğuna bakmak için önce sonucu bir yazmaca yazan ayrı bir buyruk gerekir. RISC-V bu sınamaları da doğrudan dallanma buyruğuna koymuştur; işaretli ve işaretsiz karşılaştırmaların her biri için ayrı bir dallanma buyruğu vardır.

Arm'ın 64 bitlik sürümü iki aileyi birlikte kullanır. Genel karşılaştırmalar bayrak yazmacı üzerinden yürür, ama bir yazmacın sıfır olup olmadığını sınayan dallanma buyrukları bayrağa hiç dokunmadan çalışır; sıfırla karşılaştırma programlarda çok sık geçtiğinden bu buyruklar iki buyrukluk diziyi tek buyruğa indirir.

Bayrak yazmacı

Bir grup mimaride aritmetik ve karşılaştırma buyrukları, sonucun özelliklerini ayrı bir bayrak yazmacında (durum yazmacı) biriktirir: sonucun sıfır olup olmadığı, işareti, elde çıkıp çıkmadığı ve taşma olup olmadığı. Dallanma buyruğu yalnızca bu bayrakları sınar. x86 mimarisinde bayraklar aritmetik işlemlerin yan etkisi olarak kendiliğinden güncellenir; Arm mimarisi de aynı düzeni kullanır.

Bu düzenin üstünlüğü, tek bir karşılaştırmanın ardından birden çok dallanma yapılabilmesi ve dallanma buyruğunun kısa kalmasıdır. Sakıncası, bayrak yazmacının neredeyse her buyruğun dokunduğu örtük bir ortak durum olmasıdır; sırasız yürüten işlemcilerde bu yazmacın da öteki yazmaçlar gibi yeniden adlandırılması gerekir ve bu, tasarımı karmaşıklaştırır.

Karşılaştır ve dallan

Başka bir grup mimaride karşılaştırma dallanma buyruğunun kendi içindedir. RISC-V mimarisinde beq rs1, rs2, hedef biçimindeki buyruk iki yazmacı okur, eşitliği sınar ve sonuca göre dallanır; ayrı bir bayrak yazmacı bulunmaz.

Bu seçim örtük durumu ortadan kaldırır ve yazmaç yeniden adlandırmayı yalınlaştırır. Bedeli, dallanma buyruğunun iki yazmaç numarasını birden kodlamak zorunda kalması ve hedef uzaklığına ayrılan alanın daralmasıdır. RISC-V'in bayrak yazmacı kullanmama kararı, x86'nın bayrak yazmacına dayanan düzeniyle bilinçli bir karşıtlık oluşturur.

Dallanmanın maliyeti

Dallanma buyrukları programlarda seyrek değildir; genel amaçlı kodda her dört buyruktan biri dolayında bir oranla karşılaşılır. Bu sıklık, dallanmanın her birinin küçük bir gecikmeye yol açması durumunda bile toplam başarımın belirgin biçimde düşmesi anlamına gelir.

Beklemenin etkisi doğrudan hesaplanabilir. Programdaki dallanma buyruğu oranı f_d ve her dallanma için ödenen bekleme cezası c çevrim ise, buyruk başına çevrim değeri şöyle artar:

BBÇ = 1 + f_d × c

Dallanma oranı %25 ve ceza 1 çevrim olan bir programda BBÇ değeri 1'den 1,25'e çıkar; ideal boru hattına göre yürütme süresi %25 uzar.

Cezanın kaynağı

Dallanma ne kadar geç çözülürse o kadar çok buyruk boşa getirilir. Eşitlik sınaması Çöz aşamasına alınınca ceza iki çevrimden bir çevrime iner.

Ceza, dallanmanın sonucunun boru hattının ileri bir aşamasında belli olmasından doğar. Dallanma buyruğu getirildikten sonra, koşulun sınanacağı aşamaya ulaşana kadar geçen çevrimlerde işlemci hangi buyruğu getireceğini kesin olarak bilemez; yanlış yoldan getirilen buyruklar sonradan iptal edilir. Ceza, dallanmanın çözüldüğü aşamanın ne kadar geç geldiğine bağlıdır.

Bu nedenle tasarımcılar dallanmayı olabildiğince erken çözmeye çalışır. Beş aşamalı klasik boru hattında iki yazmacın eşitliği, aritmetik mantık biriminin sonucunu beklemek yerine Çöz aşamasına konan basit bir Dışlayan VEYA kapısıyla sınanabilir; bu değişiklik dallanma cezasını iki çevrimden bir çevrime indirir.

Erken çözümün bir bedeli vardır. Karşılaştırma bir aşama öne alındığında, karşılaştırılan değerlerin de bir aşama önce hazır olması gerekir. Bellekten değer yükleyen bir buyruğun hemen ardından gelen dallanma, yüklenen değeri Çöz aşamasında hiçbir yönlendirmeyle yakalayamaz ve iki çevrimlik bekleme kaçınılmaz olur. Erken çözüm dallanma cezasını azaltırken veri sorunlarını bir aşama öne çeker.

Boru hattı derinleştikçe sorun büyür. Dallanmanın çözüldüğü aşama daha geriye düştüğünden yanlış yoldan getirilen buyruk sayısı artar; derin boru hatlı tasarımlarda yanlış bir öngörünün bedeli onlarca çevrimi bulabilir.

Gecikmeli dallanma

Erken dönem boru hatlı mimarilerin bir bölümü, dallanma cezasını donanımda çözmek yerine buyruk kümesine yansıtmayı seçti. Gecikmeli dallanmada dallanma buyruğundan hemen sonra gelen buyruk, dallanmanın sonucu ne olursa olsun yürütülür. Bu buyruğun bulunduğu yere gecikme yuvası denir. Donanım, dallanmayı çözerken geçen çevrimi boşa harcamak yerine bu buyruğu işler.

Yuvayı yararlı bir buyrukla doldurmak derleyicinin işidir. Derleyici dallanmadan önceki bağımsız bir buyruğu yuvaya kaydırabilir, döngü gövdesinden bir buyruk çekebilir ya da hiçbirini bulamazsa yuvaya işlem yapmayan bir buyruk koyar. Ölçümler, derleyicinin yuvaların yaklaşık %60'ını doldurabildiğini ve yuvaya konan buyrukların yaklaşık %80'inin gerçekten yararlı olduğunu göstermiştir.

Yöntem MIPS ve SPARC gibi mimarilerde kullanıldı, sonra terk edildi. Terk edilmesinin üç nedeni vardır. Gecikme yuvası, boru hattının derinliği gibi bir gerçekleme ayrıntısını buyruk kümesine sızdırır; buyruk kümesi bir kez tanımlandıktan sonra yuva sayısı sabit kalır, oysa sonraki kuşaklarda boru hattı derinleşir ve bir yuva yetmez olur. Üçüncüsü, dallanma öngörüsünün yaygınlaşmasıyla kazanç önemsizleşmiştir. RISC-V tasarlanırken gecikmeli dallanma bilerek dışarıda bırakılmıştır.

Dallanmadan kaçınma

Kısa ve öngörülmesi güç bir dallanma söz konusu olduğunda, dallanmayı hiç yapmamak çoğu zaman daha ucuzdur. Bunun için buyruk kümeleri, bir işlemi koşula bağlı olarak etkisiz kılma yolları sunar.

Koşullu yürütmede buyruğun kendisi bir koşul alanı taşır; koşul sağlanmazsa buyruk getirilir, çözülür, ama sonucu yazmaca işlenmez. Arm mimarisinin 32 bitlik sürümünde neredeyse her buyruğa dört bitlik bir koşul alanı verilmişti; böylece kısa bir if bloğu hiç dallanma kullanmadan yazılabiliyordu.

Bu seçimin bedeli, koşul alanının her buyruktan dört bit götürmesidir. Arm'ın 64 bitlik sürümünde genel koşullu yürütme kaldırılmış, yerine yalnızca belirli işleri yapan koşullu seçim buyrukları konmuştur; bu buyruklar iki değerden birini koşula göre seçip yazmaca yazar. x86 mimarisindeki koşullu taşıma buyrukları da aynı işi görür.

Kazanç kesin değildir. Koşula bağlı yapılan iş, koşul sağlanmasa bile yürütme kaynağı harcar; dallanma iyi öngörülüyorsa öngörülü yürütme daha hızlıdır. Bu nedenle derleyiciler bu dönüşümü yalnızca dallanmanın kısa ve düzensiz olduğu yerlerde uygular.

Dallanmadan kaçınmanın başka bir gerekçesi güvenliktir. Gizli bir değere bağlı dallanma, yürütme süresini o değere göre değiştirir; Paul Kocher 1996'da bu farkın ölçülerek gizli anahtarın çıkarılabileceğini gösterdi. Şifreleme kodu bu nedenle, aldığı yol gizli veriye bağlı olmayacak biçimde, dallanmasız yazılır.

Hedefin kodlanması

Göreceli bir dallanmada hedef, buyruğun içine yerleştirilen bir uzaklık alanıyla belirtilir. Bu alanın bit genişliği, dallanmanın ulaşabileceği en uzak noktayı sınırlar; buyruk uzunluğu sabit olduğundan uzaklık alanına ayrılan her bit, başka bir alandan alınmak zorundadır.

Koşullu dallanma ile koşulsuz atlamanın menzilleri bu yüzden birbirinden farklıdır. RISC-V mimarisinde koşullu dallanma buyruğu, uzaklığın yanı sıra karşılaştırılacak iki yazmacın numarasını da taşımak zorundadır; geriye kalan alan yaklaşık ±4 KiB'lık bir menzile yeter. Koşulsuz atlama buyruğunda karşılaştırılacak yazmaç bulunmadığından aynı 32 bite çok daha geniş bir uzaklık sığar ve menzil yaklaşık ±1 MiB'a çıkar.

Hedef menzilin dışında kalıyorsa dallanma tek başına yetmez. Bu durumda derleyici ya da bağlayıcı, koşullu dallanmayı yakındaki bir ara noktaya yönlendirip oraya asıl hedefe giden koşulsuz bir atlama yerleştirir. Bu dönüşüm, büyük programlarda uzak işlevlere yapılan çağrıların çalışmasını sağlar.

Hedefin çalışma anında hesaplandığı durumlarda uzaklık alanı kullanılamaz; dolaylı dallanmada hedef bir yazmaçtan okunur ve menzil kısıtı ortadan kalkar.

Derleyicinin rolü

Bir programın dallanmasız ilerleyen buyruk dizilerine temel blok denir. Derleyici eniyilemelerinin çoğu bir temel bloğun içinde çalışır; blokların arasında hangi yolun izleneceği önceden bilinmediğinden buyruk sırasını değiştirmek güvenli olmaz. Dallanma ne kadar sıksa temel bloklar o kadar kısalır ve eniyilemeye kalan alan daralır.

Bu nedenle derleyiciler dallanma sayısını azaltmaya çalışır. Döngü açma, döngü gövdesini birden çok kez çoğaltarak döngü başına düşen dallanma sayısını düşürür: gövdesi dört kez çoğaltılan bir döngüde dallanma yalnızca dört yinelemede bir yürütülür, dallanmaların dörtte üçü ortadan kalkar. Kazancın karşılığı kodun büyümesi ve buyruk önbelleğine getirdiği yüktür.

Derleyici ayrıca kodu, sık geçilen yolun dallanmadan devam edecek biçimde yerleşmesine göre düzenler; böylece olağan durumda dallanma hiç gerçekleşmez ve öngörü kolaylaşır.

Dallanma öngörüsü

Ana madde: Dallanma öngörüsü

Boru hattı kullanan bir işlemcide dallanmanın yol açtığı bu belirsizliğe denetim sorunu denir. Cezayı ortadan kaldırmanın başlıca yolu, sonucu beklemek yerine öngörmektir. İşlemci dallanmanın gerçekleşip gerçekleşmeyeceğini ve hedefini tahmin eder, o yoldan buyruk getirmeyi sürdürür; tahmin doğru çıkarsa hiç bekleme olmaz, yanlış çıkarsa yanlış yoldan getirilen buyruklar iptal edilir ve ceza ödenir.

Günümüz işlemcilerinde öngörü doğruluk oranı %95'in üzerindedir. Derin boru hatlı tasarımları uygulanabilir kılan da budur; öngörü olmasaydı her dallanma onlarca çevrimlik bir bekleme anlamına gelirdi.

Güvenlik

Dallanma öngörüsü ile öngörüye dayalı yürütme, 2018'de duyurulan bir saldırı ailesinin dayanağı oldu. İşlemci öngördüğü yoldan ilerlerken erişmemesi gereken verilere dokunabilir; öngörü yanlış çıktığında bu buyrukların sonuçları iptal edilir, ancak bıraktıkları izler önbellekte kalır ve zamanlama ölçülerek okunabilir.

Saldırının bir biçiminde öngörücünün kendisi hedef alınır. Saldırgan, kendi denetimindeki dallanmaları belirli bir düzende yürüterek öngörücüyü eğitir; kurban programın dallanması daha sonra bu eğitilmiş kayda göre öngörülür ve seçilen yoldan ilerler. Bu nedenle dallanma öngörüsü artık yalnızca bir başarım konusu değil, aynı zamanda bir güvenlik konusudur.