Введение в теорию построения оптимизирующих компиляторов, 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:
-
== From Ebaums Inc to MurkLoar. ==
+
<P STYLE="margin-bottom: 0cm">Параллельное чернопрограммирование
-
We at EbaumsWorld consider you as disgrace of human race.
+
19.09.06</P>
-
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
+
<P STYLE="margin-bottom: 0cm"><BR>
-
Dig yourself a grave - you will need it.
+
</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">Компилятор &ndash; некоторая программа,
 +
которая получает текст на языке высокого уровня 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 &ndash; AMD 64</P>
 +
<P STYLE="margin-bottom: 0cm"><BR>
 +
</P>
 +
<P STYLE="margin-bottom: 0cm">SPARC, PowerPC. IA32, x86-64 &ndash;
 +
CISC, IA-64 &ndash; VLIV процессоры, SPARC, PPC &ndash; RISC.</P>
 +
<P STYLE="margin-bottom: 0cm"><BR>
 +
</P>
 +
<P STYLE="margin-bottom: 0cm">Представление программы:</P>
 +
<P STYLE="margin-bottom: 0cm">HIR &ndash; high level</P>
 +
<P STYLE="margin-bottom: 0cm">MIR - midlevel</P>
 +
<P STYLE="margin-bottom: 0cm">LIR &ndash; low level</P>
 +
<P STYLE="margin-bottom: 0cm">По мере движения вниз ослабевает
 +
специфика языка. С другой стороны, при движении сверху вниз
 +
увеличивается специфика аппаратуры. Наибольший интерес имеет
 +
представление среднего уровня. Условно HIR соотв front-end, MIR &ndash;
 +
optimizer, LIR &ndash; 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) &ndash; семейство алгоритмов, разные виды анализа. В чем
 +
задача &ndash; по программе построить граф потока управления,
 +
отражающий структуру передач управления. На первой стадии будем
 +
считать, что каждая функция будет рассматриваться отдельно.
 +
Результатом является разбиение на базовые блоки и построение потока
 +
управления, отражения, переходы между блоками. Анализ недостижимых
 +
ветвей, анализ живых переменных, ..., анализ алиасов. Он обходим для
 +
языков, где они есть, то есть возм. Адресоваться к одной области
 +
памяти разным переменным.
 +
</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=&amp;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 &ndash; для
 +
каждой инструкции нашего представления нужно выбрать какую-нибудь
 +
инструкцию машинного представления.</P>
 +
<P STYLE="margin-bottom: 0cm">Instruction scheduling &ndash;
 +
</P>
 +
<P STYLE="margin-bottom: 0cm">r3 &lt;- 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">Задача &ndash;
 +
построить внутреннее построение программы, которое легко
 +
анализировать. В этом этапе выделяются следующие этапы:</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">&lt;рег. Выр.&gt;
 +
{код на Си}</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">&lt;рег. Выр.&gt;:</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">a &ndash; рег выр,
 +
соотв этому символу</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">. - любой символ</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">&laquo;ab&raquo; -
 +
соотв строке символов, в кавычках, в данном случае ab</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">[0-9], [abd-g1-5]
 +
&ndash; множество символов</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">\n, \t &ndash;
 +
спецсимволы</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">[^0-9] &ndash; все
 +
символы кроме диапазона, включая симолы перехода на след. Строку</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 &ndash; или
 +
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} &ndash;
 +
рег. Выр., повтореное от 2 до 5 раз</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">^r &ndash; может
 +
встречаться только в начале строки</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">r$ - только в
 +
конце строки</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium">r/s &ndash; 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">&laquo;{&raquo;[^{]*&laquo;}&raquo;
 +
{обновить информацию о текущей позиции. Но \n или \t нелинейно
 +
изменяют позицию в файлк, но есть yytext и yyleng, где есть указатель
 +
на лексему и его длина. Для решения поблемы можно просмотреть все
 +
символы: </FONT>
 +
</P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Courier New, monospace">for
 +
(int i=0; i&lt;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)&amp;!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">&laquo;'&raquo;([^']|'')*&laquo;'&raquo;
 +
{yylval.num=put_to_string_table(yytext, yyleng); return TOK_STRING &ndash;
 +
константы берутся из интерфейсных файлов} //строка </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)
 +
&ndash; возвращает символ во входной поток</FONT></P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">input()
 +
&ndash; выдаёт символ.</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)
 +
&ndash; возвращает поток символы, начиная с m+1:</FONT></P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">&laquo;x=&raquo;
 +
{yyles(1); return TOK_VAR;}</FONT></P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">&laquo;x&raquo;
 +
{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">&laquo;{&raquo;
 +
{ BEGIN(cmt);}</FONT></P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">&lt;cmt&gt;&laquo;}&raquo;
 +
{BEGIN(INITIAL);}</FONT></P>
 +
<P STYLE="margin-bottom: 0cm; font-weight: medium"><FONT FACE="Times New Roman, serif">&lt;cmt&gt;&lt;&lt;EOF&gt;&gt;
 +
{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
 +
&laquo;parser.h&raquo;</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»



Введение в теорию построения оптимизирующих компиляторов

01 02 03 04 05 06 07 08 09 10

Календарь

вт вт вт вт вт
Сентябрь
    19 26
Октябрь
  10   24 31
Ноябрь
07 14 21
Декабрь
05 12


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Получено с http://esyr.us/wiki/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8E_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_01_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_19_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29
Личные инструменты
Разделы