Представление информации
<<  Представление результатов работы педагогов в соответствии с требованиями аттестации на квалификационную категорию Принцип интеграции в реализации образовательных областей в ДОУ  >>
Московский физико-технический институт Выпускная квалификационная
Московский физико-технический институт Выпускная квалификационная
Общие понятия
Общие понятия
Использование форм ПП в процессе оптимизирующей компиляции
Использование форм ПП в процессе оптимизирующей компиляции
Проблематика
Проблематика
Подход к решению задачи
Подход к решению задачи
Схема верификации оптимизации
Схема верификации оптимизации
Этапы реализации транслятора СИПП
Этапы реализации транслятора СИПП
Моделирование ориентированного графа управления
Моделирование ориентированного графа управления
Моделирование ориентированного графа управления
Моделирование ориентированного графа управления
Моделирование регистров архитектуры «Эльбрус», представленных в ПП
Моделирование регистров архитектуры «Эльбрус», представленных в ПП
Моделирование операций ПП
Моделирование операций ПП
Моделирование предикатного режима исполнения операций
Моделирование предикатного режима исполнения операций
Моделирование типов переменных
Моделирование типов переменных
Моделирование вызова функций
Моделирование вызова функций
Моделирование стека данных
Моделирование стека данных
Пример вызова функции и смоделированного стека данных
Пример вызова функции и смоделированного стека данных
Пример вызова функции и смоделированного стека данных
Пример вызова функции и смоделированного стека данных
Моделирование APB (Array Prefetch Buffer)
Моделирование APB (Array Prefetch Buffer)
Моделирование асинхронной предподкачки
Моделирование асинхронной предподкачки
Заключение
Заключение

Презентация: «Система интерпретации промежуточного представления программы в оптимизирующем компиляторе». Автор: . Файл: «Система интерпретации промежуточного представления программы в оптимизирующем компиляторе.ppt». Размер zip-архива: 2354 КБ.

Система интерпретации промежуточного представления программы в оптимизирующем компиляторе

содержание презентации «Система интерпретации промежуточного представления программы в оптимизирующем компиляторе.ppt»
СлайдТекст
1 Московский физико-технический институт Выпускная квалификационная

Московский физико-технический институт Выпускная квалификационная

работа Система интерпретации промежуточного представления программы в оптимизирующем компиляторе

Студент: Битнер Вильгельм, 518 гр. Научный руководитель: Степанов П.А.

2 Общие понятия

Общие понятия

Промежуточное представление (ПП) – особая форма представления программы, предназначенного для эффективной генерации кода и проведения различных оптимизаций программы. Основные составляющие формы ПП Трехадресный код Ориентированный граф управления Типы ПП в оптимизирующем компиляторе архитектуры «Эльбрус» EIR – приближенная к языку Си форма ПП – основана на универсальных платформо-независимых средствах языка IRE2K – платформо-зависимая форма ПП – основана на машинном коде целевой архитектуры

3 Использование форм ПП в процессе оптимизирующей компиляции

Использование форм ПП в процессе оптимизирующей компиляции

4 Проблематика

Проблематика

Виды проявления ошибок Ошибки на этапе компиляции Ошибки на этапе исполнения Возникновение исключительной ситуации Возврат неверных результатов Задача: Быстро и эффективно локализовать ошибки в оптимизациях, приводящих к неверным результатам на этапах исполнения программы Сложность диагностики ошибки: Невозможно получить исполняемый файл непосредственно после применения конкретной оптимизации (без выполнения последующих фаз) Как следствие, трудно установить какая именно оптимизация выполняет некорректное преобразование

5 Подход к решению задачи

Подход к решению задачи

Разработать систему интерпретации промежуточного представления (СИПП) программы с целью верификации оптимизаций

6 Схема верификации оптимизации

Схема верификации оптимизации

7 Этапы реализации транслятора СИПП

Этапы реализации транслятора СИПП

Моделирование ориентированного графа управления Моделирование регистров архитектуры «Эльбрус», представленных в ПП Моделирование операций ПП Моделирование предикатного режима исполнения операций Моделирование типов переменных Моделирование вызова функций Моделирование стека данных Моделирование APB

