Курсовая работа: домашние задания

Файл скачан с сайта StudIzba.com

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

digraph G{

0 [label="entry"]

1 [label="

L1:

02 t1 < +, l, r

03 m < /, t1, 2

04 t2 < *, 4, m

05 t3 < a[t2]

06 ifTrue t3 == v

07 goto L2

08 else

09 goto L3

"]

2 [label="

L2:

11 t4 < m;

12 return t4;

"]

3 [label="

L3:

14 t5 < *, 4, m

15 t6 < +, a, t5

16 t7 < a[t6]

17 ifTrue t7 > v

18 goto L4

19 else

20 goto L5

"]

4 [label="

L4:

22 r < -, m, l

"]

5 [label="

L5:

24 l < +, m, 1

"]

6 [label="

L6:

26 ifTrue r >= l

27 goto L1

28 else

29 goto L7

"]

7 [label="

L7:

31 t4 < -1

32 return t4

"]

8 [label="exit"]

0 -> 1

1 -> 2

1 -> 3

2 -> 3

3 -> 4

3 -> 5

4 -> 5

5 -> 6

6 -> 1

6 -> 7

7 -> 8

}

Блок 1

01 L1: - НББ

02 t1 < +, l, r

03 m < /, t1, 2

04 t2 < *, 4, m

05 t3 < a[t2]

06 ifTrue t3 == v

07 goto L2

08 else

09 goto L3

Блок 2

10 L2: - НББ

11 t4 < m;

12 return t4;

Блок 3

13 L3: - НББ

14 t5 < *, 4, m

15 t6 < +, a, t5

16 t7 < a[t6]

17 ifTrue t7 > v

18 goto L4

19 else

20 goto L5

Блок 4

21 L4: - НББ

22 r < -, m, l

Блок 5

23 L5: - НББ

24 l < +, m, 1

Блок 6

25 L6: - НББ

26 ifTrue r >= l

27 goto L1

28 else

29 goto L7

Блок 7

30 L7: - НББ

31 t4 < -1

32 return t4

граф потока управления можно посмотреть в файле graph.png построенному при помощи graphviz по файлу graph.txt

команды return xxx; не были обработаны никаким специальным образом. (не нашёл примера в слайдах для специальной обработки, но нашёл фразу о том, что после окончания блока - мы автоматически переходим в следующий за ним блок, так и было сделано)

//====================================== ======================================== ======================================== ====

//====================================== ======================================== ======================================== ====

//====================================== ======================================== ======================================== ====

Применим теперь алгоритм "Достигающие определения", чтобы вычислить Input и Output для каждого блока:

//====================================== ======================================== ======================================== ====

Вычислим Input для каждого блока

для начала вычислим kill и gen для каждого блока:

(t1, t2, t3, t4, t5, t6, t7, l, r, m, v, a)

Bx (gen) (kill)

B1 (2, 3, 4, 5) ()

B2 (11) (31)

B3 (14, 15, 16) ()

B4 (22) ()

B5 (24) ()

B6 () ()

B7 (31) (11)

По итерационному методу будет вчислять Input и Output

Out Bx 0 = (пусто) (0 - тут номер итерации)

In Bx 0 = ()

ниже - 1-я итерация ниже - 2-я итерация ниже должна быть 3-я итерация, но она полностью совпадает со 2-й, а значит итерационный процесс - остановился

In B1 1 = Out Entry + Out B6 0 = () = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B1 1 = genB1 + (In B1 1 - killB1) = (2, 3, 4, 5) + In B1 1 = (2, 3, 4, 5) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B2 1 = Out B1 1 = (2, 3, 4, 5) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B2 2 = genB2 + (In B2 1 - killB2) = (11) + (In B2 1 - (31)) = (2, 3, 4, 5, 11) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B3 1 = Out B1 1 + Out B2 1 = (2, 3, 4, 5, 11) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B3 1 = genB3 + (In B3 1 - killB3) = (14, 15, 16) + In B3 1 = (2, 3, 4, 5, 11, 14, 15, 16) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B4 1 = Out B3 1 = (2, 3, 4, 5, 11, 14, 15, 16) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B4 1 = genB4 + (In B4 1 - killB4) = (22) + In B4 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B5 1 = Out B3 1 + Out B4 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B5 1 = genB5 + (In B5 1 - killB5) = (24) + In B5 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B6 1 = Out B5 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B6 1 = genB6 + (In B6 1 - killB6) = In B6 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

In B7 1 = Out B6 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Out B7 1 = genB7 + (In B7 1 - killB7) = (31) + (In B7 1 - (11)) = (2, 3, 4, 5, 14, 15, 16, 22, 24, 31) = (2, 3, 4, 5, 14, 15, 16, 22, 24, 31)

Input B1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B2 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B3 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B4 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B5 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B6 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

Input B7 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)

//====================================== ======================================== ======================================== ====

Вычислим Output для каждого блока

для начала вычислим def и use для каждого блока:

Bx use def

B1 (22, 24) (2, 3, 4, 5)

B2 (3) (11)

B3 (3) (14, 15, 16)

B4 (3, 24) (22)

B5 (3) (24)

B6 (22, 24) ()

B7 () (31)

In exit 0 = ()

ниже 1-я итер. ниже 2-я итер. ниже 3-я итер., но она совпадает со 2-й, а значит процесс останавливается

Out B7 = In exit = ()

In B7 = useB7 + (Out B7 - defB7) = Out B7 - 31 = ()

Out B6 = In B1 + In B7 = () = (3, 22, 24)

In B6 = useB6 + (Out B6 - defB6) = (22, 24) + Out B6 = (22, 24) = (3, 22, 24)

Out B5 = In B6 = (22, 24) = (3, 22, 24)

In B5 = useB5 + (Out B5 - defB5) = (3) + (Out B5 - (24)) = (3, 22) = (3, 22)

Out B4 = In B5 = (3, 22) = (3, 22)

In B4 = useB4 + (Out B4 - defB4) = (3, 24) + (Out B4 - (22)) = (3, 24) = (3, 24)

Out B3 = In B4 + In B5 = (3, 22, 24) = (3, 22, 24)

In B3 = useB3 + (Out B3 - defB3) = (3) + (out B3 - (14, 15, 16)) = (3, 22, 24) = (3, 22, 24)

Out B2 = In B3 = (3, 22, 24) = (3, 22, 24)

In B2 = useB2 + (Out B2 - defB2) = (3) + (Out B2 - (11)) = (3, 22, 24) = (3, 22, 24)

Out B1 = In B2 + In B3 = (3, 22, 24) = (3, 22, 24)

In B1 = useB1 + (Out B1 - defB1) = (22, 24) + (Out B1 - (2,3,4,5)) = (3, 22, 24) = (3, 22, 24)

Output B1 = (3, 22, 24)

Output B2 = (3, 22, 24)

Output B3 = (3, 22, 24)

Output B4 = (3, 22)

Output B5 = (3, 22, 24)

Output B6 = (3, 22, 24)

Output B7 = ()

//====================================== ======================================== ======================================== ====

Тут ниже ошибка была, переделано и написано выше

//====================================== ======================================== ======================================== ====

Вычислим Output для каждого блока

для начала вычислим def и use для каждого блока:

Bx use def

B1 (22, 24) (т.к. l, r, a, v - используются в блоке до того, как они определены в этом блоке и их можно достигнуть следуя в графе против шерсти) (2, 5, 6) (потому что это там где используются неопределённые переменные)

B2 (3) (m) (11)

Построить Граф Потока Управления. Для каждого Базового Блока найти множества Input и Output.

Код в промежуточном представлении:

!Внимание: В данном промежуточном представлении, метки расположены над строкой, а не слева от строки, как Вы привыкли видеть в лекциях Сергея Суреновича. Как только Вы сдадите первое задание, получите следующие.

Свои решения присылайте на bmk-compilers@ispras.ru

01 L1:

02 t1 < +, l, r

03 m < /, t1, 2

04 t2 < *, 4, m

05 t3 < a[t2]

06 ifTrue t3 == v

07 goto L2

08 else

09 goto L3

10 L2:

11 t4 < m;

12 return t4;

13 L3:

14 t5 < *, 4, m

15 t6 < +, a, t5

16 t7 < a[t6]

17 ifTrue t7 > v

18 goto L4

19 else

20 goto L5

21 L4:

22 r < -, m, l

23 L5:

24 l < +, m, 1

25 L6:

26 ifTrue r >= l

27 goto L1

28 else

29 goto L7

30 L7:

31 t4 < -1

32 return t4

https://unihub.ru/groups/bmk

По всей видимости файл пустой