KNOW INTUIT, Лекция, Генериране на код

Маркиране на общи подизрази

Изборът на общи подизрази принадлежи към областта на програмната оптимизация. Като цяло е трудно (или дори невъзможно) да се направи граница между оптимизация и "качествен превод". Оптимизация - това е качествено предаване. Обикновено терминът "оптимизация" се използва, когато се използват дълбоки трансформации на програмата за подобряване на качеството на програмата, като например преобразуването й в графична форма за изследване на нетривиалните свойства на програмата.

В този смисъл подчертаването на общи подизрази е една от най-простите оптимизации. За реализирането му е необходима известна трансформация на програмата, а именно изграждането на насочен ацикличен граф, който беше разгледан в главата за междинните представяния.

Линеен разделе поредица от изрази, в които контролът влиза в началото и излиза в края, без да спира и да прескача отвътре.

Да разгледаме дърво от линеен участък, в което операциите са върхове, а операндите са потомци. Ще кажем, че два върха образуватобщ подизраз, ако поддърветата за тях са еднакви, тоест имат една и съща структура и съответно еднакви операции във вътрешните върхове и едни и същи операнди в листата. Изборът на общи подизрази ви позволява да генерирате код за тях веднъж, въпреки че може да доведе до някои трудности, които ще бъдат обсъдени накратко по-долу.

Изборът на общи подизрази се извършва на линеен участък и се основава на две позиции Изборът на общи подизрази се извършва на линеен участък и се основава на две позиции.

Тъй като може да има няколко присвоявания на линеен участък от променлива, когато се подчертават общи подизрази, е необходимо да се прави разлика между появяванията на променливипреди и след назначение. За да направите това, всяка променлива е снабдена с брояч. Първо, броячите на всички променливи са настроени на 0. Всеки път, когато се присвоява променлива, нейният брояч се увеличава с 1.
Изборът на общи подизрази се извършва чрез обхождане на дървото на изразите отдолу нагоре отляво надясно. Когато бъде достигнат следващият връх (нека операцията, приложена в този връх, е двоична op; в случай на унарна операция разсъждението е същото), разглеждаме общите подизрази, свързани с op. Ако има израз, свързан с op и такъв, че левият му операнд е общ подизраз с левия операнд на новия израз, а десният операнд е общ подизраз с десния операнд на новия израз, тогава ние декларираме новия израз като общ с намерения и съхраняваме указателя към намерения общ израз в новия израз. Основата на конструкцията е променлива: ако операндите на двата израза са едни и същи променливи с едни и същи броячи, тогава те са общи подизрази. Ако изразът не е маркиран като общ, той е посочен в списъка с операции, свързани с op.

Нека сега разгледаме изпълнението на алгоритъма за извличане на общи подизрази. Поддържат се следните глобални променливи:

Таблица - таблица с променливи; за всяка променлива се съхранява нейният брояч ( Count ) и указател към горната част на дървото на израза, в което променливата е била последно срещната от дясната страна ( Last );

OpTable е таблица със списъци (от тип LisType) на общи подизрази, свързани с всяка операция. Всеки елемент от списъка съхранява указател към върха на дървото (поле Addr ) и продължението на списъка (поле List ).

Всеки връх на изразното дърво има свързан запис NodeType със следните полета:

Ляво - ляво дете на върха,

Дясно - дясното дете на върха,

Comm - указател към предишния общ подизраз,

Флаг - индикация дали поддървото е общ подизраз,

Varbl - индикация дали горната част е променлива,

VarCount - променлив брояч. Изборът на общи подизрази и изграждането на дървото се извършват по следните правила. Атрибутът Entry на нетерминала Variable дава указател към променливата в таблицата. Атрибутът Val на символа Op дава кода на операцията. Атрибутът Node на символите IntExpr и Assignment дава указател към записа NodeType на съответния нетерминал.

Нека сега разгледаме някои прости правила за разпределяне на регистър при наличието на общи подизрази. Ако броят на регистрите е ограничен, можете да изберете една от следните две опции.

Превод на обектно-ориентирани свойства на езици за програмиране

В този раздел ще разгледаме механизмите за превод на основните структури на обектно-ориентираните езици за програмиране, а именно наследяване и виртуални функции, използвайки езика C++ като пример.

Виртуални базови класове

Можете да добавите ключовата думаvirtualкъм дескриптора на базовия клас. В този случай един подобект на виртуалния базов клас се споделя от всеки базов клас, в който този оригинален базов клас е дефиниран като виртуален.

Да кажем, че имаме следната йерархия на наследяване:

Това може да бъде представено чрез следната класова диаграма: