Анализ Потока Данных Итеративные алгоритмы и SSA

Предмет анализа Определения и использования переменных Пути в графе управления t0 = mov 10 t1 = mov 2 t2 = add t1, t0 t3 = mul t2, 4 t4 = sub t3, t0 Время жизни t0 Определение t0 Использования t0 t1 = mov 1 t2 = add t1,2 t3 = shl t1,2 t4 = mul t2, 2 t0 = ld [x] t1 = add t0, 2 t2 = mov 10 Node Node 0 Node 1 Node 2 const t1t2 t4

Основные понятия 1. t0 = mov t1 = mov 2 3. t2 = add t1, t0 4. t3 = mul t2, 4 5. t4 = sub t3, t0 OUT[5] = {}, IN[5]= {t0,t3} OUT[4] = IN[5] = {t0,t3} IN[4] = {t0, t2} IN[4] OUT[4] = IN [5] GEN[5] = {t0,t3} GEN[4] = {t2} KILL[4] = {t3} OUT[5]

Значения потока данных 1. t0 = mov t1 = mov 2 3. t2 = add t1, t0 4. t0 = add t2, 4 5. t3 = sub t1, t0 INOUT S -… …

Глобальный анализ

Решение уравнений потока

Достигающие определения (reaching definitions)

Пример d1. Def t d2. Def t u1. Use t d4. Def t d3. Def t u2. Use t GENKILL Node 0{d1}{d2,d3,d4} 1{} 2{d2}{d1,d3,d4} 3{d4}{d1,d2,d3} 4{} 5{d3}{d1,d2,d4} Итеративное решение 01Iter IN OUT {}{d1} {d2}{d4}{d2} 2345 {d1} {d2}{d4} {d3} IN OUT 0 {}{d1, d4}{d1}{d2}{d4, d3}{d2} {d1}{d1, d4}{d2}{d4}{d4, d3}{d3} 1 IN OUT {}{d1, d4}{d1}{d2}{d4, d3}{d2} {d1}{d1, d4, d3}{d2}{d4}{d4, d3}{d3} 2

Влияние порядка вершин d1. Def t d2. Def t u1. Use t d4. Def t d3. Def t u2. Use t GENKILL Node 0{d1}{d2,d3,d4} 1{} 2{d2}{d1,d3,d4} 3{d4}{d1,d2,d3} 4{} 5{d3}{d1,d2,d4} Итеративное решение в порядке RPO 0Iter IN OUT {}{d2} {d3,d4}{d1,d3,d4} 3541 {d1}{d4}{d3}{d1,d3,d4} 0 2 {d1} {d2} {d3,d4}

Локальный анализ d1. Def t d2. Def t u1. Use t d4. Def t d3. Def t u2. Use t IN Node 0{} 1{d1,d3,d4} 2{d1} 3{d2} 4{d3,d4} 5{d2} d1d2d3d4 u1u2 Граф потока данных

Поиск доминаторов Возможна формулировка в виде прямой задачи потока Dom[B] – множество доминаторов узла B Передаточная функция Dom[B] = OUT[B] = IN[B] + {B} Оператор сбора В другом виде

SSA форма Одно присваивание каждой переменной (версии) Псевдооперация ϕ для версий одной переменной достигающих точек схождения по разным путям 1. x = mov y = mov 2 3. z = add x, y 4. x = add z, 4 5. z = sub x, y 1. x.0 = mov y.0 = mov 2 3. z.0 = add x.0, y.0 4. x.1 = add z.0, 4 5. z.1 = sub x.1, y.0 t1 = mov 1 t2 = add t1,2 t3 = shl t1,2 t4 = mul t2, 2 t0 = ld [x] t1 = add t0, 2 t2 = mov 10 Node 0 Node 1 Node 2 t1.0 = mov 1 t2.0 = add t1.0, 2 t1.2 = ϕ t1.0, t1.1 t2.2 = ϕ t2.0, t2.1 t3 = shl t1.2,2 t4 = mul t2.2, 2 t0 = ld [x] t1.1 = add t0, 2 t2.1 = mov 10 Node 0 Node 1 Node 2

Граф потока данных с SSA t1.0 = mov 1 t2.0 = add t1.0, 2 t1.2 = ϕ t1.0, t1.1 t2.2 = ϕ t2.0, t2.1 t3 = shl t1.2,2 t4 = mul t2.2, 2 t0 = ld [x] t1.1 = add t0, 2 t2.1 = mov 10 Node 0 Node 1 Node 2 t1.0 = mov 1 t0 = ld [x] t2.0 = add t1.0, 2 t1.1 = add t0, 2 t2.1 = mov 10 t1.2 = ϕ t1.0, t1.1 t2.2 = ϕ t2.0, t2.1 t3 = shl t1.2,2t4 = mul t2.2, 2 Существенно меньше дуг чем при прямом построении def-use цепочек

ДОПОЛНИТЕЛЬНО

Def-Use Chains loop: true: 3. %c = add %a, 1 false: 4. %b = 1 5. %c = add %a, %b end: 7. ret %d 6. %a = 1 1.%a = 1 2.%d = 2 1. %a = 1 3. %c = add %a, 1 5. %c = add %a, %b 4. %b = 16. %a = 1 2. %d = 1 7. ret %d

Problem with Def-Use Chains loop: 2. %a = add %a, 1 6. ret %a 1.%a = 1 %a.3 3. %a = add %a, 1 4. %a = add %a, 15. %a = add %a, 1 1. %a = 1 2. %c = add %a, 1 6. ret %d 3. %c = add %a, 1 4. %c = add %a, 15. %c = add %a, 1

Φ-Functions loop: true: 2. %a = add %a, 1 4. ret %a 3. %a = add %a, 1 1.%a = 1 2. %a = add %a, 1 3. %a = add %a, 1 4. ret %a %a.1 %a.3 %a.1 | %a.3 %a.2

Φ-Functions loop: true: 2. %a.2 = add %a_t1, 1 4. ret %a_t2 3. %a.3 = add %a_t2, 1 1.%a.1 = 1 5.mov %a_t1 = %a.1 6.mov %a_t1 = %a.3 8.mov %a_t2 = %a.2 7.mov %a_t2 = %a_t1

Φ-Functions 1. %a.1 = 1 2. %a.2 = add %a_t1, 1 3. %a.3 = add %a_t2, 1 4. ret %a 5.mov %a_t1 = %a.16.mov %a_t1 = %a.3 8.mov %a_t2 = %a.27.mov %a_t2 = %a_t1 ϕ ϕ

Φ-Functions 1. %a.1 = 1 2. %a.2 = add %a_t1, 1 3. %a.3 = add %a_t2, 1 4. ret %a 9.phi %a_t1 = %a.1, %a.3 10.phi %a_t2 = %a.2, %a_t1

Φ-Functions loop: 9.Phi %a_t1 = %a.1, %a.3 true: 2. %a.2 = add %a_t1, 1 4. ret %a_t2 10. Phi %a_t2 = %a.2, %a_t1 3. %a.3 = add %a_t2, 1 1.%a.1 = 1 loop: true: 2. %a = add %a, 1 4. ret %a 3. %a = add %a, 1 1.%a = 1