Залежність даних

Залежність потоку, також відомий як залежність даних або істинної залежності або читання після запису (RAW), відбувається, коли інструкція залежить від результату попередньої інструкції:

1. A = 3 2. B = A 3. C = B

Інструкція 3 дійсно залежить від інструкції 2, оскільки кінцеве значення C залежить від інструкції оновлюючи B. Інструкція 2 дійсно залежить від інструкції 1, бо остаточне значення B залежить від поновлення інструкції A. Через те, що інструкція 3 дійсно залежить Інструкція по 2 і 2 інструкції дійсно залежить від інструкції 1, 3 інструкція також дійсно залежить від інструкції 1. паралелізм на рівні команд тому не варіант в даному прикладі.

Антизалежність, також відомий як від запису після читання (WAR), має місце, коли інструкція вимагає значення, який пізніше був оновлений. У наступному прикладі, команда 2 антизалежить від інструкції 3 — впорядкування цих інструкцій не можуть бути змінені, вони також не можуть бути виконані паралельно (можлива зміна упорядкування команд), позаяк це може вплинути на кінцеве значення А.

1. B = 3
2. A = B + 1
3. B = 7

Антизалежність є прикладом імені залежності. Тобто, перейменування змінних можна було видалити залежність, як в наступному прикладі:

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

Нова змінна, B2, був оголошений як копія B в новій інструкції, інструкції N. антизалежність між 2 і 3 був видалений, а це означає, що ці інструкції можуть бути в цей час виконуються паралельно. Проте, модифікація представила нову залежність: інструкція 2 тепер дійсно залежить від інструкції N, який дійсно залежить від інструкції 1. Залежно потоку, ці нові залежності неможливо безпечно видалити.

Вихідна залежність, також відома як записи після запису (WAW), має місце, коли впорядкованість інструкцій впливатиме на кінцеве вихідне значення змінної. У прикладі, наведеному нижче, є вихід залежність між командами 3 і 1 — зміна порядку інструкцій в цьому прикладі буде змінюватися кінцеве значення A, таким чином, ці інструкції не можуть бути виконані паралельно.

1. B = 3
2. A = B + 1
3. B = 7

Як і з антизалежностей, залежностей вихідних є залежностями імен. Тобто, вони можуть бути видалені за допомогою перейменування змінних, як в наведеному нижче модифікації наведеного вище прикладу:

1. B2 = 3
2. A = B2 + 1
3. B = 7

Зазвичай використовується для іменування залежностей даних є наступне: для читання після запису або RAW (залежність потоку), запис після запису або WAW (вихід залежностей) і Write-Після читання або WAR (антизалежність).

Залежно управління, по суті, домінування кордону у зворотному графіку графа потоку управління (CFG). [2] Таким чином, один зі способів їх побудови, було б побудувати постдомінантності кордон КТГ, а потім заднім ходом його отримання контроль граф залежностей.

Нижче наведено псевдокод для побудови постдомінантності кордону: for each X in a bottom-up traversal of the dominator tree do:

 PostDominanceFrontier(X) ← ∅
 for each Y ∈ Predecessors(X) do:
   if immediatePostDominator(Y) ≠ X:
     then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
 done
 for each Z ∈ Children(X) do:
   for each Y ∈ PostDominanceFrontier(Z) do:
     if immediatePostDominator(Y) ≠ X:
       then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
   done
 done

Тут діти (X) є безліч вузлів у CFG, які після домінують X і Попередники (X) є набором вузлів у CFG, які безпосередньо передують X у CFG.

Після того, як постдомінантність кордону карти обчислюється, звертає його призведе до карти від вузлів у CFG до вузлів, які мають залежність управління від них.