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 bloğu 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ş bloğu (kontrol, akış grafiğine giriş bloğundan geçerek girer.) Çıkış bloğu (bütün kontrol akışları, çıkış bloğundan 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ş bloğunu 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ış bloğu, giriş bloğundan 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ş bloğu: 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 bloğundan çıkan, hem e hedef bloğuna 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ış bloğunun ü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 bloğu N bloğunu baskılıyor demektir. Giriş bloğu bütün blokları baskılar. Anlık baskılayıcı: M bloğu, N bloğunu baskılıyorsa ve M'nin baskıladığı N'yi baskılayan müdahaleci bir P bloğu yoksa, M bloğu N bloğunu anlık baskılıyor demektir. Başka bir deyişle M bloğu N bloğuna giriş yolundaki son baskılayıcıdır. Her bloğun 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 bloğundan N bloğuna bir ark vardır. Her bloğun tek bir anlık baskılayıcısı olduğundan bu çizelge bir ağaçtır. Ağacın kökü giriş bloğundadı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ış bloğundadı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 bloğu birçok gelen ayrıtla baskılayıcı, bazıları arka ayrıtla (böylece M döngü başlığı olur). M bloğunu 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ş bloğu, D çıkış bloğu 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
rogramlama
rogramlama