II.9.3. Дополнение внутреннего представления программы

Оно связано с добавлением в программу операторов и действий, не явно предусмотренных семантикой входного языка. Эти операторы и действия связаны с преобразованием типов операндов в выражениях и с передачей параметров процедуры и функций.

a:=b+c - можно отметить, что здесь выполняются 2 операции, одна – операция сложения (или конкатенации, в зависимости от типов операндов) и одна операция присвоения результата. Соответствующим образом должен быть порожден код результирующей программы. Однако не всё так очевидно. Допустим где-то перед оператором имеется описание его операнда

var

double; integer; real

Из этого описания следует, что с – вещественная переменная, b – целочисленная переменная,

а – вещественная переменная с двойной точностью. Тогда смысл приведенного оператора с точки зрения программы меняется, т.к. нельзя на прямую выполнять операции над операндами различных типов. Надо применить правило преобразования, принятого для данного языка. Это может сделать разработчик программы, но тогда преобразование типов в явном виде должен присутствовать в тексте входной программы. Это выглядит так:

a: =doublet real (b)+c);

или это может сделать компилятор. Еще разработчик может сделать так:

a: = doublet(b+trunc (c));

Этот оператор выполняет целочисленные сложения, в отличие от предыдущего, который выполняет сложение с плавающей точкой. При этом он использует преобразование типов, отличным от преобразованием языком. Результат выполнения операторов исходной программы может значительно отличаться в зависимости используемых преобразований типов. Например, если предположить, что для просмотра оператора его операнды будут b=1, c=2.5, то в результате выполнения 1го варианта оператора (операция сложения с плавающей точкой), переменная а получит значение 3.5, а в результате выполнения 2го варианта - это 3. Разраб. использ. пр. может не указывать явно используемые преобразования типов. Это выполняет код, порожденный компилятором, если эти преобразования предусмотрены семантическими соглашениями языка. Для этого в составе библиотек функций, доступных компилятору должны быть функции преобразования типов. При отсутствии явно указанных преобразований типов в этом примере будет не 2, а 4 операции:

1) преобразование целочисленной переменной b в формат вещественных чисел;

2) сложение 2ух вещественных чисел;

3) преобразование результата в вещественное число с двойной точностью;

4) присвоение результата переменной а.

Преобразование типов – это только 1 из вариантов операций, не явно добавляемых компилятором в код результирующей программы на основе семантических соглашений. Другим примером такого рода операций могут служить операции вычисления адреса, когда приходится обращаться к элементам сложных структур данных. И так, вывод: действия, выполняемые С-А существенно влияют на порождаемый оператором код результирующей программы.

 

II.9.4. Проверка смысловых норм языка программирования

Она напрямую не связана с входным языком. Это сервисная функция, которая предоставляется разработчиком программы компилятора. Эта функция обеспечивает проверку комп. соглашений выполнения которых связано со смыслом, как всей исходной программы, так и отдельных ее фрагментов. Примеры таких соглашений:

1) каждая переменная (константа) должна хотя бы 1 раз использоваться в программе;

2) каждая переменная должна быть определена до ее первого использования при любом ходе выполнения программы;

3) результат функции должен быть определен при любом ходе ее выполнения;

4) каждый оператор в исходной программе должен иметь возможность хотя бы 1 раз выполниться;

5) операторы условия и выбора должны предусматривать возможность хода выполнения программы по каждой из своих ветвей;

6) операторы цикла должны предусматривать возможность завершения цикла.

Какие конкретно соглашения будут проверяться и как они будут обрабатываться, зависит от качества компилятора. Необязательность соглашения такого типа накладывает еще одну особенность на их обработку С-А, т.е. их несоблюдение не может трактоваться как ошибка и приводить к прекращению работы компиляции. Здесь компилятор выдает предупреждение о несоблюдении одного из требований. Как на это реагировать зависит от разработчика программы.

Пример

Int f test(int a);

{ int b,c;

b=0;

c=0;

if (b=1){return a};

c=a+b;

}

Компилятор в этом моменте программы обнаружит следующие ошибки: с описана, ей присвоено значение, но она нигде не используется. Значение переменной b, присвоенной равной к 0 тоже нигде не используется. Условный оператор лишен смысла, т.к. всегда предусматривает ход выполнения только по одной ветке. Значит оператор с никогда выполнен не будет. В этом операторе if (b=1) присвоение стоит в условии. Это незапрещенно ни синтаксисом, ни семантикой в языке, но является семантической ошибкой.

 

II.10. Принципы генерации кода

Генерация объектного кода – это перевод компилятором внутр. представ. исход. пр. цепочку символу выходного языка. Она порождает результирующую объектную программу на языке ассемблера или на машинном языке. Внутр. предст. программа может иметь любую структуру в зависимости от компилятора, в то время, как результирующая программа представляет собой линейную последовательность команд, т.е. генерация должна выполнять действия, связанные с преобразованием синтаксических структур в линейные цепочки. Она выполняется после того, как сделан СА программы и все действия по подготовке генерации кода

1. распределение адресного пространства под функции и переменные;

2. проверка соответствия имен переменных, констант, функций, типов переменных в синтаксических конструкциях исходной программы и др.

