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

анализа производительности
Форматы исполняемых файлов
Форматы отладочной информации

Agenda

проч. (редакторы, навигаторы по коду, системы автодокументации, верификаторы и т.д.)
Примеры:
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

High-Level IR

High-Level IR

Low-Level
IR

Low-Level
IR

Low-Level IR

asm

.o
.obj

.out
.exe

1

2

4

5

6

1.Препроцессор
2.Front-End
3.Оптимизации
4.Кодогенератор
5.Ассемблер
6.Линкер
++ Можно проследить запуски фаз компиляции (опция ‘--verbose’ в GCC)

диграфов (в С++)
Собственно препроцессирование
Подключение файлов (#include)
Макроподстановки (#define/undef/##)
Условная компиляция (#ifdef/if/else/elif/endif)
Управление строками (#line)
Диагностика (#error/warning)
++ Часто полезно получить препроцессированный код (опция ‘-E’ в GCC)

Preprocessing

Триграф

значение

??(

[

??)

]

??<

{

??>

}

??=

#

??/

\

??'

^

??!

|

??-

~

/??/
*
*/ # /*
*/ defi\
ne FO\
O 10\
20
#define FOO 1020

a = i+++j;

a = (i++) + j;

a = i + (++j);

диграфов (в С++)
Собственно препроцессирование
Подключение файлов (#include)
Макроподстановки (#define/undef/##)
Условная компиляция (#ifdef/if/else/elif/endif)
Управление строками (#line)
Диагностика (#error/warning)
++ Часто полезно получить препроцессированный код (опция ‘-E’ в GCC)

Preprocessing

Триграф

значение

??(

[

??)

]

??<

{

??>

}

??=

#

??/

\

??'

^

??!

|

??-

~

/??/
*
*/ # /*
*/ defi\
ne FO\
O 10\
20
#define FOO 1020

a = i+++j;

a = (i++) + j;

a = i + (++j);

С/С++ это файл после препроцессирования. В FORTRAN – один файл может содержать несколько TU.
Компилятор включает:
Компилятор переднего плана (Frontend) – строит по исходному коду промежуточное представление (Intermediate Representation – IR, или IL); включает
Лексический анализатор
Синтаксический анализатор
Семантический анализатор
Фазы Анализа и Оптимизаций представления
их много (Основная часть курса), но можно и уменьшить: разные уровни оптимизаций
Фазы Распределение регистров и кодогенерация
Результат работы компилятора – язык ассемблера (ассемблер, машинный язык) целевой архитектуры

Compiler

++ Можно проследить результат работы компилятора после каждой фазы
(опции ‘--dump-tree-all --dump-rtl-all’ в GCC)

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, @function
f:
.LFB0:
.cfi_startproc
leal (%rdi,%rdi), %eax
ret
.cfi_endproc

Code transformation

++ Бывает полезно посмотреть ассемблерный код (опция ‘-S’ в GCC)

Source code
AST
High-level IR
Low-level IR
assembler

a1

-8

a2

a1

a2

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):
С++: ‘one definition rule’
С: ‘tentative definition’ для неинициализированных глобалов
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: 000...00

data

code

heap

bss

data

code

file

memory

stack

навсегда
динамические библиотеки:.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 f@PLT
movq G2@GOTPCREL(%rip), %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

код
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

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

Libraries

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

Библиотеки

Libraries

них почти ничего не известно (пропреитарный код, который можно продавать)
Портирование имеющегося
Коммерческие Front-End’ы – Edison Design Group
Открытая система программирования GCC (GNU Compiler Collection)
Еще одна: LLVM (Low-Level Virtual Machine)
UTL (Universal Translating Library)

Creating/Poring TC

…

…

Входные языки

Целевые платформы

SUN
Compiler

MS
Compiler

GCC
LLVM

EDG Front-End

Intel
compiler

Elbrus
compiler

CG1

CG2

C++

C

F77

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

Простой пример

Example

– компоненты компилятора
Из MD генерируется RTL generator (expander) и кодогенератор
MD – описывает структуру генератора генератора кода

Описание Машины

Machine Description (MD)

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

Цикл работы компилятора

???(MD)

– шаблон инструкции в генерации кода
define_split – шаблон разбиения сложных шаблонов на более простые
define_expand – именнованный шаблон, используется для генерации RTL из GIMPLE
define_peephole – шаблон частной архитектурно-зависимой оптимизации
define_predicate – шаблон предиката (для проверки соответствия операндов инструкции)

Структура описания в GCC

GCC description structure

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

Двоичный интерфейс приложения

ABI

caller
f()
callee
g()

написана на ЯВУ с минимальными аппаратными зависимостями
Эффективность (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

во время компиляции (компилятор, утилиты 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

раз
По сути является JIT (Just-In-Time) компилятором (UCode – Собственный IR)
Имеет ряд стандартных утилит
Альтернатива – утилита Pin от Intel, настроена на x86, IA64, XScale
>100 утилит для Pin.
На горячем коде замедление 1.2-4 раза, на холодном 30-50 раз

framework

Valgrind

Valgrind

X86
PPC
…

Build IL

IL

Code gen

init IL

Instrumented IL

Tool

Memcheck – проверка памяти
Cachegrind – профиль кэша
Callgrind – профиль кэша+кода
Massif – профиль кучи
Helgrind – анализ многопоточности
Lackey – кол-во инструкций и BB
TreadSanitizer – новое от Google

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

Анализ производительности

Performance Analysis

26.95 48912/48965 BZ2_bzWrite [7]
[5] 73.8 0.00 26.98 48965 BZ2_bzCompress [5]
1.81 25.17 48965/48965 handle_compress [6]
0.00 0.00 53/56 isempty_RL [43]
-----------------------------------------------
1.81 25.17 48965/48965 BZ2_bzCompress [5]
[6] 73.8 1.81 25.17 48965 handle_compress [6]
5.10 19.95 273/273 BZ2_compressBlock [8]
0.12 0.00 7012881/7012881 add_pair_to_block [22]
0.00 0.00 270/273 prepare_new_block [42]
0.00 0.00 3/56 isempty_RL [43]
0.00 0.00 3/6 init_RL [47]
-----------------------------------------------
11.23 5.74 273/273 BZ2_blockSort [9]
[10] 46.4 11.23 5.74 273 mainSort [10]
5.74 0.00 316455844/316455844 mainGtU [15]
-----------------------------------------------

Пример профиля

Profile example

Место в профиле

Собств.
время

Время
потомков

Общее число вызовов

Откуда вызвали

Сколько вызвали отсюда

Листовая функция, вызывается из одного места в огромном цикле

Executable (Windows)
a.out – условно “непосредственный код”
COFF (XCOFF, ECOFF)

Executable Formats