8 Моделирование ориентированного графа управления

Моделирование ориентированного графа управления

Средства реализации Узел ? метка с характерным названием Дуга ? оператор «goto»

sint32_t main( sint32_t A1) { Rs( 0) = A1; /* CFG Start Node 0 */ nodestart0: goto nodeif8; /* CFG If Node 8 */ nodeif8: /* 25. MOVs Rs0 */ Vs(1) = Rs(0); /* 42. CMPLEs Vs1 */ Ps(0) = ( Vs(1) <= 1 ); /* 9. CTPD C0 = &&nodereturn2; /* 10. BRANCH C0 */ if ( !Ps(0) ) goto *C0; /* 11. END */ goto nodereturn3; ... /* CFG Stop Node 4 */ nodestop4: return ( result); }/* main */

int main( int argc) { if ( argc > 1 ) { return 1; } else { return 0; } }

9 Моделирование ориентированного графа управления

Моделирование ориентированного графа управления

Условные переходы If-конструкции Switch-конструкции Особенность реализации switch-конструкции Использование gnu-расширение компилятора gcc

void *_T_1[16]; int i_loop; for ( i_loop = 0; i_loop < 16; i_loop++) { _T_1[i_loop] = &&node96; } _T_1[13] = &&nodeif88; _T_1[11] = &&nodeif82; _T_1[4] = &&nodeif76; _T_1[2] = &&nodeif70; _T_1[9] = &&nodeif64; _T_1[12] = &&nodeif16; _T_1[15] = &&nodeif9; _T_1[0] = &&nodeif3; ... /* 31. CTPG */ C0 = _T_1[0]; /* 10. BRANCH C0 */ goto *C0;

10 Моделирование регистров архитектуры «Эльбрус», представленных в ПП

Моделирование регистров архитектуры «Эльбрус», представленных в ПП

Регистры архитектуры «Эльбрус» моделируются с помощью локальных переменных языка Си 32-х разрядные регистры моделируются переменными типа «int», 64-х разрядные - переменными типа «long long int»

11 Моделирование операций ПП

Моделирование операций ПП

Элементарные операции: замена аналогичными операциями языка Си (ADD ? «+»; DIV ? «/» и т.д.) Специфические операции: моделирование функциональности операции в отдельной процедуре с последующим вызовом процедуры вместо операции getf insf Операции доступа к памяти load/store -> чтение/запись по указателю Инициализация указателя аргументами операции

12 Моделирование предикатного режима исполнения операций

Моделирование предикатного режима исполнения операций

Предикат – регистр, смоделированный аналогично регистрам архитектуры «Эльбрус» (переменная Ps) Моделируется предикатный режим исполнения операции передачи управления

nodeif8: /* 23. ENTER // 3 */ /* 25. MOVs Rs0 -> Vs1 // 3 */ Vs(1) = Rs(0) /* 42. CMPLEs Vs1 0x1 -> P0 [T] // 3 */ Ps(0) = (Vs(1) <= 1) /* 9. CTPD -> C0 // 3 */ C0 = &&nodereturn2; /* 10. BRANCH C0 P0 [F] // 3 */ if ( !Ps(0) ) goto *C0; /* 11. END // 3 */ goto nodereturn3;

13 Моделирование типов переменных

Моделирование типов переменных

Базовые типы переменных (char, int, float и т.д.) Сложные типы переменных – все типы использованные в исходной программе в моделирующем коде восстановлены с помощью эквивалентных средств языка Си

struct xsym { ... }; struct xint { long xi_int; }; struct xfloat { float xf_float; }; typedef union { struct xsym n_xsym; struct xint n_xint; struct xfloat n_xfloat; }class152711628_t; struct node { sint8_t n_type; sint8_t n_flags; class152711628_t n_info; };

typedef struct node { char n_type; char n_flags; union { struct xsym { ... } n_xsym; struct xint { long xi_int; } n_xint; struct xfloat { float xf_float; } n_xfloat; } n_info; } NODE;

14 Моделирование вызова функций

Моделирование вызова функций