Характер отображения входной программы в послед. команд выполнения генерации зависит от входного языка, от архитектуры ВС, от качества желаемого объектного кода. Генерация выполняется поэтапно на основе законных синтаксических конструкций входной программы. Компилятор выделяет такую конструкцию из текста исходной программы, порождает для нее фрагмент результирующего кода и помещает ее в код программы. Затем переходит к следующей синтаксической конструкции. Примерами типов синтаксических конструкций могут быть операторы цикла, условные операторы, операторы выбора и др. Для семантических конструкций порождается типовой результирующий код. Для этих действий компилятор использует метод, называемый синтаксическим управленческим переводом (СУ-перевод). Семантика и синтаксис языка взаимно связаны как на входе, так и на выходе. В общем случае СУ-перевод выполняет следующие действия:

1. помещение выходного потока команд, представляющих собой результат работы компилятором;

2. выдачу пользователю сообщений об ошибках;

3. порождение и выполнение команд, указывающих что некоторые действия будут произведены самим компилятором (операции, выполняемые над данными

размещенными в ТИ)

 

II.11. Оптимизация кода

Генерация кода выполняется компилятором не для всей исходной программы в целом, а последовательно для отдельных ее конструкций. Полученные для каждой синтаксической конструкции входной программы фрагменты результирующего кода также последовательно объединяются в общий текст результирующей программы. Построенный таким образом код результирующей программы может содержать лишние команды и данные, что снижает эффективность ее выполнения. Оптимизация программы – это обработка, связанная с переупоряд. и изменением операции, компилируемой пр. с целью получения более эффективной результирующей объектной программы.

Показатели эффективности:

1. объем памяти, необходимый для выполнения результирующей программы (для хранения всех ее данных и кода);

2. скорость выполнения (быстродействие) программы.

Не всегда удается удовлетворить обоим этим критериям, т.е. один улучшается, другой ухудшается. Выбирают или один из них, или комплексный, основанный на них. Различают 2 основных вида оптимизирующих преобразований:

1) преобразование исходной программы (форме ее внутреннего представления в компиляторе, независящих от результирующего объектного языка);

2) преобразования результирующей объектной программы.

Первый вид не зависит от архитектуры целевой ВС, на которой будет выполняться результирующая программа. Он основан на выполнении известных математических и логических преобразований, производимых на внутреннем представлении программы.

Методы преобразования программы зависят от типа синтаксических конструкций исходного языка:

1. линейные участки программы;

2. логические выражения;

3. циклы;

4. вызов процедуры функций.

Другие конструкции используют как машинозависящие, так и машинонезависящие методы оптимизации. Рассмотрим принцип оптимизации линейных участков программы. Это выполняемая по порядку последовательность операций, имеющая один вход и один выход. Чаще всего это последовательность вычислений, состоящих из арифметических оераций и операторов присвоения чисел переменных. Здесь применяются следующие виды оптимизирующих преобразований:

1)удаление бесполезных присвоений;

2)исключение избыточных вычислений, т.е. лишних операций;

3) свёртка операций объектного кода;

4)перестановка операций;

5) арифметические преобразования.

Удаление бесполезных присвоений заключается в том, что если в составе линейного участка программы имеется операция присвоения значения некоторой переменной А с номером i, а также операция присваивающая значение той же переменной с номером j, где i<j и ни в одной операции между i и j не используется значение переменной А, то операция присвоения с номером i является бесполезной, т.е. бесполезная операция присваивания значения дает переменной такое значение, которое нигде не используется. Такая операция может быть исключена. Бесполезными могут оказаться и любые другие операции, результат выполнения которых нигде не используется.

Например, в фрагменте программы

A:=B*C;

D:=B+C;

A:=D*C

операция присвоения A:=B*C является бесполезной и может быть удалена. Можно удалить и операцию умножения, которая тоже бесполезна. Исключение избыточных вычислений, т.е. лишних операций заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция лин. уч. с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым номером j, где j<i и никакой операнд, обработанный этой операцией, не изменился никакой операцией, имеющей порядковый номер между i и j. Свертка объектного кода – это выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны. Примером свертки является вычисленной выражение, где все числа являются константой.

Более сложные примеры – это варианты алгоритма свертки, который учитывает и переменные, и функции, значения которых уже известны. Не всегда компилятору удается выполнить свертку, даже если выражение допускает ее выполнение. Например, выражение

A:=R*B*C*3

может быть преобразовано к виду

A:=6*B*C

в порядке вычислений

A:=2*(B*(C*3)) это неочевидно. Для более эффективного выполнения свертки можно совместить ее выполнение с другим методом перестановкой операций. Перестановка операций заключается в изменение в порядке следований операций, которая может повысить эффективность программы, но не будет влиять на конечный результат вычислений.

Например, A:=2*B*3*C можно переставить без изменения конечного результата и выполнить в таком порядке

A:=(2*3)*(B*C).

Тогда представляется возможность выполнить свертку и сократить выполнение операций.

Арифметические преобразования предоставляют собой выполнение изменения характера и порядка следования операций на основании известных алгебраических и логических тождеств.

Например:

A:=B*C+B*D может быть выполнено A:=B*(C+D)

Конечный результат при этом не изменится, но объектный код будет содержать на одну операцию умножения меньше.