Анализ потока управления. Линейные участки (basic blocks, базовые блоки) Линейный участок – это максимальная последовательность инструкций, такая что: - презентация

1 Анализ потока управления

2 Линейные участки (basic blocks, базовые блоки) Линейный участок – это максимальная последовательность инструкций, такая что: Поток управления может входить только в первую инструкцию Управление покидает линейный участок без ветвлений, за исключением, возможно, в последней команде. 1. t0 = ld [x_addr] 2. t1 = ld [y_addr] 3. p0 = cmpe t0, t1 4. brc p0, t2 = ld [i_addr] 6. t3 = shl t2, 2 7. p1 = cmpe t3, brc p1, t1 = sub t1, add t2,1 -> t2 11. bru t4 = shl t1, t5 = add arr_addr, st [t5], t4 15. ret

3 Разбиение кода на ЛУ Поиск первых инструкций («лидеров», входов) – Первая команда – Целевая команда перехода – Команда за условным или безусловным переходом Построение ЛУ, начиная с лидеров 1. t0 = ld [x_addr] 2. t1 = ld [y_addr] 3. p0 = cmpe t0, t1 4. brc p0, t2 = ld [i_addr] 6. t3 = shl t2, 2 7. p1 = cmpe t3, brc p1, t1 = sub t1, add t2,1 -> t2 11. bru t4 = shl t1, t5 = add arr_addr, st [t5], t4 15. ret

4 Граф управления Вершины – линейные участки Дуги существуют между блоками если: – Между ними существует условный или безусловный переход – Блоки следуют друг за другом в исходной последовательности, причем первый не заканчивается безусловным переходом 1. t0 = ld [x_addr] 2. t1 = ld [y_addr] 3. p0 = cmpe t0, t1 4. brc p0, t2 = ld [i_addr] 6. t3 = shl t2, 2 7. p1 = cmpe t3, brc p1, t1 = sub t1, add t2,1 -> t2 11. bru t4 = shl t1, t5 = add arr_addr, st [t5], t4 15. ret

5 Граф управления 1. t0 = ld [x_addr] 2. t1 = ld [y_addr] 3. p0 = cmpe t0, t1 4. brc p0, t2 = ld [i_addr] 6. t3 = shl t2, 2 7. p1 = cmpe t3, brc p1, t1 = sub t1, add t2,1 -> t2 11. bru t4 = shl t1, t5 = add arr_addr, st [t5], t4 15. ret 1. t0 = ld [x_addr] 2. t1 = ld [y_addr] 3. p0 = cmpe t0, t1 4. brc p0, t2 = ld [i_addr] 6. t3 = shl t2, 2 7. p1 = cmpe t3, brc p1, t1 = sub t1, add t2,1 -> t2 11. bru t4 = shl t1, t5 = add arr_addr, st [t5], t4 15. ret 4. brc 8. brc 11. brc

6 Поиск в глубину Start/Entry Node 8Node 2 Node 3 Node 6 Node 1 Back edge Node 4 Node 5 Cross edge tree edge Start/Entry Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node 7 DFS tree Node 7

7 Особенности нумерации Pre-order s, 1, 2, 3, 4, 5, 6, 7, 8 Post-order 6, 5, 7, 4, 3, 2, 8, 1, s Reverse post order s, 1, 8, 2, 3, 4, 7, 5, 6 Start/Entry Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5 Start/Entry Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node 7 DFS tree Node 7

8 Доминаторы и постдоминаторы Отношение доминирования Строгое доминирование Непосредственный доминатор Постдоминатор

9 Доминаторы (пример) Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node 7 Node 8Node 2Node 3 Node 5 Node 1 Node 4Node 6Node 7 Дерево доминаторов Node 0

10 Постдоминаторы (пример) Node 0 Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node 7 Node 6 Node 8Node 2 Node 3Node 5Node 4 Node 1 Node 7 Дерево постдоминаторов Node 0

11 Зависимость по управлению Вершина y зависит по управлению от вершины x если существует дуга из x в z, такая что y pdom z, но y !pdom x. Node 0 Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node Дерево постдоминаторов 0 Node 0 Node 8 Node 2 Node 3Node 6Node 1 Node 4 Node 5Node 7 Граф зависимостей по управлению

12 Граница доминирования Node 8Node 2 Node 3 Node 6 Node 1 Node 4 Node 5Node 7 Node 0 DF(x) множество вершин Y такое что x доминирует предшественника y но не доминирует строго y DF(1) = {4,7} Итеративная граница доминирования:

13 Циклы в графах потока управления Statt/Entty Node 3Node 2 Node 4 Stop Node 1 Loop head backedge Цикл – множество вершин каждая из которых достижима из любой другой вершины этого множества (сильно связаная компонента на графе управления) Особенные вершины: Голова цикла Входные вершины Выходные вершины Особенные дуги: Обратные дуги Входные дуги Выходные дуги

14 Loop 3 Outetmost Loop 1 Innetmost Loop 2 Дерево циклов Statt/Entty Node 3Node 2 Node 4 Stop Node 1 Loop nest: Node 5 Loop 1Loop 3 Loop 2 Loop 0 Loop ttee:

15 Несводимые циклы Start Node 3Node 5 Node 4 Stop Node 2 Node 1 head Start Node 3Node 5 Node 4 Stop Node 2 Node Побочный вход head

16 Пример для анализа