Введение в теорию построения оптимизирующих компиляторов, 01 лекция (от 19 сентября)
Материал из eSyr's wiki.
Параллельное чернопрограммирование 19.09.06
Первая лекция
//Лектор не знает, как называется спецкурс
Пусть будет: Введение в построение оптимизирующих компиляторов
Программа:
Будет рассмотрен весь компилятор, рассмотрены алгоритмы, им применяемы, оптимизация, генерация кода.
Типичная структура компилятора:
Компилятор – некоторая программа, которая получает текст на языке высокого уровня b на выходе получаем текст на языке ассемблера для целевой платформы. Причем, для языка Си, будем рассматривать входной программу, получаемую после работы препроцессора
Самые важные архитектуры: IA32 i386+
В институте ведутся работы по более глубокому портированию GCC на IA64.
X86-64 – AMD 64
SPARC, PowerPC. IA32, x86-64 – CISC, IA-64 – VLIV процессоры, SPARC, PPC – RISC.
Представление программы:
HIR – high level
MIR - midlevel
LIR – low level
По мере движения вниз ослабевает специфика языка. С другой стороны, при движении сверху вниз увеличивается специфика аппаратуры. Наибольший интерес имеет представление среднего уровня. Условно HIR соотв front-end, MIR – optimizer, LIR – back-end. Условно программу можно рассматривать как дерево разбора. Для предст низкого уровня можно рассм. Программу на языке ассемблера.
Что бывает в оптимизаторе:
1) внутрипроцедурный анализ
Анализ потока управления (control-flow analysis) – семейство алгоритмов, разные виды анализа. В чем задача – по программе построить граф потока управления, отражающий структуру передач управления. На первой стадии будем считать, что каждая функция будет рассматриваться отдельно. Результатом является разбиение на базовые блоки и построение потока управления, отражения, переходы между блоками. Анализ недостижимых ветвей, анализ живых переменных, ..., анализ алиасов. Он обходим для языков, где они есть, то есть возм. Адресоваться к одной области памяти разным переменным.
Анализ алиасов необходим, если, например:
a=1
p=&a;
*p=2;
b=a;
В этом премере ошибочно полагать, что b=1.
Платформенно-независимая оптимизация. Свёртка констант, свёртка юю, constant folding, constant propagation, copy propogation, lood invation, code motion, common subprecision eliminating
Back-end:
register allocation
instruction selection – для каждой инструкции нашего представления нужно выбрать какую-нибудь инструкцию машинного представления.
Instruction scheduling –
r3 <- r4+к5
к2Б-ьуь
к1Б-к2+к3
и хотелось бы отнести загрузку данных отдельно от арифметики.
Const folding, const propagation, CSE выполняются много раз, но они независимы. В back-end алгоритмы противоречат друг-другу. Например, при scheduling хотелось бы распределять регистры, но... . В результате хотелось бы написать back-end так, чтобы он делал всё. Но подобное трудно разрабатывать и поддерживать. Посему алгоритмов хороших нет.
На этапе back-end много целевых платформ, и он разный. Соответственно, back-end, заточенный под одну платформу, плохо работает на другой.
Прежде, чем перейти к рассмотрению оптимизаторов и back-end, рассмотрим front-end.
Frond-end
Задача – построить внутреннее построение программы, которое легко анализировать. В этом этапе выделяются следующие этапы:
лексический
семантический
синтаксический
Для написания лекс и синт анализаторов имеются хорошие инструменты. Для семант инструменты не столь хороши, но там и задача не столь формализована.
На вход компилятору поступает набор символов, по которому нужно построить таблицу символов, порезать комментарии и быть готовым отдать на синт. Анализ.
Для лекс анализаторов существуют инструменты, при помощи которых этот процесс можно ускорить и автоматизировать.
Flex
Как выглядит спецификация:
%{ - произвольный код на языке С
%}
Далее идут объявления для flex, в которых объявляются нач. состояни,я символы..
%% - спецификация рег выр
<рег. Выр.> {код на Си}
...
%%
произвольный код на Си
Что можно писать в кач-ве рег. Выр.
<рег. Выр.>:
a – рег выр, соотв этому символу
. - любой символ
«ab» - соотв строке символов, в кавычках, в данном случае ab
[0-9], [abd-g1-5] – множество символов
\n, \t – спецсимволы
[^0-9] – все символы кроме диапазона, включая симолы перехода на след. Строку
Если есть r1, r2, то их можно конкатенировать r1r2
r1|r2 – или r1 или r2
r* - повторение 0 или более раз
r+ - 1 или более раз
r? - 0 или 1 раз
() - используютсмя для группировки
r{2,5} – рег. Выр., повтореное от 2 до 5 раз
^r – может встречаться только в начале строки
r$ - только в конце строки
r/s – r, только если за ним s (trailing context)
С использованием рег. Выр. Модно описать любой язык в несколько строчек.
Рассмотрим паскалеподобный язык.
%%
«{»[^{]*«}» {обновить информацию о текущей позиции. Но \n или \t нелинейно изменяют позицию в файлк, но есть yytext и yyleng, где есть указатель на лексему и его длина. Для решения поблемы можно просмотреть все символы:
for (int i=0; i<yyleng; i++)
{
if (yytext[i]=='\n')
{
yylval.line++;
yylval.col=0;
}
if (yytext[i]=='\t')
{
yylval.col=(yylval.col+8)&!7;
}
}
}//комментарий
«'»([^']|)*«'» {yylval.num=put_to_string_table(yytext, yyleng); return TOK_STRING – константы берутся из интерфейсных файлов} //строка
Регулярные выражение жадные, поэтому распознаётся наиболее длинная строка, которая может быть рассмотрена как это выражение, посему 'abcde' будет распознана как одна строка, а ене две
[Bb][Ee][Gg][Ii][Nn] {...} //ключевое слово begin вне зависимости от регистра. Так как стоит раньше, чем опр идентификатора.
[A-Za-z][A-Za-z0-9]* {...} //идентификатор
([0-9]+([.][0-9]+)?[e](+|-)?[0-9]+)|([0-9]+[.][0-9]+([e](+|-)?[0-9]+)?) {...} //вещ число
Лекс анализ вызывается обычно как подпрограмма. При генерации flex она называется int yylex();. Она возвращает номер лексемы или 0 в случае конце файла. Существует глобальная переменная yylval, тип этой переменной определяется из синт анализа, и в неё сканер пишет дополнительные аттрибуты, например, позиция в тексте, номер строки и т. д.
Для чего нужна таблица идентификаторов: поскольку номер целое число, то при наличии таблицы идентификаторов их удобно идентифицировать и работать с ними. Потом сканер строит свои таблицы в соотв с областями видимости.
Flex необязательно можно использовать дл генерации сканеров. Можно и синтаксический анализатор.
Есть понятие стека состояний, для работы с ним существуют комманды
yy_push_stack
yy_pop_stack
yy_top_stack
Это позволяет посмотреть вперед, не найти, что нужно, и откатиться назад.
Unput(c) – возвращает символ во входной поток
input() – выдаёт символ.
Можно выполнять дополн. Действия, когда рег выр распознано.
yyless(m) – возвращает поток символы, начиная с m+1:
«x=» {yyles(1); return TOK_VAR;}
«x» {return TOK_MUL}
Извращённые функции нужны для извращённых языков
«{» { BEGIN(cmt);}
<cmt>«}» {BEGIN(INITIAL);}
<cmt><<EOF>> {error}
начальные усовия нужно объявить в блоке Сишного кода (%{ ... %})
Можно определить
[A-Za-z] ID
[0-9] D
и тогда использовать их в определении рег выр
для того, чтобы всё было хорошо, нужно сделать
#include «parser.h»
Введение в теорию построения оптимизирующих компиляторов
Календарь
вт | вт | вт | вт | вт | |
Сентябрь
| 19 | 26 | |||
Октябрь
| 10 | 24 | 31 | ||
Ноябрь
| 07 | 14 | 21 | ||
Декабрь
| 05 | 12 |