Bağımlılık analizi - Dependence analysis

İçinde derleyici teorisi, bağımlılık analizi İfadeler / talimatlar arasında yürütme sırası kısıtlamaları üretir. Genel olarak bir ifade S2 bağlıdır S1 Eğer S1 daha önce idam edilmeli S2. Genel olarak, iki tür bağımlılık vardır:kontrol bağımlılıkları ve veri bağımlılıkları.

Bağımlılık analizi, güvenli olup olmadığını belirler. yeniden sıralama veya paralelleştirmek ifadeler.

Kontrol bağımlılıkları

Kontrol bağımlılığı, bir program komutunun, önceki komutun yürütülmesine izin verecek şekilde değerlendirmesi durumunda yürütüldüğü bir durumdur.

Bir deyim S2 dır-dir kontrole bağlı açık S1 (yazılı ) ancak ve ancak S2 'infazı şartlı olarak korunmaktadır S1. Aşağıda bu tür bir kontrol bağımlılığına bir örnek verilmiştir:

S1 eğer x> 2 L1S2 y: = 3 S3 L1: z: = y + 1 ise

Buraya, S2 yalnızca yüklem S1 yanlış.

Görmek veri bağımlılıkları daha fazla ayrıntı için.

Veri bağımlılıkları

Bir veri bağımlılığı, aynı kaynağa erişen veya onu değiştiren iki ifadeden kaynaklanır.

Akış (Gerçek) bağımlılığı

Bir deyim S2 dır-dir akışa bağlı açık S1 (yazılı ) ancak ve ancak S1 bir kaynağı değiştirir S2 okur ve S1 önceler S2 yürütmede. Aşağıda bir akış bağımlılığı örneği verilmiştir (RAW: Yazdıktan Sonra Oku):

S1 x: = 10S2 y: = x + c

Antidependence

Bir deyim S2 dır-dir antidependent açık S1 (yazılı ) ancak ve ancak S2 bir kaynağı değiştirir S1 okur ve S1 önceler S2 yürütmede. Aşağıda bir antidependence örneği verilmiştir (WAR: Write After Read):

S1 x: = y + cS2 y: = 10

Buraya, S2 değerini belirler y fakat S1 önceki bir değerini okur yLiteratürde yaygın olarak kullanılan 'antidependence' terimi yanlış bir isimdir çünkü 'anti' tam tersi anlamına gelir. Doğru terim 'ante' anlamına gelmelidir. Dolayısıyla doğru kelime bağımlılık olmalıdır.

Çıktı bağımlılığı

Bir deyim S2 dır-dir çıktıya bağlı açık S1 (yazılı ) ancak ve ancak S1 ve S2 aynı kaynağı değiştirin ve S1 önceler S2 yürütmede. Aşağıda bir çıktı bağımlılığı örneği verilmiştir (WAW: Yazdıktan Sonra Yaz):

S1 x: = 10S2 x: = 20

Buraya, S2 ve S1 her ikisi de değişkeni ayarla x.

Giriş bağımlılığı

Bir deyim S2 dır-dir girdiye bağlı açık S1 (yazılı ) ancak ve ancak S1 ve S2 aynı kaynağı okuyun ve S1 önceler S2 yürütmede. Aşağıda bir girdi bağımlılığı örneği verilmiştir (RAR: Okuduktan Sonra Oku):

S1 y: = x + 3S2 z: = x + 5

Buraya, S2 ve S1 her ikisi de değişkene erişir x. Bu bağımlılık yeniden sıralamayı yasaklamaz.

Döngü bağımlılıkları

Önemli ve önemsiz bir sorun olan döngüler içindeki bilgi işlem bağımlılıkları sorunu, döngü bağımlılık analizi Burada verilen bağımlılık çerçevesini genişleten.

Ayrıca bakınız

daha fazla okuma

  • Cooper, Keith D .; Torczon, Linda. (2005). Derleyici Mühendisliği. Morgan Kaufmann. ISBN  1-55860-698-X.
  • Kennedy, Ken; Allen, Randy. (2001). Derleyicileri Modern Mimariler İçin Optimize Etme: Bağımlılık Temelli Bir Yaklaşım. Morgan Kaufmann. ISBN  1-55860-286-0.
  • Muchnick Steven S. (1997). Gelişmiş Derleyici Tasarımı ve Uygulaması. Morgan Kaufmann. ISBN  1-55860-320-4.