Учебный компилятор (для лекций по курсу "Разработка компиляторов"):
список заданий
Во всех заданиях требуется расширить возможности
учебного компилятора "TinyСС" или улучшить качество генерируемого
ассемблерного кода. После задачи указана примерная оценка ее
сложности по трехбальной шкале: (1) простая, (2) средняя, (3) сложная.
Задачи на оптимизацию выполняются только на уровне
базового блока (локальная оптимизация), за исключением
задачи на оптимизацию переходов.
Одна задача принимается не больше чем у двух студентов.
-
Добавить свертывание константных выражений на стадии синтаксических
деревьев, т.е. после генерации парсером деревьев выражений, но
перед генерацией RTL-кода для выражения. К примеру, выражение
"2+3+x+5" должно сворачиваться к "x+10", выражение "x+2*8" -- к "x+16".
(1)
-
Добавить в язык операции "+=", "-=", "*=", "/=" ("увеличить на",
"уменьшить на", "домножить на", "разделить на"). (1)
-
Оптимизация: добавить нахождение общих подвыражений, выполняется
на уровне RTL представления, т.е. после генерации RTL кода и
перед генерацией ассемблерного кода функции. Общие подвыражения
ищутся только в пределах базового блока. Пусть, например,
псевдорегистру R[123] присвоено некоторое выражение. Если ниже по тексту
(в пределах данного базового блока) другому псевдорегистру, например
R[234], присвоено то же самое выражение, то всюду в тексте можно заменить
ссылки на регистр R[234] ссылками на регистр R[123]. При этом команду,
вычисляющую регистр R[234], можно удалить. (3)
-
Оптимизация: добавить удаление "мертвых" выражений.
Например, если в пределах одного базового блока выполняются
две строки "x = 2" и "x = 3", то первую строку можно удалить. (3)
-
Оптимизация: добавить оптимизацию переходов, выполняется
на уровне RTL кода. Если после метки перехода идет "goto"
на другую метку, то можно сразу перейти на нее, сэкономив
команду перехода. Также нужно удалить команды переходов
на следующую строку и строки с метками, если на них нет переходов. (1)
-
Перенести учебный компилятор на Win32. Переделать генерацию
ассемблерного кода с GNU Ассемблера "as", который использует
синтаксис AT&T, на Ассемблер Microsoft "masm", который использует
синтаксис Intel. (2)
-
Добавить инициализацию локальных переменных в операторах
описаний, например "int x = (y+z)*2;". Инициализируются
только простые переменные, не массивы. (2)
-
Добавить инициализацию глобальных переменных,
включая простые переменные и массивы (как в Cи).
Массив типа "char" может инициализироваться
либо последовательностью символов или целых чисел,
например "char a[10] = {1, 2, 'a', '\n'};", либо
строковой константой, например 'char a[] = "abcd";'. (2)
-
Добавить указатели на функции. Синтаксис должен соответствовать Cи,
за исключением того, что можно присваивать друг другу указатели
разных типов. (3)