18c0693f

Свертка функций


Вследствие большого количества инструкций в трассе, аналитик перед началом анализа некоторым образом разбивает трассу на блоки (примером такого блока может служить вызов функции), а затем анализирует их по очереди. Таким образом, после завершения анализа некоторого блока и его описания, аналитику, как правило, не требуется работать с инструкциями этого блока. Возникает задача скрыть от аналитика проанализированные и описанные блоки кода для упрощения анализа других блоков. Для этого добавлена возможность создания визуальных свёрток. Этот механизм аналогичен свёрткам в визуальных средах разработки высокоуровневых языков программирования, например в редакторе MS Visual Studio для каждой функции существует возможность скрыть её тело, если оно в данный момент пользователя не интересует. В трассах это позволяет пользователю скрывать проанализированные фрагменты кода. Свёртка представляет из себя именованную блок последовательных инструкций. При создании свёртки (может происходить вручную или автоматически, как результат работы алгоритмов анализа структуры трассы) указывается имя свёртки и её границы. Свёртка может находиться в 2х состояниях:

Свёртки могут быть вложенными, но не могут пересекаться.

При переходе на заданный шаг в трассе, в случае если он находится внутри свёртки и скрыт от пользователя, происходит автоматическое разворачивание этой свёртки, а также всех других свёрток, в которые она вложена.

Класс свёртки CVisualFurl представляет собой структуру из трёх полей: имя, начальный и конечный шаги свёртки и реализует методы для доступа к их значениям.

Класс FurlManager инкапсулирует всю работу со свёртками, отвечает за их сохранение и загрузку из файла. Так как объём трасс достаточно велик, хранить текстовое представление трассы невыгодно, поэтому при необходимости отобразить некоторый шаг трассы компонент отображения должен заново получать его текстовое представление.
Компонент отображения обращается с запросами к FurlManager, для того чтобы правильно сгенерировать очередную строку в трассе

Опишем основные методы класса FurlManager, а ниже вкратце опишем его взаимодействие с компонентом отображения.

Основные методы класса FurlManager:



Чтобы отобразить очередной шаг трассы, нужно знать начинается ли на этом шаге свёртка, и если начинается, то в каком состоянии она находится – свёрнутом или развёрнутом. Для этого используется метод getFurl. В зависимости от результатов запросов очередная строка может быть отображена как:

Кроме того, нужно знать точную длину видимой трассы, с учётом свёрнутых участков. Для этого используется метод getStepsCount.

При переходе в заданный пользователем шаг нужно убедиться, что он в данный момент виден. Для этого используется метод ensureVisible.

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


Для этого используется метод expandFurl.

При загрузке трассы выполняется также и загрузка информации о свёртках – методом loadFurls.А после окончания работы с трассой, в слу-чае если состояние компонента FurlManager изменилось (появились новые свёртки или старые были удалены – метод isDirty возвращает истину) информация о свёртках сохраняется в файл с помощью метода saveFurls.

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

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

Граф зависимостей представляет собой направленный двудольный граф, где одно множество вершин – это ячейки, содержащие значения, а второе множество – инструкции (шаги трассы), которые читают или пишут значения в эти ячейки. Направление ребра определяется тем, пишет инструкция в ячейку или читает из неё. Если ячейка читается – ребро направлено от ячейки к инструкции, если пишется, то ребро направлено от инструкции к ячейке. Задача построения свёртки функций по графу зависимостей состоит в трансформации этого графа в другой направленный двудольный граф с атрибутированными рёбрами, который и назовём свёрткой. Дадим его определение.

Назовём свёрткой такой двудольный граф, в котором:



Выделим несколько видов зависимостей между ячейками.

Рассмотрим подробнее преобразование «свёртка». Фактически требуется для всех входных и выходных ячеек, между которыми существует путь по рёбрам графа зависимостей добавить ребро в граф свёртки. Однако возникает проблема задания атрибута этого ребра. Таким образом, требуется:


  1. Для каждой пары ячеек, одна из которых является входной, а другая выходной в графе зависимостей, найти все пути между ними.
  2. Для каждого найденного пути на основе встречающихся в нём инструкций сгенерировать атрибут типа зависимости между входной и выходной ячейкой.
  3. На основании же имеющегося атрибута, полученного при анализе прошлых путей и вновь созданного атрибута получить итоговый атрибут типа зависимости.


Алгоритм поиска путей в графе является стандартным, поэтому остановимся подробнее на 2 и 3 пункте. Рассмотрим различные виды путей типы атрибутов, им соответствующие.

Из вышесказанного следует, что приоритет выставления атрибутов при анализе зависимостей следующий:

Рассмотрим теперь процесс «слияния» атрибутов, полученных при анализе разных путей от входной ячейки к выходной. Вначале рассмотрим пример.

Пусть a – текущая выходная ячейка блока, b – текущая входная ячейка блока, а c и d – некоторые другие выходные ячейки блока. Пусть между ячейками с и b есть простая зависимость, а между ячейками d и b – зависимость косвенная. Пусть есть инструкция, реализующая простую зависимость a(c,d). Требуется определить атрибут зависимости a(b). Видно, что существует 2 пути из b в a: b – c – a и b – d – a. Причём первому пути соответствует атрибут простой зависимости, а второму – атрибут косвенной зависимости.

В этом случае итоговый атрибут будет соответствовать «объединению» этих двух типов зависимости. Очевидно, что в случае объединения атрибутов одного типа, итоговый атрибут будет равен каждому из исходных. Следовательно, атрибуты на рёбрах могут принимать три значения:

Предлагается хранить зависимости выходных ячеек от входных в виде битовых масок, где отдельные биты соответствуют типам зависимостей. А объединённым зависимостям соответствуют группы выставленных битов. Это позволит эффективно добавлять новые типы зависимостей, не меняя модели.

В случае представления значения атрибута, как битовой маски, объединение атрибутов представляет собой просто выполнение побитового "или" над их масками.

Алгоритм построения свёрток зависимостей по заданному блоку инструкций реализован в виде компонента FurlMaker. Промежуточные результаты алгоритма в процессе его работы хранятся в специальном компоненте, DependencyContainerTree оптимизированном по скорости доступа с учётом специфики алгоритма. Окончательные результаты хранятся в компоненте CDependencyFurl, который аналогичен компоненту визуальных свёрток, но дополнительно хранит отображение входных элементов на выходные и наоборот с учётом видов зависимостей.

Основные методы алгоритма FurlMaker:

Для визуализации свёрток зависимостей была использована сторонняя библиотека Microsoft GLEE. Так как библиотека была написана на С#, то для её использования в C++ проекте был написан специальный переходник с использованием промежуточного языка Managed C++.

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




Все публикации раздела