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

инструкций, такая что:
Поток управления может входить только в первую инструкцию
Управление покидает линейный участок без ветвлений, за исключением, возможно, в последней команде.

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

условный или безусловный переход
Блоки следуют друг за другом в исходной последовательности, причем первый не заканчивается безусловным переходом

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. 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

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, 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

2

Node 3

Node 5

Node 1

Node 4

Node 6

Node 7

Дерево доминаторов

Node 0

Node 0

6

Node 8

Node 2

Node 3

Node 5

Node 4

Node 1

Node 7

Дерево постдоминаторов

Node 0

существует дуга из 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

Граф зависимостей по управлению

множество вершин Y такое что x доминирует предшественника y но не доминирует строго y

DF(1) = {4,7}

DF(1) = {4,7}

Итеративная граница доминирования:

множество вершин каждая из которых достижима из любой другой вершины этого множества (сильно связаная компонента на графе управления)

Особенные вершины:
Голова цикла
Входные вершины
Выходные вершины

Особенные дуги:
Обратные дуги
Входные дуги
Выходные дуги

nest:

Node 5

Loop 1

Loop 3

Loop 2

Loop 0

Loop ttee:

1

0

5

1

2

4

3

6

Побочный вход

Побочный вход

head

head