Анализ указателей в программах с вызовами библиотечных функций. Маркин (1157400)
Текст из файла
Маркин А.Л., Ермолицкий А.В. (ЗАО «МЦСТ»)АНАЛИЗ УКАЗАТЕЛЕЙ В ПРОГРАММАХ С ВЫЗОВАМИ БИБЛИОТЕЧНЫХФУНКЦИЙАннотацияВ статье рассмотрена методика ускорения анализа указателей в оптимизирующихкомпиляторах, позволяющая уменьшить затраты и увеличить точность анализа вызововфункций стандартной библиотеки за счёт использования модели их поведения.Ключевые словаоптимизирующий компилятор, стандартная библиотека, анализ указателейВступлениеВажной частью оптимизирующих компиляторов является анализ указателей - набортехник для вычисления возможных пересечений указателей в памяти, т.е. определяется,могут ли два указателя ссылаться на один участок памяти.
Такая информация необходима дляполноценной работы всех оптимизаций, работающих с операциями чтения/записи в память[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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
