Введение в теорию построения оптимизирующих компиляторов, 01 лекция (от 19 сентября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1284 участника 202.106.212.226 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | <P STYLE="margin-bottom: 0cm">Параллельное чернопрограммирование |
- | + | 19.09.06</P> | |
- | + | <P STYLE="margin-bottom: 0cm"><BR> | |
- | + | </P> | |
+ | <P STYLE="margin-bottom: 0cm">Первая лекция</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">//Лектор не знает, как называется | ||
+ | спецкурс</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Пусть будет: Введение в построение | ||
+ | оптимизирующих компиляторов</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Программа:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Будет рассмотрен весь компилятор, | ||
+ | рассмотрены алгоритмы, им применяемы, оптимизация, генерация кода.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Типичная структура компилятора:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Компилятор – некоторая программа, | ||
+ | которая получает текст на языке высокого уровня b на выходе получаем | ||
+ | текст на языке ассемблера для целевой платформы. Причем, для языка | ||
+ | Си, будем рассматривать входной программу, получаемую после работы | ||
+ | препроцессора</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Самые важные архитектуры: IA32 i386+</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В институте ведутся работы по более | ||
+ | глубокому портированию GCC на IA64.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">X86-64 – AMD 64</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">SPARC, PowerPC. IA32, x86-64 – | ||
+ | CISC, IA-64 – VLIV процессоры, SPARC, PPC – RISC.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Представление программы:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">HIR – high level</P> | ||
+ | <P STYLE="margin-bottom: 0cm">MIR - midlevel</P> | ||
+ | <P STYLE="margin-bottom: 0cm">LIR – low level</P> | ||
+ | <P STYLE="margin-bottom: 0cm">По мере движения вниз ослабевает | ||
+ | специфика языка. С другой стороны, при движении сверху вниз | ||
+ | увеличивается специфика аппаратуры. Наибольший интерес имеет | ||
+ | представление среднего уровня. Условно HIR соотв front-end, MIR – | ||
+ | optimizer, LIR – back-end. Условно программу можно | ||
+ | рассматривать как дерево разбора. Для предст низкого уровня можно | ||
+ | рассм. Программу на языке ассемблера.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Что бывает в оптимизаторе:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">1) внутрипроцедурный анализ</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Анализ потока управления (control-flow | ||
+ | analysis) – семейство алгоритмов, разные виды анализа. В чем | ||
+ | задача – по программе построить граф потока управления, | ||
+ | отражающий структуру передач управления. На первой стадии будем | ||
+ | считать, что каждая функция будет рассматриваться отдельно. | ||
+ | Результатом является разбиение на базовые блоки и построение потока | ||
+ | управления, отражения, переходы между блоками. Анализ недостижимых | ||
+ | ветвей, анализ живых переменных, ..., анализ алиасов. Он обходим для | ||
+ | языков, где они есть, то есть возм. Адресоваться к одной области | ||
+ | памяти разным переменным. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Анализ алиасов необходим, если, | ||
+ | например:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">a=1</P> | ||
+ | <P STYLE="margin-bottom: 0cm">p=&a;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">*p=2;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">b=a;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">В этом премере ошибочно полагать, что | ||
+ | b=1.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Платформенно-независимая оптимизация. Свёртка | ||
+ | констант, свёртка юю, constant folding, constant propagation, copy | ||
+ | propogation, lood invation, code motion, common subprecision | ||
+ | eliminating</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Back-end:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">register allocation</P> | ||
+ | <P STYLE="margin-bottom: 0cm">instruction selection – для | ||
+ | каждой инструкции нашего представления нужно выбрать какую-нибудь | ||
+ | инструкцию машинного представления.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Instruction scheduling – | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">r3 <- r4+к5</P> | ||
+ | <P STYLE="margin-bottom: 0cm">к2Б-ьуь</P> | ||
+ | <P STYLE="margin-bottom: 0cm">к1Б-к2+к3</P> | ||
+ | <P STYLE="margin-bottom: 0cm">и хотелось бы отнести загрузку данных | ||
+ | отдельно от арифметики. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Const folding, const propagation, CSE | ||
+ | выполняются много раз, но они независимы. В back-end алгоритмы | ||
+ | противоречат друг-другу. Например, при scheduling хотелось бы | ||
+ | распределять регистры, но... . В результате хотелось бы написать | ||
+ | back-end так, чтобы он делал всё. Но подобное трудно разрабатывать и | ||
+ | поддерживать. Посему алгоритмов хороших нет.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">На этапе back-end много целевых | ||
+ | платформ, и он разный. Соответственно, back-end, заточенный под одну | ||
+ | платформу, плохо работает на другой.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Прежде, чем перейти к рассмотрению | ||
+ | оптимизаторов и back-end, рассмотрим front-end.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><B>Frond-end</B></P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Задача – | ||
+ | построить внутреннее построение программы, которое легко | ||
+ | анализировать. В этом этапе выделяются следующие этапы:</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">лексический</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">семантический</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">синтаксический</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Для написания лекс | ||
+ | и синт анализаторов имеются хорошие инструменты. Для семант | ||
+ | инструменты не столь хороши, но там и задача не столь формализована.</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">На вход | ||
+ | компилятору поступает набор символов, по которому нужно построить | ||
+ | таблицу символов, порезать комментарии и быть готовым отдать на синт. | ||
+ | Анализ.</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Для лекс | ||
+ | анализаторов существуют инструменты, при помощи которых этот процесс | ||
+ | можно ускорить и автоматизировать.</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Flex</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Как выглядит | ||
+ | спецификация:</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">%{ - произвольный | ||
+ | код на языке С</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">%}</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Далее идут | ||
+ | объявления для flex, в которых объявляются нач. состояни,я символы..</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">%% - спецификация | ||
+ | рег выр</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><рег. Выр.> | ||
+ | {код на Си}</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">...</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">%%</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">произвольный код | ||
+ | на Си</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Что можно писать в | ||
+ | кач-ве рег. Выр.</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><рег. Выр.>:</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">a – рег выр, | ||
+ | соотв этому символу</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">. - любой символ</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">«ab» - | ||
+ | соотв строке символов, в кавычках, в данном случае ab</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">[0-9], [abd-g1-5] | ||
+ | – множество символов</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">\n, \t – | ||
+ | спецсимволы</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">[^0-9] – все | ||
+ | символы кроме диапазона, включая симолы перехода на след. Строку</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Если есть r1, r2, | ||
+ | то их можно конкатенировать r1r2</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r1|r2 – или | ||
+ | r1 или r2</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r* - повторение 0 | ||
+ | или более раз | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r+ - 1 или более | ||
+ | раз</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r? - 0 или 1 раз</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">() - используютсмя | ||
+ | для группировки</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r{2,5} – | ||
+ | рег. Выр., повтореное от 2 до 5 раз</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">^r – может | ||
+ | встречаться только в начале строки</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r$ - только в | ||
+ | конце строки</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">r/s – r, | ||
+ | только если за ним s (trailing context)</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">С использованием | ||
+ | рег. Выр. Модно описать любой язык в несколько строчек. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium">Рассмотрим | ||
+ | паскалеподобный язык.</P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">%%</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">«{»[^{]*«}» | ||
+ | {обновить информацию о текущей позиции. Но \n или \t нелинейно | ||
+ | изменяют позицию в файлк, но есть yytext и yyleng, где есть указатель | ||
+ | на лексему и его длина. Для решения поблемы можно просмотреть все | ||
+ | символы: </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">for | ||
+ | (int i=0; i<yyleng; i++) </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">{</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> if | ||
+ | (yytext[i]=='\n') </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> {</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> yylval.line++; | ||
+ | </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> yylval.col=0;</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> } | ||
+ | </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> if | ||
+ | (yytext[i]=='\t') </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> {</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> yylval.col=(yylval.col+8)&!7;</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace"> }</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">} | ||
+ | </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">}//комментарий</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">«'»([^']|'')*«'» | ||
+ | {yylval.num=put_to_string_table(yytext, yyleng); return TOK_STRING – | ||
+ | константы берутся из интерфейсных файлов} //строка </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Регулярные | ||
+ | выражение жадные, поэтому распознаётся наиболее длинная строка, | ||
+ | которая может быть рассмотрена как это выражение, посему 'abc''de' | ||
+ | будет распознана как одна строка, а ене две</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">[Bb][Ee][Gg][Ii][Nn] | ||
+ | {...} //ключевое слово begin вне зависимости от регистра. Так как | ||
+ | стоит раньше, чем опр идентификатора. </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">[A-Za-z][A-Za-z0-9]* | ||
+ | {...} //идентификатор</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">([0-9]+([.][0-9]+)?[e](+|-)?[0-9]+)|([0-9]+[.][0-9]+([e](+|-)?[0-9]+)?) | ||
+ | {...} //вещ число</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Лекс | ||
+ | анализ вызывается обычно как подпрограмма. При генерации flex она | ||
+ | называется int yylex();. Она возвращает номер лексемы или 0 в случае | ||
+ | конце файла. Существует глобальная переменная yylval, тип этой | ||
+ | переменной определяется из синт анализа, и в неё сканер пишет | ||
+ | дополнительные аттрибуты, например, позиция в тексте, номер строки и | ||
+ | т. д. </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Для | ||
+ | чего нужна таблица идентификаторов: поскольку номер целое число, то | ||
+ | при наличии таблицы идентификаторов их удобно идентифицировать и | ||
+ | работать с ними. Потом сканер строит свои таблицы в соотв с областями | ||
+ | видимости.</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Flex | ||
+ | необязательно можно использовать дл генерации сканеров. Можно и | ||
+ | синтаксический анализатор.</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Есть | ||
+ | понятие стека состояний, для работы с ним существуют комманды</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">yy_push_stack</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">yy_pop_stack</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">yy_top_stack</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Это | ||
+ | позволяет посмотреть вперед, не найти, что нужно, и откатиться назад.</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Unput(c) | ||
+ | – возвращает символ во входной поток</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">input() | ||
+ | – выдаёт символ.</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Можно | ||
+ | выполнять дополн. Действия, когда рег выр распознано.</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">yyless(m) | ||
+ | – возвращает поток символы, начиная с m+1:</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">«x=» | ||
+ | {yyles(1); return TOK_VAR;}</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">«x» | ||
+ | {return TOK_MUL}</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif"><FONT SIZE=3><FONT FACE="Times New Roman">Извращённые | ||
+ | функции нужны для извращённых языков</FONT></FONT> </FONT> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">«{» | ||
+ | { BEGIN(cmt);}</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif"><cmt>«}» | ||
+ | {BEGIN(INITIAL);}</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif"><cmt><<EOF>> | ||
+ | {error}</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">начальные | ||
+ | усовия нужно объявить в блоке Сишного кода (%{ ... %})</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">Можно | ||
+ | определить</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">[A-Za-z] | ||
+ | ID</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">[0-9] | ||
+ | D</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">и | ||
+ | тогда использовать их в определении рег выр</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">для | ||
+ | того, чтобы всё было хорошо, нужно сделать</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">#include | ||
+ | «parser.h»</FONT></P> | ||
+ | <P STYLE="margin-bottom: 0cm; font-weight: medium"><BR> | ||
+ | </P> | ||
+ | |||
+ | {{Введение в теорию построения оптимизирующих компиляторов}} | ||
+ | {{Lection-stub}} |
Текущая версия
Параллельное чернопрограммирование 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 |