Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Анализ указателей в программах с вызовами библиотечных функций. Маркин

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

PDF-файл Анализ указателей в программах с вызовами библиотечных функций. Маркин, который располагается в категории "статьи" в предмете "конструирование компиляторов" изседьмого семестра. Анализ указателей в программах с вызовами библиотечных функций. Маркин - СтудИзба 2019-09-18 СтудИзба

Описание файла

PDF-файл из архива "Анализ указателей в программах с вызовами библиотечных функций. Маркин", который расположен в категории "статьи". Всё это находится в предмете "конструирование компиляторов" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

Маркин А.Л., Ермолицкий А.В. (ЗАО «МЦСТ»)АНАЛИЗ УКАЗАТЕЛЕЙ В ПРОГРАММАХ С ВЫЗОВАМИ БИБЛИОТЕЧНЫХФУНКЦИЙАннотацияВ статье рассмотрена методика ускорения анализа указателей в оптимизирующихкомпиляторах, позволяющая уменьшить затраты и увеличить точность анализа вызововфункций стандартной библиотеки за счёт использования модели их поведения.Ключевые словаоптимизирующий компилятор, стандартная библиотека, анализ указателейВступлениеВажной частью оптимизирующих компиляторов является анализ указателей - набортехник для вычисления возможных пересечений указателей в памяти, т.е. определяется,могут ли два указателя ссылаться на один участок памяти.

Такая информация необходима дляполноценной работы всех оптимизаций, работающих с операциями чтения/записи в память[1].Принцип работы анализа указателей.Анализ указателей является технически сложным и ресурсоёмким процессом, которыйдаёт максимальный эффект при межпроцедурном анализе всей программы.

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

Данный алгоритм начиная сфункции main рекурсивно просматривает содержимое каждой функции. Для каждойоперации чтения/записи в функции он находит множество указателей с которыми этаоперация гипотетически может работать. Если множества указателей двух операций непересекаются, то операции считаются независимыми. Т.к. данный анализ являетсямежпроцедурным, то во время его работы могут создаваться графы с миллионами узлов, асамо время работы может занимать большую часть от всего времени компиляции.В компиляторе для архитектуры Эльбрус межпроцедурный анализ указателей показываетнаибольшую эффективность в режиме “вся программа”. В этом режиме компилятор видитвсе исходные файлы как один модуль и имеет доступ к коду всех функций, использующихся впрограмме.При этом независимо от режима в программах часто встречаются вызовы функций,определённых стандартной библиотекой языка.

Их поведение всегда неизменно, нокомпилятор вынужден каждый раз заново производить их анализ. На это тратятся ресурсы вовремя компиляции, а также, учитывая сложность некоторых библиотечныйх функций,происходит уменьшение точности всего анализа. В рамках данной работы было предложеносоздать модель поведения функций, определённых стандартом для устранениянеобходимости анализировать содержимое таких функций. [2]Структура модели поведения функцийМодель библиотечных функций представляет из себя, описание свойств множествафункций, поведение которых определено стандартом и не может быть изменено. Модельфункции позволяет анализировать программу без точного анализа содержимого этойфункции. В неё включается информация об аргументах функции, работе функции суказателями и глобальными переменными. Ниже приведено подробное описание свойствфункций, описываемых данной моделью.Режим возврата - свойство, отвечающее на вопрос “всегда ли функция возвращаетуправление?”.

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

Часто это свойство можно не учитыватьЗапись по аргументам-указателям - список аргументов-указателей, в которые можетбыть записано какое-либо значениеЧтение из аргументов-указателей - список аргументов-указателей, которыесчитываются функциейИспользование аргументов-указателей - список аргументов-указателей, которые могутпопасть в результат функции или быть записаны в глобальную переменнуюВызов функции по аргументу-указателю - список аргументов, которые являютсяуказателем на функцию и могут вызываться внутри библиотечной функцииВозврат указателя - результатом функции является указатель.Принадлежность к стандарту - стандарт языка, в котором данная функция определена.Приведённых выше свойств достаточно для корректной работы анализов и оптимизацийбез анализа кода библиотечных функций, описанных моделью.

Вся необходимая информацияизвлекается непосредственно через запросы к модели. Это позволяет уменьшить времякомпиляции программ, количество потребляемой памяти во время компиляции и увеличитьточность анализа указателей за счет уменьшения количества анализируемого кода.Исследование экспериментальных результатов.Предложенная модель библиотечных функций была внедрена в промышленныйоптимизирующий компилятор для семейства микропроцессоров Эльбрус. Влияние моделифункций на процесс компиляции и исполнения было экспериментально измерено на задачахиз пакетов тестов SPEC-CPU2000 и SPEC-CPU2006 [3].В рамках данного исследования проводится замер скорости работы и потребляемойпамяти анализа указателей в 2 режимах сборки с 3 разными наборами опций.Первый набор называется «black_box».