Передача параметров функции при ее вызове Объявление переменных необходимого количества и нужного типа Инициализация переменных путем копирования участка памяти из регистров или стека данных Вызов функции Вызов по косвенности – вызов через указатель, инициализированный смоделированным регистром подготовки передачи управления Регистр подготовки передачи управления моделируется как переменная типа void* Получение функцией параметров Копирование параметров в регистры или в стек данных

15 Моделирование стека данных

Моделирование стека данных

Стек данных есть массив типа char Работа со стеком организована через 2 реперные точки Rs( 8) и Rs( 9), соответствующие указателям stack-pointer и frame-pointer Стек моделируется в каждой процедуре как независимая составляющая

Исходная программа

struct TEST { int a; int b; int a1; int b1; double c; }; void foo( struct TEST test, short a1, char a2, int a3, double a4, long long a5, int a6, int a7, int a8, int a9, int a10 ) { ... } int main( void) { struct TEST test = {1, 2, 5, 8, 9.}; foo( test, 1, 2, 3, 4., 5, 6, 7, 8, 9, 10); return 0; }

16 Пример вызова функции и смоделированного стека данных

Пример вызова функции и смоделированного стека данных

Смоделированный код исходной программы

Реперные точки стека

Обработка параметров функции

void foo( struct TEST A1, sint16_t A2, sint8_t A3, sint32_t A4, float64_t A5, sint64_t A6, sint32_t A7, sint32_t A8, sint32_t A9, sint32_t A10, sint32_t A11) { DefT_t( R, 1024) = {0}; ... sint8_t Stack[size_S] = {0}; Rs( 8) = Stack + size_S; Rs( 9) = Stack; memcpy( &Rd( 0), ( &A1) + 0), 8); memcpy( &Rd( 1), ( &A1) + 8), 8); memcpy( &Rd( 2), ( &A1) + 16), 8); Rs( 3) = A2; Rs( 4) = A3; Rs( 5) = A4; Rd( 6) = A5; Rd( 7) = A6; Rs( 8) -= 104; *(Rs( 8) + 64) = A7; memset( (Rs( 8) + 68), 0, 4); *(Rs( 8) + 72) = A8; memset( (Rs( 8) + 76), 0, 4); *(Rs( 8) + 80) = A9; memset( (Rs( 8) + 84), 0, 4); *(Rs( 8) + 88) = A10; memset( (Rs( 8) + 92), 0, 4); *(Rs( 8) + 96) = A11; memset( (Rs( 8) + 100), 0, 4); ... }

17 Пример вызова функции и смоделированного стека данных

Пример вызова функции и смоделированного стека данных

Инициализация регистра подготовки передачи управления

Подготовка переменных

Вызов по косвенности

sint32_t main( void) { ... /* 30. CTPDCR [DISP 2 `foo`] -> C0 // 30 */ C0 = &foo; /* 31. CALL C0 // 30 */ { struct TEST t1_31; memcpy( (&t1_31 + 0), &Bd( 0), 8); memcpy( (&t1_31 + 8), &Bd( 1), 8); memcpy( (&t1_31 + 16), &Bd( 2), 8); { sint16_t t2_31 = Bs(3); { sint8_t t3_31 = Bs(4); { sint32_t t4_31 = Bs(5); { float64_t t5_31 = Bd(6); { sint64_t t6_31 = Bd(7); { sint32_t t7_31 = *(Rs( 9) + 64); { sint32_t t8_31 = *(Rs( 9) + 72); { sint32_t t9_31 = *(Rs( 9) + 80); { sint32_t t10_31 = *(Rs( 9) + 88); { sint32_t t11_31 = *(Rs( 9) + 96); { typedef void proc_31( struct TEST, sint16_t, sint8_t, sint32_t, float64_t, sint64_t, sint32_t, sint32_t, sint32_t, sint32_t, sint32_t); ((proc_31 *)C0)(t1_31, t2_31, t3_31, t4_31, t5_31, t6_31, t7_31, t8_31, t9_31, t10_31, t11_31); } }}}}}}}}}}} ... }

18 Моделирование APB (Array Prefetch Buffer)

Моделирование APB (Array Prefetch Buffer)

