'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

Особенности нумерации 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 8 Node 2 Node 3 Node 6 Node 1 Node 4 Node 5 Start/Entry Node 8 Node 2 Node 3 Node 6 Node 1 Node 4 Node 5 Node 7 DFS tree Node 7


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

Пример для анализа 1 2 3 4 5 7 12 6 8 9 10 11


×

HTML:





Ссылка: