Введение в теорию построения оптимизирующих компиляторов, 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»