В этом наборе опций компилятор не видит кодбиблиотечных функций, и, следовательно, всегда делает консервативные предположениякасательно их поведения.Второй набор называется «full_lib». В нём компилятору становится доступен для анализапромежуточный код библиотечных функций.Третий режим называется «fast_lib». В этом режиме используется модель поведениябиблиотечных функций. Если компилятор находит в ней исследуемую функцию, то он непроизводит её анализ, а получает все данные основываясь на информации из модели.Исследование влияния на процесс компиляции.Параметры компиляции по вышеописанным наборам опций измеряются в режимахпомодульной сборки и сборки всей программы.

Помодульная сборка представляет из себянаиболее привычный способ сборки программ, при котором сначала отдельно собираетсякаждый файл с исходным кодом, а далее происходит их связывание. В режиме «всяпрограмма» компилятор видит все исходные файлы как одно целое и компилирует всюпрограмму с библиотеками как единственный модуль.Замеры затрат ресурсов показывают, что при использовании модели библиотечныхфункций затраты памяти и время выполнения анализа указателей сокращаются поотношению к набору опций «full_lib», а на некоторых задачах близки к набору опций«black_box».

Но точность анализа такая же или выше чем с набором опций компиляции«full_lib». Результаты тестов для наборов задач SPEC-CPU2000 и SPEC-CPU2006 можноувидеть на Рис. 1 а,б и Рис. 2 а,б. Т.к. для данных замеров сборка в помодульном режиме неимеет смысла, рассматриваются только замеры в режиме сборки «вся программа».Погрешность измерений в среднем составляет 4.5%.Рис 1.а Отношение времени исполнения фазыРис 1.б Отношение расхода памятиРис 2.а Отношение времени исполнения фазыРис 2.б Отношение расхода памятиКрасными столбцами обозначены замеры, показывающие отношение параметра врежиме «black_box» к режиму «full_lib», а зелёными - отношение параметра в режиме«black_box» к режиму «fast_lib». Т.е.

чем меньше значение столбца тем хуже результат.Значение единица показывает, что отсутствуют изменения в затрачиваемых ресурсах.Для набора задач SPEC-CPU2000 использование набора опций «full_lib» даётдеградацию в скорости анализа указателей в среднем на 55%, а расход памяти увеличиваетсяв среднем на 40%.

При использовании набора опций «fast_lib» деградации по времениработы анализа составляют в среднем 1%, что находится в пределах погрешности, а среднееувеличение использованной памяти составляет всего 9%.Наибольшее ускорение анализа указателей произошло в задаче 183.equake на 50%, амаксимальная деградация происходит в задаче 197.parser на 65%. При этом стоит отметить,что на задачах 164.gzip и 256.bzip2 при опциях «full_lib» происходят деградации времениработы анализа указателей на 96% и 97% соответственно, а при «fast_lib» в задаче 164.gzipнаблюдается деградация на 25%, а в задаче 256.bzip2 ускорение на 5%. Это связано с тем, чтообъём исходного кода задач сопоставим с объёмом кода используемых ими библиотечныхфункций.Единственной задачей, уменьшившей потребление памяти при наборе опций «fast_lib»является 173.applu, показавшей улучшение на 6%.

Наибольшую деградацию поиспользованной памяти показала задача 197.parser — анализ указателей на этой задаче сталпотреблять на 46% больше памяти. Подобные эффекты происходят из-за отсутствияанализируемых функций в модели. Обычно это библиотечные функции, не описанные встандарте. Например, в задаче 197.parser при работе анализа указателей было зафиксировано421 уникальных обращений к модели, из которых только для 55 обращений содержаласьинформация.Для набора задач SPEC-CPU2006 использование набора опций «full_lib» даётдеградацию в скорости анализа указателей в среднем на 50%, а расход памяти увеличиваетсяв среднем на 37%. При использовании набора опций «fast_lib» деградации по времениисполнения составляют в среднем 20%, а среднее увеличение использованной памятисоставляет 19%.Наибольшее ускорение анализа указателей произошло в задаче 456.hmmer на 25%, амаксимальная деградация происходит в задаче 462.libquantum на 94%. Время работы анализана задаче 462.libquantum с набором опций «fast_lib» аналогично времени работы с наборомопций «full_lib», что связано с большим количеством библиотечных функций, не включённыхв модель — 328 из 367.

Свежие статьи
Популярно сейчас