Методические указания (1114907), страница 13
Текст из файла (страница 13)
Еще одно представление трехадресного кода состоит в использовании списка указателей на тройки вместо списка самих троек. Естественно, такая реализация названа косвенными тройками (indirect triples).
Ниже приведена таблица, содержащая непосредственно тройки.
| op | arg1 | arg2 | |
| (14) | uminus | c | |
| (15) | * | b | (14) |
| (16) | uminus | c | |
| (17) | * | b | (16) |
| (18) | + | (15) | (17) |
| (19) | assign | а | (18) |
Далее таблица, содержащая ссылки на эти тройки
| statement | |
| (0) | (14) |
| (1) | (15) |
| (2) | (16) |
| (3) | (17) |
| (4) | (18) |
| (5) | (19) |
Оптимизация
Существует ряд способов, которыми компилятор может улучшить программу без изменения вычисляемой функции. Устранение общих подвыражений, размножение копий, удаление недоступного кода и дублирование констант – вот основные примеры таких преобразований, сохраняющих функции.
Общие подвыражения.
Выражение E называется общим подвыражением, если E было ранее вычислено и значения переменных в E с того времени не изменились. Повторного вычисления можно избежать, если использовать ранее вычисленные значения.
Приведем фрагмент кода с подвыражениями, которые будут устранены в результате оптимизации.
t6 := 4 * i
x := a[t6]
t7 := 4 * i
t8 := 4 * j
t9 := a[t8]
a[t7] := t9
t10 := 4 * j
a[t10] := x
t6 := 4 * i
x := a[t6]
t8 := 4 * j
t9 := a[t8]
a[t6] := t9
a[t8] := x
Распространение копий.
Идея преобразования распространения копий заключается в использовании после присваивания f := g переменной g вместо f везде, где это только возможно.
Сам по себе этот прием не несет в себе улучшения качества кода, однако совместно с удалением бесполезного кода, которое будет описано ниже.
Приведем фрагмент кода, в котором проведем распространение копий.
x := t3
a[t2] := t5
a[t4] := t3
x := t3
a[t2] := t5
a[t4] := x
Удаление бесполезного кода.
Переменная в некоторой точке программы считается “живой”, или активной, если ее значение будет использовано в программе в последующем; в противном случае она считается “мертвой”. Очередная оптимизация касается “мертвого”, или бесполезного кода, т.е. кода, вычисляющего значения, которые никогда не будут использованы.
Таким образом, данная оптимизация совместно с распространением копий превращает инструкции копирования в мертвый код, который в последствие удаляется.
Приведем фрагмент кода, в котором удалим бесполезный код.
x := t3
a[t2] := t5
a[t4] := t3
a[t2] := t5
a[t4] := t3
Построение формальной КС-грамматики, а так же ее атрибутивной грамматики с семантическими действиями более подробно описано в лабораторном практикуме по курсу.
Условие:
-
Построить промежуточный код в указанном формате (С?) для фрагмента исходного кода (F?) на языке C.
-
Описать типологию команд промежуточного кода. Она должна соответствовать той, что описана выше в теории.
-
Над полученным промежуточным кодом провести оптимизацию. Записать протокол оптимизирующих действий.
-
Полученный после оптимизации код записать в другом формате (-> C?).
-
По исходному фрагменту кода построить формальную КС-грамматику, которая задавала бы схожие фрагменты.
-
На основе полученной КС-грамматики построить атрибутивную грамматику, в которой описываются действия по проверке семантических ошибок и по генерации промежуточного кода.
Варианты:
| № | Формулировка варианта задания |
| | F1,C1 -> C3 |
| | F1,C2 -> C3 |
| | F1,C3 -> C1 |
| | F1,C4 -> C1 |
| | F1,C5 -> C1 |
| | F2,C1 -> C3 |
| | F2,C2 -> C3 |
| | F2,C3 -> C1 |
| | F2,C4 -> C1 |
| | F2,C5 -> C1 |
| | F3,C1 -> C3 |
| | F3,C2 -> C3 |
| | F3,C3 -> C1 |
| | F3,C4 -> C1 |
| | F3,C5 -> C1 |
| | F4,C1 -> C3 |
| | F4,C2 -> C3 |
| | F4,C3 -> C1 |
| | F4,C4 -> C1 |
| | F4,C5 -> C1 |
| | F5,C1 -> C3 |
| | F5,C2 -> C3 |
| | F5,C3 -> C1 |
| | F5,C4 -> C1 |
| | F5,C5 -> C1 |
| | F6,C1 -> C3 |
| | F6,C2 -> C3 |
| | F6,C3 -> C1 |
| | F6,C4 -> C1 |
| | F6,C5 -> C1 |
| F1 | int a, b, c = 1, d = c * 3; char * s = “строка символов”; if (s[c + d] == 0) { a = c + 1; b = c + 2; } else { a = d + 1; b = d + 2; } printf(“Ответ: %d”, a + b); |
| F2 | int f(int n) { return n * 3 + 1;} int main(void) { int d = f (4); return f(5) + d; } |
| F3 | for (int i = 0; i < 12; i++) { scanf(“%d”, f); int d = i * f * 3; printf(“%d”, d); } |
| F4 | int a, b; scanf(“%d”, a); switch(a) { case 1: b = a + 1; case 2: b = a + 2; break; default: b = 0; } exit(b); |
| F5 | struct {int a; char b} s, f; s.a = 1; s.b = ‘3’; strcpy(&f, &s, sizeof(s)); printf(“%d - %d”, f.a, f.b); |
| F6 | char[] str = “string”; int a, b, c; a = 3; if (str[a] == ‘\n’) { b = str[a-1]; c = 0; } else { b = str[a+1]; c = 1; } str[b] = 0; printf (“%s”, str); |
| C1 | Синтаксическое дерево |
| C2 | Даг |
| C3 | Трехадресный код. Четверки |
| C4 | Трехадресный код. Тройки |
| C5 | Трехадресный код. Косвенные тройки |
Пример решения задачи:
-
Фрагмент кода
char[] str = “something”;
int f = 4;
char[] useless = “bad string”;
int x = f;
int j;
for (int i = 0; i < strlen(str); i++) {
scanf(“%d”, &j);
int k = x * j;
printf(“%c - %d”, str[x * j], k);
}
-
Построение промежуточного кода.
-
В виде синтаксического дерева.
-
Рис. 5.3. Представление промежуточного кода в виде синтаксического дерева
-
В виде дага.
Рис. 5.4. Представление промежуточного кода в виде дага
-
В виде четверок.
Ячейки памяти для констант
| Номер ячейки | Значение |
| D01 | “something” |
| D02 | “bad string” |
| D03 | “%d” |
| D04 | “%c - %d” |
| op | arg1 | arg2 | result | |
| (0) | assign | D01 | str | |
| (1) | assign | 4 | f | |
| (2) | assign | D02 | useless | |
| (3) | assign | f | x | |
| (4) | assign | 0 | i | |
| (5) | param | str | ||
| (6) | call | strlen | 1 | t1 |
| (7) | < | i | t1 | t2 |
| (8) | if | t2 | (10) | |
| (9) | goto | (25) | ||
| (10) | param | D03 | ||
| (11) | & | j | t3 | |
| (12) | param | t3 | ||
| (13) | call | scanf | 2 | |
| (14) | * | j | x | t4 |
| (15) | assign | t4 | k | |
| (16) | param | D04 | ||
| (17) | * | j | x | t5 |
| (18) | [] | str | t5 | t6 |
| (19) | param | t6 | ||
| (20) | param | k | ||
| (21) | call | printf | 3 | |
| (22) | + | i | 1 | t7 |
| (23) | assign | t7 | i | |
| (24) | goto | (5) | ||
| (25) |
-
В виде троек.
Ячейки памяти для констант
| Номер ячейки | Значение |
| D01 | “something” |
| D02 | “bad string” |
| D03 | “%d” |
| D04 | “%c - %d” |
| op | arg1 | arg2 | |
| (0) | assign | str | D01 |
| (1) | assign | f | 4 |
| (2) | assign | useless | D02 |
| (3) | assign | x | f |
| (4) | assign | i | 0 |
| (5) | param | str | |
| (6) | call | strlen | 1 |
| (7) | < | i | (6) |
| (8) | if | (7) | (10) |
| (9) | goto | (25) | |
| (10) | param | D03 | |
| (11) | & | j | |
| (12) | param | (11) | |
| (13) | call | scanf | 2 |
| (14) | * | j | x |
| (15) | assign | k | (14) |
| (16) | param | D04 | |
| (17) | * | j | x |
| (18) | [] | str | (17) |
| (19) | param | (18) | |
| (20) | param | k | |
| (21) | call | printf | 3 |
| (22) | + | i | 1 |
| (23) | assign | i | (22) |
| (24) | goto | (5) | |
| (25) |
-
В виде косвенных троек.
Ячейки памяти для констант
| Номер ячейки | Значение |
| D01 | “something” |
| D02 | “bad string” |
| D03 | “%d” |
| D04 | “%c - %d” |
Непосредственно тройки.
| Op | arg1 | arg2 | |
| (30) | assign | str | D01 |
| (31) | assign | f | 4 |
| (32) | assign | useless | D02 |
| (33) | assign | x | f |
| (34) | assign | i | 0 |
| (35) | param | str | |
| (36) | call | strlen | 1 |
| (37) | < | i | (36) |
| (38) | if | (37) | (40) |
| (39) | goto | (55) | |
| (40) | param | D03 | |
| (41) | & | j | |
| (42) | param | (41) | |
| (43) | call | scanf | 2 |
| (44) | * | j | x |
| (45) | assign | k | (44) |
| (46) | param | D04 | |
| (47) | * | j | x |
| (48) | [] | str | (47) |
| (49) | param | (48) | |
| (50) | param | k | |
| (51) | call | printf | 3 |
| (52) | + | i | 1 |
| (53) | assign | i | (52) |
| (54) | goto | (35) | |
| (55) |
Таблица, содержащая ссылки на тройки.
| statement | |
| (0) | (30) |
| (1) | (31) |
| (2) | (32) |
| (3) | (33) |
| (4) | (34) |
| (5) | (35) |
| (6) | (36) |
| (7) | (37) |
| (8) | (38) |
| (9) | (39) |
| (10) | (40) |
| (11) | (41) |
| (12) | (42) |
| (13) | (43) |
| (14) | (44) |
| (15) | (45) |
| (16) | (46) |
| (17) | (47) |
| (18) | (48) |
| (19) | (49) |
| (20) | (50) |
| (21) | (51) |
| (22) | (52) |
| (23) | (53) |
| (24) | (54) |
| (25) | (55) |
-
Типология команд промежуточного кода.
-
Для синтаксического дерева.
-
-
program – программа. Содержит список операторов программы.
-
op+ - список операторов программы. Содержит оператор и ссылку на следующий.
-
next_op – ссылка на следующий оператор списка. Содержит оператор и ссылку на следующий (ссылка может отсутствовать).
-
assign – оператор присваивания. Содержит объект, которому присваивается значение и значение, которое присваивается.
-
for_op – оператор итерационного цикла. Состоит из оператора присваивания, условного оператора и списка операторов тела цикла.
-
< - логическая операция «меньше». Состоит из двух объектов, которые сравниваются этим оператором.
-
strlen – оператор нахождения длины строки. Содержит строку, длину которой находит.
-
scanf – оператор ввода. Содержит список параметров.
-
param+ - список параметров функции. Содержит параметр и ссылку на следующий параметр.
-
next_param - ссылка на следующий параметр функции. Содержит параметр функции и ссылку на следующий (ссылка может отсутствовать).
-
& - оператор взятия адреса. Содержит объект, адрес которого берется.
-
* - оператор умножения. Содержит умножаемые числа.
-
printf – оператор вывода. Содержит список параметров.
-
[] – оператор обращения к элементу массива по индексу. Содержит массив, к которому осуществляется обращение и индекс запрашиваемого элемента.
-
Для дага.
Номенклатура операторов для дага ничем не отличается от описанной выше для синтаксического дерева.
-
Для четверок.
-
assign – оператор присваивания. Содержит объект, которому присваивается значение и значение, которое присваивается.
-
param – оператор занесения параметра в стек. Содержит параметр, заносимый в стек.
-
call – вызов функции. Содержит имя вызываемой функции и число параметров, извлекаемых из стека.
-
< - логическая операция «меньше». Состоит из двух объектов, которые сравниваются этим оператором.
-
if – оператор условного перехода. Содержит условие перехода и метку, по которой осуществляется переход. В случае выполнения условия осуществляется переход по метке, в противном случае осуществляется переход к следующей инструкции.
-
goto – оператор безусловного перехода. Содержит метку, по которой осуществляется переход.
-
& - оператор взятия адреса. Содержит объект, адрес которого берется.
-
* - оператор умножения. Содержит умножаемые числа.
-
[] – оператор обращения к элементу массива по индексу. Содержит массив, к которому осуществляется обращение и индекс запрашиваемого элемента.
-
+ - оператор сложения. Содержит складываемые числа.
-
Для троек.
Номенклатура операторов для троек ничем не отличается от описанной выше для четверок.
-
Для косвенных троек.
Номенклатура операторов для косвенных троек ничем не отличается от описанной выше для четверок и троек.
-
Оптимизация промежуточного кода.
Для наглядности оптимизацию проведем над исходным кодом, затем покажем, как она отразилась на каждом виде промежуточного кода.
-
Найдем общие подвыражения и заменим их, где это возможно.
char[] str = “something”;
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
