Введение в теорию построения оптимизирующих компиляторов, 01 лекция (от 19 сентября)

Материал из eSyr's wiki.

Версия от 17:35, 3 февраля 2008; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Параллельное чернопрограммирование 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


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

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы