8.8. common7 (1134684)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

8.8. Выделение общих подвыражений

Выделение общих подвыражений проводится на линейном участке и основывается на двух положениях.

1. Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания. Для этого каждая переменная снабжается счетчиком. Вначале номера всех переменных устанавливаются равными 0. При каждом присваивании переменной ее номер увеличивается на 1.

2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная 'op'; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op. Если имеется выражение, связанное с op и такое, что его левый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение общим с найденным и в новом выражении запоминаем указатель на найденное общее выражение. Базисом построения служит переменная: если операндами обоих выражений являются одинаковые переменные с одинаковыми счетчиками, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заносится в список операций, связанных с op (рис. 8.27).

OP

Рис.8.27

Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные:

Table - таблица переменных; для каждой переменной хранится ее номер (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в правой части (Last);

OpTable - таблица списков общих подвыражений, связанных с каждой операцией (Addr - указатель на вершину дерева, List - продолжение списка);

С каждой вершиной дерева выражения связана запись (Тип LisType):

struct NodeType {
Left -- левый потомок вершины;
Right -- правый потомок вершины;
Comm -- указатель на предыдущее общее подвыражение;
Flag -- признак, является ли поддерево
общим подвыражением;
Varbl -- признак, является ли вершина переменной;
VarCount -- счетчик переменной;
}

Все общие подвыражения собраны в список (с типом элемента LisType), начинающийся с OpTable[Op], как это изображено на рис. 8.28.

OpTable

OP

Рис. 8.28

Выделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут Entry нетерминала Variable дает указатель на переменную в таблице Table. Атрибут Val символа Op дает код операции. Атрибут Node символов IntExpr и Assignment дает указатель на запись типа NodeType соответствующего нетерминала.

RULE
Assignment ::= Variable IntExpr
SEMANTICS
Table[Entry<1>].Count=Table[Entry<1>].Count+1.
//Увеличить счетчик присваиваний переменной

RULE
IntExpr ::= Variable
SEMANTICS
if ((Table[Entry<1>].Last!=NULL)
// Переменная уже была использована
&& (Table[Entry<1>].Last->Node<0>->VarCount
== Table[Entry<1>].Count ))
//С тех пор переменной не было присваивания
{Node<0>->Flag=true;
//Переменная - общее подвыражение
Node<0>->Comm= Table[Entry<1>].Last;
//Указатель на общее подвыражение
}
else Node<0>->Flag=false;
Table[Entry<1>].Last=Node<0>;
//Указатель на последнее использование переменной
Node<0>->VarCount= Table[Entry<1>].Count;
//Номер использования переменной
Node<0>->Varbl=true. //Выражение – переменная

RULE
IntExpr ::= Op IntExpr IntExpr
SEMANTICS
LisType * L; //Тип списков операции
if ((Node<2>->Flag) && (Node<3>->Flag))
// И справа, и слева - общие подвыражения
{L=OpTable[Val<1>];
// Начало списка общих подвыражений для операции
while (L!=NULL)
if ((Node<2>==L->Left)
&& (Node<3>==L->Right))
// Левое и правое поддеревья совпадают
break;
else L=L->List;//Следующий элемент списка
}
else L=NULL; //Не общее подвыражение

Node<0>->Varbl=false; //Не переменная
Node<0>->Comm=L;
//Указатель на предыдущее общее подвыражение или NULL
if (L!=NULL)
{Node<0>->Flag=true; //Общее подвыражение
Node<0>->Left=Node<2>;
// Указатель на левое поддерево
Node<0>->Right=Node<3>;
// Указатель на правое поддерево
}
else {Node<0>->Flag=false;
// Данное выражение не может рассматриваться как общее
// Если общего подвыражения с данным не было,
// включить данное в список для операции
L=new LisType();
L->Addr=Node<0>;
L->List=OpTable[Val<1>];
OpTable[Val<1>]=L;
}.

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

1. При обнаружении общего подвыражения с подвыражением в уже просмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да, и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново.

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

155

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций