Владиславлев Виктор Системы программирования (СП) Создание СП для новых архитектур

Содержание Системы программирования Структура компилятора o Препроцессор o Компилятор o Ассемблер o Линковщик o Динамический Линковщик Прочие системные утилиты Библиотеки Создание/Портирование СП o Machine Description o Двоичный интерфейс приложения o Библиотеки Симулятор Средства отладки Средства анализа производительности Форматы исполняемых файлов Форматы отладочной информации Agenda

Системы программирования Toolchain – набор средств разработки программ Компилятор Бинарные утилиты Библиотеки Средства отладки и профилирования И проч. (редакторы, навигаторы по коду, системы автодокументации, верификаторы и т.д.) Примеры: GNU toolchain – Unix/Linux/Windows на большинстве архитектур Microsoft Visual Studio – Windows на x86 ICC – toolchain от компании Intel – Windows/Linux на x86 и IA64 Code Warrior – toochain для встроенных систем Xcode – toochain для Mac OS X и iOS Можно разделить Нативные системы (host = target) Кросс-системы (host != target) Toolchain

ядро компилятора Структура компилятора Компилятор - переводит исходный код программы (написанные на языке высокого уровня) в эквивалентный код на языке целевой платформы Compiler structure.c.cpp.f77....c.cpp.F... High-Level IR Low-Level IR Low-Level IR Low-Level IR asm.o.obj.out.exe Препроцессор 2.2.Front-End 3.3.Оптимизации 4.4.Кодогенератор 5.5.Ассемблер 6.6.Линкер ++ Можно проследить запуски фаз компиляции (опция --verbose в GCC)

Препроцессирование Инициальная обработка 1.Разбиение на строки 2.Замена триграфов 3.Объединение строк 4.Замена комментариев Рабиение на токены 1.(слева направо, жадная) 2.Замена диграфов (в С++) Собственно препроцессирование 1.Подключение файлов (#include) 2.Макроподстановки (#define/undef/##) 3.Условная компиляция (#ifdef/if/else/elif/endif) 4.Управление строками (#line) 5.Диагностика (#error/warning) ++ Часто полезно получить препроцессированный код (опция -E в GCC) Preprocessing Триграфзначение ??([ ??)] ??} ??=# ??/\ ??'^ ??!| ??-~ /??/ * */ # /* */ defi\ ne FO\ O 10\ 20 #define FOO 1020 a = i+++j; a = (i++) + j; a = i + (++j);

Препроцессирование Инициальная обработка 1.Разбиение на строки 2.Замена триграфов 3.Объединение строк 4.Замена комментариев Рабиение на токены 1.(слева направо, жадная) 2.Замена диграфов (в С++) Собственно препроцессирование 1.Подключение файлов (#include) 2.Макроподстановки (#define/undef/##) 3.Условная компиляция (#ifdef/if/else/elif/endif) 4.Управление строками (#line) 5.Диагностика (#error/warning) ++ Часто полезно получить препроцессированный код (опция -E в GCC) Preprocessing Триграфзначение ??([ ??)] ??} ??=# ??/\ ??'^ ??!| ??-~ /??/ * */ # /* */ defi\ ne FO\ O 10\ 20 #define FOO 1020 a = i+++j; a = (i++) + j; a = i + (++j);

собственно Компилятор Компилятор обрабатывает единицу трансляции (translating unit TU, compilation unit). В С/С++ это файл после препроцессирования. В FORTRAN – один файл может содержать несколько TU. Компилятор включает: 1.Компилятор переднего плана (Frontend) – строит по исходному коду промежуточное представление (Intermediate Representation – IR, или IL); включает o Лексический анализатор o Синтаксический анализатор o Семантический анализатор 2.Фазы Анализа и Оптимизаций представления o их много (Основная часть курса), но можно и уменьшить: разные уровни оптимизаций 3.Фазы Распределение регистров и кодогенерация Результат работы компилятора – язык ассемблера (ассемблер, машинный язык) целевой архитектуры Compiler ++ Можно проследить результат работы компилятора после каждой фазы (опции --dump-tree-all --dump-rtl-all в GCC)

трансформация Кода int f(int b, int c) { int a1 = b*5 - c; int a2 = -8*b + 2*c; return 2*a1 + a2; } D.26 = b * 5; a1 = D.26 - c; 27 = b * -4; D.28 = D.27 + c; a2 = D.28 * 2; D.20 = a1 * 2; D.29 = D.20 + a2; return D.29;.globl f.type f:.LFB0:.cfi_startproc leal (%rdi,%rdi), %eax ret.cfi_endproc Code transformation ++ Бывает полезно посмотреть ассемблерный код (опция -S в GCC) 1.Source code 2.AST 3.High-level IR 4.Low-level IR 5.assembler a1 -8 a2 a1a2 ret set (reg:SI 62) (ashift:SI (reg/v:SI 60 [ b ]) (const_int 1 [0x1]); set (reg/i:SI 0 ax) (reg:SI 62);

Ассемблер Ассемблер как программа переводит язык ассемблера в код целевой архитектуры, сохраняемый в исполняемом формате Для символьных ссылок – резервирует место, подстановку реальных адресов осуществляет линкер КАК ПРАВИЛО, ассемблер – тривиален (парсинг, упаковщик). Исключение: IA-64 (Itanium) (виртуальные регистры, шаблоны, скобки параллельности) Язык ассемблера Имеет типы (наследованные от архитектуре), комментарии, объекты и пр. характерезуется тривиальным синтаксисом может быть не стандартизирован даже в рамках одной платформы Assembler mov eax, ebx Intel movl %ebx, %eax AT&T Имена регистров зарезервированы Сначала dst, потом src Регистры начинаются с % b, w, l, q – размер операнда

Линковщик Дефиниция – полное определение сущности (глобала или функции) Декларация – лишь обещание того, что где-то есть дефиниция Объектный файл содержит дефиниции функций и глобалов В коде есть ссылки на декларированные глобалы и/или функции Основная задача линковщика (линкера) – реализовать чужие обещания Проблемы: Никого не нашли – ошибка! Нескольких – (duplicate definitions): o С++: one definition rule o С: tentative definition для неинициализированных глобалов o FORTRAN: common model – в каждой TU свой COMMON блок, своего размера Инициализированный глобал Предварительное определение Декларация Дефиниция Переменная на стеке Указывает на память в куче Linker int G1 = 1; int G2; extern int G3; extern int f( int*); int g( int n) { int* h = malloc(n*sizeof(int)); f( h); return h[ G2 ]; } bss: datacodeheap bssdatacodefile memorystack

Недостатки статических библиотек: многократное дублирование кода в памяти связь приложения с реализацией библиотеки навсегда динамические библиотеки:.so в Unix,.dll в Windows,.dylib в MacOS X PIC (position-independent code) в Linux Procedure Linkage Table Global Offset Table ld.so – динамический загрузчик Мапирование кода в адресное пространство процесса Проблема с данными библиотеки DLL – это не PIC, как в Linux; в Windows это называется memory mapping Динамическая линковка Dynamic Linking movl %edx, %esi movq %rax, %rdi call movq %rax movl (%rax), %eax cltq movl %edx, %esi movq %rax, %rdi call f movl G2(%rip), %eax сltq call f … LPT f:?? a.out libname lib function f ld.so LPT f:0x… f() lib.so

Прочие бинарные утилиты as – ассемблер ld – линкер gprof – профилировшик, требует инструментирование код ar – архиватор для создания статических библиотек (LIB – Windows) objcopy – копирует содержимое одних объектных файлов в другие objdump – получение информации из объектного файла, в частности, выполняет функцию дизассемблера readelf – показать содержимое ELF файла strip – удаляет символы из объектного файла gold – улучшенный линкер от Google, теперь – в стандартных утилитах nm – получить список символов из объектного файла c++filt – DeMangling windmc – message compiler (Win) windres – recourse compiler (Win) Other binutils _ZGVZN15UICmdWithParser11parseMemoryEPPKcmRmP7ProgramP7MachineS3_RNS_15uiParserWidth_tEE8reMemory UICmdWithParser::parseMemory(char const**, unsigned long, unsigned long&, Program*, Machine*, unsigned long&, UICmdWithParser::uiParserWidth_t&)::reMemory

Библиотеки Требования к стандартной библиотеке языка 1.Взаимодействие с ОС 2.Удобный ввод-вывод 3.Математические функции 4.Средства отладки и диагностирования программ (про assert.h) 5.Поддержка часто используемых типов (функции работы со строками, работа с UNICODE) Для С это libc ++ не все требования выполнены; например, п.1. – отдельный стандарт POSIX Распространненные реализации: GNU C Library – самая распространенная реализация, используемая в Linux Microsoft C Run-time Library Dietlibc – альтернативная небольшая реализация Стандартной библиотеки Си uClibc – Стандартная библиотека Си для встраиваемых систем на базе Linux Newlib – Стандартная библиотека языка Си для встраиваемых систем Klibc – применяется главным образом для загрузки Linux-систем Eglibc – разновидность glibc для встраиваемых систем bionic – реализация стандартной библиотеки в Android Libraries

Для С это libstdc++ o IOStream o STL Библиотеки динамической поддержки языковой; для С++ это libsupc++ o EH (exception handling) o RTTI (run-time type information): dynamic_cast, typeid, type_info o new с синтаксисом размещения Библиотека поддержки компилятора; для GCC это libgcc o Арифметические функции, которые не могут быть напрямую раскрыты в команды target архитектуры (divsi3(int, int)) o Функции работы с исключениями (независимые от языка) (_Unwind_GetIp) o Другие функции поддержки компилятора (_splitstack_find) BFD (Binary File Descriptor) library – основа большинства бинарных утилит Библиотеки Libraries

Создание/Портирование СП Два пути Создание Toolchain с нуля: есть свои плюсы, но о них почти ничего не известно (пропреитарный код, который можно продавать) Портирование имеющегося o Коммерческие Front-Endы – Edison Design Group o Открытая система программирования GCC (GNU Compiler Collection) o Еще одна: LLVM (Low-Level Virtual Machine) o UTL (Universal Translating Library) Creating/Poring TC … … Входные языки Целевые платформы SUN Compiler MS Compiler GCC LLVM EDG Front-End Intel compiler Elbrus compiler CG1CG2 C++CF77

Простой пример на С и его возможное расположение в памяти Семантические единицы: тип и размер данных, управляющие структуры, операции, вызовы функций (что требует ABI) Это трудоемко! Описание машины быстро решает эту задачу Простой пример Example

Показан процесс сборки cc1 под ARM Сверху – блок исходных кодов, снизу – компоненты компилятора Из MD генерируется RTL generator (expander) и кодогенератор MD – описывает структуру генератора генератора кода Описание Машины Machine Description (MD)

Циклограмма работы собранного компилятора SSA (static single assignment) – представления кода, при котором каждая переменная непосредственно модифицируется лишь единожды, а далее только используется GIMPLE – высокоуровневый язык внутреннего для GCC представления программы в SSA форме RTL (register transfer language) – низкоуровневый язык внутреннего для GCC представления программы, по сути высокоуровневый ассемблер Цикл работы компилятора ???(MD)

Файловая структура: директория gcc/gcc/config/ Файлы.h,.cpp и.md, который содержит: define_insn – шаблон инструкции в генерации кода define_split – шаблон разбиения сложных шаблонов на более простые define_expand – именнованный шаблон, используется для генерации RTL из GIMPLE define_peephole – шаблон частной архитектурно-зависимой оптимизации define_predicate – шаблон предиката (для проверки соответствия операндов инструкции) Структура описания в GCC GCC description structure

ABI (Application Binary Interface) – набор соглашений для обеспечения взаимодействия между приложениями, библиотеками и ОС Размер и выравнивание данных Формат системных вызовов Calling Convention – cпособ передачи параметров функций и возвращаемого значения: o Где передавать параметры: на регистрах, в стеке, через динамическую память, комбинируя всё вышеперечисленное o В каком порядке: прямом, обратном (проще реализовать эллипсиса) o Кто сдвигает стек обратно: callee или caller o Callee/Сaller saved регистры Какие бывают: cdecl – через стек, справа налево, обратный сдвиг – caller pascal – через стек, слева направо, сдвиг – callee fastcall – на регистрах, сдвиг – callee stdcall – через стек, справа налево, сдвиг – callee tailcall – вызов непосредственно перед возвратом, можно не двигать стек Двоичный интерфейс приложения ABI caller f() callee g()

Требования к библиотекам (в порядке убывания значимости) 1.Соответствие стандарту(корректная работа). 2.Код максимально написана на ЯВУ с минимальными аппаратными зависимостями 3.Эффективность (Premature optimazation is the root of all evil) В идеале необходимо создать лишь машинно-зависимую часть Рассмотрим bionic. Девиз: keep it really simple! Содержит libc, libm и немного для C++ НЕ содержит поддержки механизма исключений и wide chars собирается общей системой сборки Android содержит таблицу с номерами системных вызовов и их параметрами tools/gensyscalls.py – скрипт для генерации системных вызовов В аппаратно-зависимой части находятся setjmp()/longjmp() Содержит динамический загрузчик ld.so Портирование Библиотек Library Porting

Создание/портирование компилятора и ОС происходит параллельно с созданием архитектуры. Вопрос: КАК? Ответ: симулятор Функциональный симулятор Задача – отрабатывать семантику эмулируемого кода как можно быстрее QEMU – быстрый и портируемый динамический транслятор; имеет свой IR Performance симулятор Задача – воссоздать потактовую модель архитектуры предельно точно Конвейер Кэш Память Очень медленный SimPoint – обрабатывает трассы симулятора (формат BBV – Basic Block Vectors) и определяет наиболее горячие регионы исполнения для прогона на Performance симуляторе Симулятор Simulator

Средства отладки До отладчика Static source analysis – анализ исходного кода до или во время компиляции (компилятор, утилиты lint, cppcheck) Dynamic source analysis – анализ программы на этапе исполнения; исходный код инструментируется до/во время компиляции (Insure++) Static binary analysis – анализ двоичных файлов до их запуска (Антивирусы) Dynamic binary analysis – анализ кода на этапе исполнения; инструментируется бинарный код (valgrind, Pin) Комбинированные решения Отладчик На основе аппаратной поддержки – debug registers На основе программной поддержки: INT 1 – пошаговое исполнение; INT 3 – однобайтовая команда (INT n – 2 байта) GBD (GNU DeBugger) – поддерживает оба механизма, для привязки к коду требуется отладочная информация, что требует поддержки компилятора. Есть gdb-server – для упрощения портирования. Debugging tools

Valgrind Общий механизм для запуска различных утилит анализа Замедляет работы приложения в раз По сути является JIT (Just-In-Time) компилятором (UCode – Собственный IR) Имеет ряд стандартных утилит Альтернатива – утилита Pin от Intel, настроена на x86, IA64, XScale >100 утилит для Pin. На горячем коде замедление раза, на холодном раз framework Valgrind X86 PPC … Build IL IL Code gen init IL Instrumented IL Tool Memcheck – проверка памяти Cachegrind – профиль кэша Callgrind – профиль кэша+кода Massif – профиль кучи Helgrind – анализ многопоточности Lackey – кол-во инструкций и BB TreadSanitizer – новое от Google

VTune – система от Intel, сбор информации о динамическом поведении приложения на основе аппаратной поддержки (множество системных регистров) Gprof – в основе лежит метод Монте-Карло: каждые 10мс прерывается исполнение, смотрим стек и добавляет 10мс ко времени исполнения процедуры Утилиты на основе valgrind (+ callgrind или cachegrind) – в основе лежит детальный подсчет инструкций, не инструментирует код, но динамически ретранслирует приложение ++ Для профилирования надо инструметрировать код (опция -pg в GCC) Анализ производительности Performance Analysis

index % time self children called name /48965 BZ2_bzWriteClose64 [29] /48965 BZ2_bzWrite [7] [5] BZ2_bzCompress [5] /48965 handle_compress [6] /56 isempty_RL [43] /48965 BZ2_bzCompress [5] [6] handle_compress [6] /273 BZ2_compressBlock [8] / add_pair_to_block [22] /273 prepare_new_block [42] /56 isempty_RL [43] /6 init_RL [47] /273 BZ2_blockSort [9] [10] mainSort [10] / mainGtU [15] Пример профиля Profile example Место в профиле Собств. время Время потомков Общее число вызовов Откуда вызвали Сколько вызвали отсюда Листовая функция, вызывается из одного места в огромном цикле

Граф вызовов Call Graph

Профиль по инструкциям Instruction profiling

Исполняемые форматы ELF – Executable and Linkable Format (Unix, Linux) PE – Portable Executable (Windows) a.out – условно непосредственный код COFF (XCOFF, ECOFF) Executable Formats

Stab COFF PE/COFF OMF IEEE-695 DWARF – рекомендован к ознакомлению Отладочные форматы Debugging formats