Kontrol akış çizelgesi

Kontrol Akış Çizelgesi (Control Flow Graph (CFG)), bir program yürütülürken içinden geçebilecek bütün yolların çizelge simgeleri kullanılarak gösterimidir.

Çizelgedeki her boğum bir temel bloku gösterir. Kontrol akışındaki atlamaları göstermek için yönlendirilmiş ayrıtlar kullanılır.

İki özel olarak belirlenmiş blok vardır:
 Giriş bloku (kontrol, akış grafiğine giriş blokundan geçerek girer.)
 Çıkış bloku (bütün kontrol akışları, çıkış blokundan geçerek çıkar.)

CFG, birçok derleyici eniyilemesinin ve statik analiz gereçlerinin özüdür.
Ulaşılabilirlik, eniyilemede kullanışlı olan başka bir çizelge özelliğidir.

 Ulaşılabilirlik 
Eğer bir blok / alt, giriş blokunu bulunduran alt çizgeyle bağlantılı değilse, o blok herhangi bir yürütüm boyunca ulaşılmazdır ve ulaşılamaz kod güvenli bir şekilde kaldırılabilir. Eğer çıkış bloku, giriş blokundan ulaşılamaz ise, bu sonsuz döngüyü belirtir.

Programcı kodu açık olarak o yolla yazmazsa da, yine de ölü kodlar ve sonsuz döngüler mümkün olabilir. Sabit yayılım ve sabit katlama gibi atlama izleğiyle takip edilen eniyilemeler, çoklu temel bir bloğa çökertebilir. Bu da ayrıtların CFG'den kaldırılmasına neden olur.

 Terminoloji 
Bu terimler, kontrol akış çizelgelerini anlatırken çokça kullanılır:

 Bloklar 
 Giriş bloku: Bütün kontrol akışlarının akış çizelgesinin içinden geçerek girdiği blok
 Çıkış blogu: Bütün kontrol akışlarının akış çizelgesinin içinden geçerek çıktığı blok

 Ayrıtlar 
 Arka ayrıt: Grafiğin derinliğine geçmesinde bir atayı işaret eden ayrıt.
 Kritik ayrıt: Hem kaynak blokundan çıkan, hem e hedef blokuna giren ayrıt. Bu ayrıtlar, ayrıta hesaplama yerleştirmek için bölünmüş olmalı (ayrıtın ortasında yeni bir blok yaratılmalı)
 Olağan dışı ayrıt: Hedefi bilinmeyen ayrıt. Bu ayrıtlar eniyilemeyi katlamaya eğilimlidir. Ayrıklık giderimi yapıları bu ayrıtları üretebilir.
 Olanaksız ayrıt: (Sahte ayrıt olarak da bilinir) Çizelgeye yalnızca çıkış blokunun ütün blokları sonradan bastırma özelliğini korumak için eklenen ayrıttır. Bu ayrıtın içinden geçilemez.

 Baskılayıcı 
 Baskılayıcı: Eğer girişten blok N'ye ulaşan her yol, M'den geçmek zorunda ise, M bloku N blokunu baskılıyor demektir. Giriş bloku bütün blokları baskılar.
 Anlık baskılayıcı: M bloku, N blokunu baskılıyorsa ve M'nin baskıladığı N'yi baskılayan müdahaleci bir P bloku yoksa, M bloku N blokunu anlık baskılıyor demektir. Başka bir deyişle M bloku N blokuna giriş yolundaki son baskılayıcıdır. Her blokun tek bir anlık baskılayıcısı vardır.
 Anlık sonradan baskılayıcı: Anlık baskılayıcının bir benzeridir.
 Baskılayıcı ağaç: Baskılayıcı bağlantıları gösteren yardımcı veri yapısı. Eğer M, N'nin anlık baskılayıcısı ise M blokundan N blokuna bir ark vardır. Her blokun tek bir anlık baskılayıcısı olduğundan bu çizelge bir ağaçtır. Ağacın kökü giriş blokundadır. Lengauer-Tarjan algoritması kullanılarak etkin bir biçimde kullanılabilir.
 Sonradan baskılayıcı ağaç: Baskılayıcı ağacın bir benzeridir. Bu ağacın kökü çıkış blokundadır.

 Döngü 
 Döngü başlığı: Döngü oluşturan arka ayrıtın hedefi olan baskılayıcı bazen döngünün giriş noktası olarak kullanılır. Döngüdeki bütün blokları baskılar.
 Döngü ön başlığı: Farzedelim ki M bloku birçok gelen ayrıtla baskılayıcı, bazıları arka ayrıtla (böylece M döngü başlığı olur). M blokunu Mpre ve Mloop olarak iki bloğa ayırmak birçok eniyilemenin geçişi için faydalıdır. M'nin ve arka ayrıtların içeriği Mloop'a aktarılır, geri kalan ayrıtlarda Mpre'ye aktarılır ve Mpre'den Mloop'a yeni bir ayrıt yerleştirilir (Mpre'nin Mloop'un anlık baskılyıcısı olması için). Başta Mpre boş olur ama döngü-değişimsiz kod devinimi gibi geçişler Mpre'yi doldurabilir.

 Örnek 
Aşağıdaki kod parçasını ele alalım:
 0: (A) t0 = read_num
 1: (A) if t0 mod 2 == 0 goto 4
 2: (B) print t0 + " is odd."
 3: (B) goto 5
 4: (C) print t0 + " is even."
 5: (D) end program
Yukarıda 4 tane temel blok var: 0'dan 1'e A, 1'den 3'e B, 4'te C, 5'te D.
Bu örnekte; A giriş bloku, D çıkış bloku ve 4 ve 5 satırları aklama hedefleri. Bu kod parçası için çizilecek çizelge A'dan B'ye, A'dan C'ye, B'den D'ye ve C'den D'ye ayrıtlara sahiptir.

Kategori:Programlama