Выделение общих подвыражений
Выделение общих подвыражений относится к области оптимизации программ. В общем случае трудно (или даже невозможно) провести границу между оптимизацией и «качественной трансляцией». Оптимизация - это и есть качественная трансляция. Обычно термин «оптимизация» употребляют, когда для повышения качества программы используют ее глубокие преобразования такие, например, как перевод в графовую форму для изучения нетривиальных свойств программы.
В этом смысле выделение общих подвыражений - одна из простейших оптимизаций. Для ее осуществления требуется некоторое преобразование программы, а именно построение ориентированного ациклического графа, о котором говорилось в главе, посвященной промежуточным представлениям.
Линейный участок - это последовательность операторов, в которую управление входит в начале и выходит в конце без остановки и перехода изнутри.
Рассмотрим дерево линейного участка, в котором вершинами служат операции, а
потомками - операнды. Будем говорить, что две вершины образуют общее подвыражение, если поддеревья для них совпадают, т.е. имеют одинаковую структуру и, соответственно, одинаковые операции во внутренних вершинах и одинаковые операнды в листьях. Выделение общих подвыражений позволяет генерировать для них код один раз, хотя может привести и к некоторым трудностям, о чем вкратце будет сказано ниже.
Выделение общих подвыражений проводится на линейном участке и
основывается на двух положениях.
1. Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания. Для этого каждая переменная снабжается счетчиком. Вначале счетчики всех переменных устанавливаются равными 0. При каждом присваивании переменной ее счетчик увеличивается на 1.
2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх
слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная op; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op.
Если имеется выражение, связанное с op и такое, что его левый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение
общим с найденным и в новом выражении запоминаем указатель на найденное общее выражение. Базисом построения служит переменная: если операндами обоих выражений являются одинаковые переменные с одинаковыми счетчиками, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заносится в список операций, связанных с op.
Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные
переменные:
Table - таблица переменных; для каждой переменной хранится ее счетчик (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в правой части (Last);
OpTable - таблица списков (типа LisType) общих подвыражений, связанных с каждой операцией. Каждый элемент списка хранит указатель на вершину дерева (поле Addr) и продолжение списка (поле List).
С каждой вершиной дерева выражения связана запись типа NodeType, со следующими полями:
Left - левый
потомок вершины,
Right - правый потомок вершины,
Comm - указатель на предыдущее общее подвыражение,
Flag - признак, является ли поддерево общим подвыражением,
Varbl - признак, является ли вершина переменной,
VarCount - счетчик переменной.
Выделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут Entry нетерминала Variable дает указатель на переменную в таблице Table. Атрибут Val символа Op дает код операции. Атрибут Node символов IntExpr и Assignment дает указатель на запись типа NodeType соответствующего
нетерминала.
|
RULE Assignment ::= Variable IntExpr SEMANTICS Table[Entry].Count=Table[Entry].Count+1. // Увеличить счетчик присваиваний переменной RULE IntExpr ::= Variable SEMANTICS if ((Table[Entry].Last!=NULL) // Переменная уже была использована && (Table[Entry].Last->VarCount == Table[Entry].Count )) // С тех пор переменной не было присваивания {Node->Flag=true; // Переменная - общее подвыражение Node->Comm= Table[Entry].Last; // Указатель на общее подвыражение } else Node->Flag=false; Table[Entry].Last=Node; // Указатель на последнее использование переменной Node->VarCount= Table[Entry].Count; // Номер использования переменной Node->Varbl=true. // Выражение - переменная RULE IntExpr ::= Op IntExpr IntExpr SEMANTICS LisType * L; //Тип списков операции if ((Node->Flag) && (Node->Flag)) // И справа, и слева - общие подвыражения {L=OpTable[Val]; // Начало списка общих подвыражений для операции while (L!=NULL) if ((Node==L->Left) && (Node==L->Right)) // Левое и правое поддеревья совпадают break; else L=L->List;// Следующий элемент списка } else L=NULL; //Не общее подвыражение Node->Varbl=false; // Не переменная Node->Comm=L; //Указатель на предыдущее общее подвыражение или NULL if (L!=NULL) {Node->Flag=true; //Общее подвыражение Node->Left=Node; // Указатель на левое поддерево Node->Right=Node; // Указатель на правое поддерево } else {Node->Flag=false; // Данное выражение не может рассматриваться как общее // Если общего подвыражения с данным не было, // включить данное в список для операции L=alloc(sizeof(struct LisType)); L->Addr=Node; L->List=OpTable[Val]; OpTable[Val]=L; }. |
Рассмотрим теперь некоторые простые правила распределения регистров при наличии общих подвыражений. Если число регистров ограничено, можно выбрать один из следующих двух вариантов.
1. При обнаружении
общего подвыражения с подвыражением в уже просмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да, и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново.
2. Вводим еще один проход. На первом проходе распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево общее с уже
вычисленным ранее, но значение регистра потеряно, то в такой вершине на втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева. Поскольку стоимость команды MOVE известна, можно сравнить стоимости и принять оптимальное решение: пометить предыдущую вершину для
сброса либо вычислять поддерево полностью.
