-
Notifications
You must be signed in to change notification settings - Fork 18
Instrumentation
- 1 Введение
- 2 Инструментация и динамический анализ программы
- 3 Обозначения формальных параметров
- 4 Мета информация
- 5 Инструментация обращений к памяти
- 6 Инструментация функций и их вызовов
- 7 Инструментация естественных циклов программы
- 8 Пример программы после инструментации
Динамический анализ опирается на инструментацию, выполняемую на уровне внутреннего представления программы LLVM IR. Для каждого инструментируемого объекта анализатору передается описывающая его мета информация. Данная информация может быть использована в динамическом анализаторе для определения объекта исходного кода, соответствующего инструментированному объекту.
Инструментация модуля программы (llvm::Module) включает:
- объявление функций динамического анализатора;
- вставку вызовов данных функций в тела функций инструментируемого модуля;
- объявление глобального пула, содержащего мета информацию, описывающую инструментируемые объекты модуля;
- создание вспомогательных функций, отвечающих за инициализацию мета информации, регистрацию типов и глобальных данных.
Все функции динамического анализатора имеют префикс sapfor. Для обозначения переменных и функций связанных с получением мета информации, описывающей объекты программы, используется обозначение DI (Debug Info).
С каждым объектом добавленным в LLVM IR в процессе инструментации будут связанны метаданные, к которым можно получить доступ по имени sapfor.da. Кроме того, для некоторых добавленных объектов соответствующие им метаданные будут указаны в списке именованных метаданных для каждого модуля программы. Список также будет иметь имя sapfor.da.
Для добавления в программу вызовов функций динамического анализатора используется опция анализатора TSAR -instr-llvm. Запущенный с данной опцией анализатор построит для заданной программы LLVM IR с вызовами функций динамического анализатора. Затем можно воспользоваться компилятором Clang, чтобы сначала скомпилировать файлы, содержащие реализацию этих функций, а затем скомпоновать их с пользовательской программой.
Замечание. Воспользоваться инструментацией возможно начиная с pull request #7.
Clang также позволяет получить обычные объектные файлы для .ll файлов, для этого можно воспользоваться опцией -c. В этом случае для компиляции файлов динамического анализаторa и последующей компоновки можно воспользоваться другими компиляторами, например GCC.
Предупреждение. Во время компоновки нужно учитывать, что при инструментации используется конвенция вызовов языка Си (“ccc” - The C calling convention). В частности, это означает, что в С++ коде определения функций динамического анализатора нужно окружить блоком extern "C" {...}.
Ниже приведена последовательность запуска инструментированной программы на примере, программы Jacobi.c и реализации функций динамического анализатора DAExample.c, расположенных в директории test/instrumentation репозитория TSAR:
tsar -instr-llvm Jacobi.c
clang -std=c++11 Jacobi.ll DAExample.cpp -o Jacobi.out
./Jacobi.outС помощью TSAR также возможна инструментация файлов, содержащих LLVM IR. В частности, начиная с LLVM 7.0 поддерживается инструментация LLVM IR полученного для Fortran-программ c помощью Flang. Для избежания сложностей при компоновке библиотеки динамического анализа и проинструментированной программы рекомендуется выполнять сборку динамического анализатора также с помощью Flang. В этом случае, запуск интсрументированной программе Jacobi.f90 будет выглядеть следующим образом:
flang -S -emit-llvm -g Jacobi.f90
tsar -instr-llvm Jacobi.ll
flang Jacobi.ll DAExample.cpp -lstdc++ -o Jacobi.out
./Jacobi.outЗамечание. В данный момент раздельная инструментация модулей программы не поддерживается (см. issue #29). Для инструментации многомодульной программы можно воспользоваться опцией -merge-ast анализатора TSAR совместно с опцией -instr-llvm, чтобы предварительно объединить абстрактные синтаксические деревья (AST) разных модулей в один модуль. Также можно воспользоваться инструментом llvm-link, чтобы объединить предварительно полученные представления LLVM IR для разных файлов. После этого можно воспользоваться опцией -instr-llvm чтобы проинструментировать объединенный файл, содержащий LLVM IR для всей программы.
Опция -instr-entry=<function> позволяет указать функцию, в начало которой будут вставлены вызовы функций, выполняющих инициализацию структур динамического анализатора (см. ниже).
Опция -instr-start=<function-list> позволяет указать имена функций, начиная с которых будет выполнена инструментация. Если данная опция задана, то проинструментированны будут все указанные функции, а также все функции которые из них вызываются (в том числе косвенно, через вызовы других функций). Данная опция не влияет на точку, в которой выполняется инициализация структур динамического анализа.
Если анализатор TSAR собран в отладочном режиме, то становятся доступными опции:
-
-deug-only=instr-llvm- позволяющая вывести некоторую отладочную информацию о ходе процесса инструментации программы; -
-stats- позволяющая получить статистику по объектам, для которых была выполнена инструментация (количество зарегистрированных переменных, обращений к памяти, циклов, функций и др.).
Анализатор позволяет выполнять инструментацию не только для программы, заданной в виде файла с исходным кодом, но и для программы, представленной в виде LLVM IR, содержащим отладочную информацию. Это позволяет, например, выполнить инструментацию оптимизированного LLVM IR.
Ниже приведен пример того, как избежать инструментации большинства скалярных переменных, а также переменных простых агрегатных типов (структур, массивов известного размера):
tsar -emit-llvm Jacobi.c
opt -sroa -S Jacobi.ll -o Jacobi.sroa.ll
tsar -instr-llvm Jacobi.sroa.ll
clang -std=c++11 Jacobi.sroa.ll DAExample.cpp -o Jacboi.out
./Jacobi.outОпция -sroa инcтрумента LLVM opt запускает проход Scalar Replacement of Aggregates. В результате инструкции доступа к большинству локальных скалярных переменных (alloca), для которых не выполняются операции взятия адреса, будут преобразованы инструкции SSA-формы, а сами переменные будут размещены на регистрах. Данные переменные не будут учитываться при инструментации программы.
Ниже приведены имена формальных параметров функций динамического анализатора. Указанные имена используются для удобства описания и могут отличаться от соответствующих имен как в LLVM IR, так и в исходном коде динамического анализатора.
-
PoolPtr- пул хранящий мета информацию о программе; -
Size- размер некоторого объекта; -
StartId- смещение, которое используется для вычисления глобального идентификатора объекта, по локальному идентификатору в некотором модуле; -
Ids- массив идентификаторов объектов; -
Sizes- массив размеров объектов; -
Num- количество элементов в массиве свойств объектов; -
Addr- адрес участка памяти, к которому осуществляется доступ; -
ArrBase- адрес начала массива; -
ArrSize- размер массива, для многомерных массивов указывается общее количество элементов, фактически выполняется линеаризация; -
Start,End,Step- начало, конец и шаг итерационной переменной цикла; -
Position- номер параметра функции (нумерация начинается с0); -
Iter- номер итерации цикла.
Параметры с префиксом DI, представляющие собой указатель на элемент в пуле мета информации, выделяемом в начале программы:
-
DIVar- описание переменной программы; -
DILoc- описание позиции в исходной программе; -
DILoop- описание инструментируемого цикла; -
DIFunc- описание функции; -
DI- один из рассмотренных выше указателей.
Элементы в пуле мета информации строятся динамическим анализатором на основе мета строк:
-
DIString- строковое описание объекта исходной программы.
Под мета информацией понимается некоторое описание инструментируемых объектов исходной программы (например, имя переменной в исходном коде, строка где переменная была объявлена и др.).
В процессе динамического анализа мета информация об объектах программы хранится в структурах, зависящих от реализации динамического анализатора. Информация, необходимая для построения этих структур передается динамическому анализатору в виде текстовых строка (мета строк) определенного вида. Динамический анализатор помещает указатели на построенные структуры в пул мета информации, после чего они могут быть использованы в инструментируемой программе и при необходимости будут переданы в вызовы функций динамического анализатора в качестве параметров.
Таким образом все структуры, содержащие разобранные мета строки, должны быть заполнены до первого использования. В данный момент заполнение структур выполняется в начале инструментируемой программы, для этого соответсвующим образом модифицируется точка входа в программу (например, main()). Параметры функций динамического анализатора с префиксом DI (кроме DIString) соответствуют указателям, содержащимся в пуле мета информации.
Отдельно хранится информация об используемых типах данных. Каждый тип характеризуется уникальным идентификатором и размером. Идентификатор представляет собой целое число. Нумерация типов начинается с 0 и является общей для всех модулей программы. При этом один и тот же тип в разных модулях будет иметь разные идентификаторы.
В данный момент понятие идентификатора используется только для типов. Но в случае использования идентификаторов других объектов должна быть использована единая нумерация объектов. Это позволяет выполнять раздельную инструментацию модулей программы. Сначала вычисляются локальные идентификаторы в рамках обрабатываемого модуля. Затем, в начале выполнения программы эти идентификаторы пересчитываются в глобальные.
Предупреждение. В мета строках содержаться локальные идентификаторы. Глобальные идентификаторы могут быть вычислены динамическим анализатором на основе смещения, которое будет ему передано при регистрации строк.
Выделение пула указателей заданного размера:
void sapforAllocatePool(void ***PoolPtr, std::uint64_t Size);Создание структуры данных, хранящей отладочную информацию, по заданной текстовой строке:
void sapforInitDI(void **DI, char *DIString, std::int64_t StartId);Указатель на созданную по мета строке структуру будет сохранен по адресу DI, который должен указывать на некоторый объект в пуле мета информации, выделенном функцией sapforAllocatePool(). Если в строке DIString содержится локальный идентификатор LocalId, то StartId задает смещение необходимое для вычисления глобального идентификатора: GlobalId = StartId + LocalId. При обработке некоторого модуля StartId определяется по количеству идентификаторов используемых в ранее обработанных модулях.
Регистрация типов с заданными глобальными идентификаторами:
void sapforDeclTypes(std::uint64_t Num, std::uint_64_t *Ids, std::uint64_t *Sizes)Глобальные идентификаторы типов содержаться в массиве Ids. Размеры типов заданы в массиве Sizes. Массивы имеют размер Num.
Мета строки генерируются статически во время инструментации программы и сохраняются в виде глобальных константных объектов. Каждая строка включает описание ее типа type и пары <name>=<value>, разделенные *; заканчивается строка **:
"type=<value>*<name>=<value>*…*<name>=<value>**":Все параметры кроме type являются необязательными. Ниже рассмотрены допустимые виды мета строк, также указано какие параметры соответствуют указателям на структуры, хранящие разобранные строки.
Регистрация скалярных переменных (тип var_name) и массивов (arr_name) - параметр DIVar:
-
file,line1- файл и строка в которой переменная была объявлена; -
name1- имя переменной в исходной программе (не в LLVM IR); -
vtype- глобальный идентификатор типа (см.sapforDeclTypes()); -
rank- для массивов указывается количество измерений; -
local- устанавливается в1, если переменная является локальной (память выделяется на стеке), в противном случае устанавливается в0.
"type=var_name*file=Jacobi.с*line1=28*name1=I*vtype=0*local=1**"
"type=arr_name*file=Jacobi.c*line1=24*name1=A*vtype=2*rank=2*local=1**"Позиция (строка и столбец) в программе (тип file_name) - параметр DILoc:
"type=file_name*file=Jacobi.c*line1=30*col1=12**"Объявление функции (тип function) - параметр DIFunc:
-
vtype- тип возвращаемого значения (типvoidтакже имеет свой идентификатор); -
file- файл, в котором объявлена функция (определена функция может быть в другом файле); -
line1,line2– строки, задающие начало и конец функции соответственно; -
name1- имя функции в исходной программе (если не доступно, то имя в LLVM IR); -
rank- количество формальных параметров.
Для библиотечной функции fabs() доступно только объявление и не доступна отладочная информация, поэтому будет указано имя в LLVM IR, а границы указаны не будут:
"type=function*file=Jacobi.c*vtype=0*rank=0*line1=27*name1=main**"
"type=function*file=Jacobi.c*vtype=1*rank=1*name1=fabs**"Описание цикла (тип seqloop) - параметр DILoop:
-
file- файл, где расположен цикл; -
line1,col1иline2,col2- позиции начала и конца цикла соответственно; -
bounds- битовый флаг, который указывает известны ли границы и шаг цикла, а также представлены они знаковым или беззнаковым целым числом:-
1000- известно (или может быть вычислено до начала выполнения цикла) начальное значение переменной индукции; -
0100- известно (или может быть вычислено до начала выполнения цикла) конечное значение переменной индукции -
0010- известен (или может быть вычислен до начала выполнения цикла) шаг переменной индукции. -
0001- известные значения представлены беззнаковыми целыми числами, иначе - знаковыми.
-
Значение флага bounds равное 7 соответствует 1110 и означает, что границы и шаг цикла известны и представлены знаковыми целыми числами:
"type=seqloop*file=Jacobi.c**bounds=7*line1=28*col1=3*line1=35*col1=5**"Регистрация объявления скалярных переменных и массивов:
void sapforRegVar(void *DIVar, void *Addr);
void sapforRegArr(void *DIVar, std::uint64_t ArrSize, void *Addr);Перед чтением значения скалярной переменной или массива вставляются вызовы функций:
void sapforReadVar(void *DILoc, void *Addr, void *DIVar);
void sapforReadArr (void *DILoc, void *Addr, void *DIVar, void *ArrBase);После записи в скалярную переменную или массив вставляются вызовы функции
void sapforWriteVarEnd(void *DILoc, void *Addr, void *DIVar);
void sapforWriteArrEnd(void *DILoc, void *Addr, void *DIVar, void *ArrBase);В начале выполнения каждой функции вызывается вызов функции:
void sapforFuncBegin(void *DIFunc);Перед каждым выходом из функции вставляется вызов функции (возможное аварийное завершение или выброс исключения не отслеживается и не инструментируется):
void sapforFuncEnd(void *DIFunc);Перед первым использованием формальных параметров вставляются вызовы функций (для скалярных переменных и массивов соответственно), при этом регистрация переменных с помощью функций sapforRegVar и sapforRegArr не выполняется:
void sapforRegDummyVar(void *DIVar, void *Addr, void *DIFunc, std::uint64_t Position);
void sapforRegDummyArr(void *DIVar, std::uint64_t ArrSize, void *Addr, void *DIFunction, std::uint64_t Position);Перед и после вызова функции вставляются вызовы функций:
void sapforFuncCallBegin(void *DILoc, void *DIFunc);
void sapforFuncCallEnd(void *DIFunc);Выполняется инструментация всех естественных циклов программы, распознанных средствами LLVM (llvm::LoopInfoWrapperPass).
Перед входом в последовательный цикл вставляется вызов функции:
void sapforSLBegin(void *DILoop, std::uint64_t Start, std::uint64_t End, std::uint64_t Step);Если границы цикла и шаг невозможно вычислить до начала выполнения цикла, то в качестве их значений будет передан 0, а при регистрации мета строки, соответствующей DILoop будет определенным образом указан флаг bounds.
После выхода из цикла (выходов может быть несколько) вставляется вызов функции:
void sapforSLEnd(void *DILoop);В начало каждой итерации цикла вставляется вызов функции:
void sapforSIter(void *DILoop, std::uint64_t Iter);Для подсчета итераций заводится специальный регистр-счетчик, значение которого передается в данную функцию. Нумерация итераций начинается с 0.
Рассмотрим основные элементы LLVM IR полученного после инструментации программы:
// main.c
int main() {
return 0;
}Для получения LLVM IR была выполнена команда:
tsar -instr-llvm main.cВ результате будет получен файл main.ll.
Данный файл будет содержать объявление глобальной переменной для хранения пула мета информации и описывающие его метаданные:
@sapfor.di.pool = global i8** null, align 4, !sapfor.da !0
!0 = !{!"sapfor.di.pool", i8*** @sapfor.di.pool, i64 9}После объявления пула будут указаны глобальные строковые константы, содержащие мета строки:
@0 = internal constant [69 x i8] c"type=file_name*file=/home/dvmuser1/kataev/test/dynamic_anls/main.c**\00", !sapfor.da !1
@1 = internal constant [102 x i8] c"type=function*file=/home/dvmuser1/kataev/test/dynamic_anls/main.c*vtype=0*rank=0*line1=2*name1=main**\00", !sapfor.da !1
@2 = internal constant [76 x i8] c"type=var_name*file=/home/dvmuser1/kataev/test/dynamic_anls/main.c*vtype=0**\00", !sapfor.da !1Объявления массивов для хранения глобальных идентификаторов типов и их размеров имеют следующий вид:
@sapfor.type.ids = internal global [1 x i64] zeroinitializer, !sapfor.da !1
@sapfor.type.sizes = internal global [1 x i64] [i64 32], !sapfor.da !1В данном случае в программе используется только один тип данных int, представленный в LLVM IR с помощью i32, который будет иметь идентификатор 0. Поэтому для инициализации переменной @sapfor.type.ids используется zeroinitializer.
Для регистрации мета строк и заполнения пула мета информации будет создана отдельная внутренняя функция, для которой будет задано отдельное мета описание:
define internal void @sapfor.init.di(i64) !sapfor.da !7 {
%2 = load i8**, i8*** @sapfor.di.pool
%3 = getelementptr i8*, i8** %2, i64 5
%4 = getelementptr inbounds [69 x i8], [69 x i8]* @0, i32 0, i32 0
call void @sapforInitDI(i8** %3, i8* %4, i64 %0)
%5 = load i8**, i8*** @sapfor.di.pool
%6 = getelementptr i8*, i8** %5, i64 7
%7 = getelementptr inbounds [102 x i8], [102 x i8]* @1, i32 0, i32 0
call void @sapforInitDI(i8** %6, i8* %7, i64 %0)
%8 = load i8**, i8*** @sapfor.di.pool
%9 = getelementptr i8*, i8** %8, i64 8
%10 = getelementptr inbounds [76 x i8], [76 x i8]* @2, i32 0, i32 0
call void @sapforInitDI(i8** %9, i8* %10, i64 %0)
ret void
}
!7 = !{!"sapfor.init.di", void (i64)* @sapfor.init.di}В данной функции последовательно вызываются функции динамического анализатора sapforInitDI() для регистрации всех мета строк, преобразования их в структуры анализатора и сохранения указателей на данный структуры в пуле мета информации sapfor.di.pool.
Для регистрации типов и преобразования локальных идентификаторов в глобальные будет создана внутренняя функция и ее мета описание:
define internal void @sapfor.register.type(i64) !sapfor.da !1 {
br label %2
; <label>:2: ; preds = %2, %1
%3 = phi i64 [ 0, %1 ], [ %7, %2 ]
%4 = getelementptr [1 x i64], [1 x i64]* @sapfor.type.ids, i64 0, i64 %3
%5 = load i64, i64* %4
%6 = add nuw i64 %5, %0
store i64 %6, i64* %4
%7 = add nuw i64 %3, 1
%8 = icmp ult i64 %7, 1
br i1 %8, label %2, label %9
; <label>:9: ; preds = %2
%10 = getelementptr [1 x i64], [1 x i64]* @sapfor.type.ids, i64 0, i64 0
%11 = getelementptr [1 x i64], [1 x i64]* @sapfor.type.sizes, i64 0, i64 0
call void @sapforDeclTypes(i64 1, i64* %10, i64* %11)
ret void
}
!8 = !{!"sapfor.register.type", void (i64)* @sapfor.register.type, i64 1}Данная функция принимает единственный параметр %0, который задает начальное смещение, необходимое для вычисления глобальных идентификаторов типов. В конце функции стоит вызов функции динамического анализатора sapforDeclTypes(), отвечающей за регистрацию типов, используемых в программе.
Функции sapfor.init.di() и sapfor.register.type() создаются для каждого инструментируемого модуля. Они объявлены внутренними, чтобы не возникало конфликтов с аналогичными функциями из других модулей. Для вызова данных функций в начале программы в момент компоновки нескольких модулей в каждом модуле создается дополнительная внешняя функция sapfor.init.moduleN(), где N - номер модуля:
define i64 @sapfor.init.module0(i64) !sapfor.da !9 {
call void @sapfor.init.di(i64 %0)
call void @sapfor.register.type(i64 %0)
%2 = add nuw i64 %0, 1
ret i64 %2
}
!9 = !{!"sapfor.init.module", i64 (i64)* @sapfor.init.module0}При компоновке нескольких модулей в начало точки входа в программу (entry point) будет добавлен вызов функции выделения памяти для пула мета информации, который является общим для всех модулей программы:
define i32 @main() #0 !dbg !10 {
call void @sapforAllocatePool(i8*** @sapfor.di.pool, i64 9), !sapfor.da !1
%1 = call i64 @sapfor.init.module0(i64 0), !sapfor.da !1
%2 = load i8**, i8*** @sapfor.di.pool, !sapfor.da !1
%3 = getelementptr inbounds i8*, i8** %2, i64 7, !sapfor.da !1
%4 = load i8*, i8** %3, !sapfor.da !1
call void @sapforFuncBegin(i8* %4), !sapfor.da !1
%5 = alloca i32, align 4
%6 = load i8**, i8*** @sapfor.di.pool, !sapfor.da !1
%7 = getelementptr inbounds i8*, i8** %6, i64 8, !sapfor.da !1
%8 = load i8*, i8** %7, !sapfor.da !1
%9 = bitcast i32* %5 to i8*, !sapfor.da !1
call void @sapforRegVar(i8* %8, i8* %9), !sapfor.da !1
store i32 0, i32* %5, align 4
%10 = load i8**, i8*** @sapfor.di.pool, !sapfor.da !1
%11 = getelementptr inbounds i8*, i8** %10, i64 5, !sapfor.da !1
%12 = load i8**, i8*** @sapfor.di.pool, !sapfor.da !1
%13 = getelementptr inbounds i8*, i8** %12, i64 8, !sapfor.da !1
%14 = load i8*, i8** %13, !sapfor.da !1
%15 = load i8*, i8** %11, !sapfor.da !1
%16 = bitcast i32* %5 to i8*, !sapfor.da !1
call void @sapforWriteVarEnd(i8* %15, i8* %16, i8* %14), !sapfor.da !1
%17 = load i8**, i8*** @sapfor.di.pool, !sapfor.da !1
%18 = getelementptr inbounds i8*, i8** %17, i64 7, !sapfor.da !1
%19 = load i8*, i8** %18, !sapfor.da !1
call void @sapforFuncEnd(i8* %19), !sapfor.da !1
ret i32 0, !dbg !15
}Следом за инициализацией мета информации идет вызов функции sapforFuncBegin(), перед выходом из функции (инструкция ret) добавлен вызов функции sapforFuncEnd().
В исходной программе не было переменных, поэтому при инструментации LLVM IR будет зарегистрирована только одна переменная %5 = alloca 32, align 4, являющаяся вспомогательной и хранящая код возврата из функции main(). Для этого будет выполнен вызов функции sapforRegVar(). После записи 0 в данную переменную будет выполнен вызов функции sapforWriteVarEnd().
Все добавленный объекты (переменные, функции, инструкции) помечаются метаданными с именем sapfor.da. Для большинства объектов (кроме тех, что были упомянуты выше) метаданные не содержат какой-либо специальной информации и имеют вид:
!1 = !{}Ссылки на метаданный для специальных объектов sapfor.di.pool, sapfor.init.di, sapfor.register.type, sapfor.init.moduleN перечислены в списке именованных метаданных:
!sapfor.da = !{!7, !8, !0, !9}Написать нам можно через форму связи на сайте проекта DVM-системы.