Асинхронная предподкачка Подкачка необходимых элементов массива заранее перед исполнением Применение только для самых вложенных циклов APB – часть механизма предподкачки – временная память для подкаченных элементов массива циклического фрагмента программы Важность асинхронной предподкачки Ускорение процесса обращения в память во время исполнения и, как следствие, уменьшение времени исполнения программы Моделирование Определение буфера, соответствующему физической реализации APB Предварительное заполнение буфера (предподкачка) Инициализация базы массива Заполнение буфера начиная с инициализированной базы Последующее заполнение буфера по мере его освобождения, что является продолжением предварительного чтения

19 Моделирование асинхронной предподкачки

Моделирование асинхронной предподкачки

Чтение из буфера APB

Начало асинхронной предподкачки в буфер APB

Начинается загрузка программы асинхронной предподкачки в APB

Инициализация регистров доступа к массиву

Остановка асинхронной предподкачки

node 51

CTPL AAU BAP

node 50

MOVA

node 52

EAP

nodeif50: if( !Was_Prefetch ) { Was_Prefetch = 1; IntroduceLDOVL( &apb, 255); BAP( &apb, 0, -1); } /* 129. ENTER // 6 */ /* 130. SHLs Vs0 0x2 -> Vs4 // 8 */ Vs(4) = (Vs(0) << 2); /* 164. MOVAW No.0 ind 0 am 1 -> Vs6 // 8 */ Vs(6) = mova( 0, 0, 1, 1, &apb); /* 132. ADDs Vs1 Vs6 -> Vs1 // 8 */ Vs(1) = (Vs(1) + Vs(6)); /* 133. ADDs Vs0 0x1 -> Vs0 // 6 */ Vs(0) = (Vs(0) + 1); /* 134. CMPLs Vs0 0x64 -> P1 [T] // 6 */ Ps(1) = (Vs(0) < 100); /* 135. CTPD -> C0 // 6 */ C0 = &&nodeif50; /* 136. BRANCH C0 P1 [T] // 6 */ if ( Ps(1) ) goto *C0; /* 137. END // 6 */ goto node52;

int foo ( int ar[]) { int i, sum; for ( i = 0; i < 100; i++ ) { sum += ar[i]; } return (int)(sum/100); } int main ( void) { int i, a[100]; for ( i = 0; i < 100; i++ ) { a[i] = i; } printf( "Average = %d\n", foo( a)); return 0; }`

node52: /* 140. ENTER // 6 */ /* 141. END // 6 */ STOP_APB( &apb); goto nodereturn4;

node51: /* 138. ENTER // 6 */ /* 145. MOVs 0x64 -> Vs10 // 6 */ Vs(10).i = 100; ... /* 159. ADDs Vs14 Vs2 -> Vs3 // 6 */ Vs(3) = (Vs(14) + Vs(2)); /* 160. AAURWs Vs3 -> AAIND // 6 */ AAIND(1) = Vs(3); /* 157. CTPL -> C1 // 6 */ AAIND( 0) = 0; AAINCR( 0) = 1; CTPL_node = &&continue_157; goto node53; continue_157: /* 163. AAURWq Vq128 -> AAD // 6 */ AAD(0) = Vd(128); *(&AAD(0) + 1)= *(&Vd(128) + 1); /* 139. END // 6 */ goto nodeif50;

20 Заключение

Заключение

Разработана система интерпретации промежуточного представления программы Произведено успешное тестирование системы на 230 тестах пакета тестов SpecPerf (пакет тестов для операционного контроля производительности оптимизирующего компилятора) Реализована возможность трансляции 20 оптимизаций Дальнейшие развитие СИПП Завершение отладки на пакете тестов SpecPerf Покрытие всей линейки оптимизации

«Система интерпретации промежуточного представления программы в оптимизирующем компиляторе»
http://900igr.net/prezentacija/informatika/sistema-interpretatsii-promezhutochnogo-predstavlenija-programmy-v-optimizirujuschem-kompiljatore-226715.html
cсылка на страницу

Представление информации

12 презентаций о представлении информации
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Представление информации > Система интерпретации промежуточного представления программы в оптимизирующем компиляторе