Министерство образования Российской Федерации Московский Физико-Технический Институт (ГУ) Разработка средства анализа трассы исполнения двоично-транслированной программы в терминах промежуточного представления компиляции. Квалификационная бакалаврская работа студента 112 группы Факультета Радиотехники и Кибернетики Загребина Андрея Александровича Научный руководитель: Старший научный сотрудник Масленников Дмитрий Михайлович Москва, 2005

Описание проблемы отладки двоичного оптимизирующего компилятора: Intel x86 код – код Эльбрус 2000 Intel x86 код Двоичный оптимизирующий компилятор Процесс отладки: Dump-файл Информация о компиляции Промежуточное представление Исполняемый код Эльбрус 2000 Исполнение Trace-файл Трасса исполнения Информация о выполненных командах Ошибки исполнения Ошибки восстановления x86 контекста Выявление Причин Ошибок Исправление ошибок Нехватка информации о компиляции Необходимость сопоставления информации вручную ! Сильное различие ! Интерпретатор Архитектуры Эльбрус 2000 В связи с возникшей задачей было поставлено следующее техническое задание.

Техническое задание. 1. Выявить основные различия между представлением семантики в трассе результирующего исполняемого кода микропроцессора VLIW-архитектуры Эльбрус 2000 и промежуточным представлением двоичного оптимизирующего компилятора: Intel x86 код – код Эльбрус 2000, а также важную с точки зрения анализа разработчиком при отладке результирующего кода информацию из промежуточного представления компилятора, которая отсутствует в трассе исполнения. 2. По результатам анализа из предыдущего пункта разработать средство отладки двоичного компилятора Intel x86 -> Эльбрус 2000, позволяющего представить результат исполнения откомпилированной программы (трассу) в терминах промежуточного представления компилятора. 3. Разрабатываемое средство должно представлять из себя программу, запускаемую из командной строки в операционной системе Linux. 4. Программа должна обрабатывать трассу исполнения кода, полученного после компиляции любого кода платформы Intel x86, на интерпретаторах микропроцессора Эльбрус 2000 в том числе в режиме моделирования прерываний для тестирования механизма восстановления x86 контекста.

Оптимизирующий двоичный компилятор. начальная (front end) Синтаксический Семантический разбор Фазы анализа промежуточного представления Фазы оптимизаций опт. Код E2K Intel x86 код, информация о регионах, профильная информация Промежуточное Представление (IR) Операционная семантика Граф потока управления Control Flow Graph (CFG) Enter Op 1, Op 2 … переход Enter Op 1 Op 2 … переход Enter Op 1, Op 2 … переход Enter Op 1, Op 2 … переход Узлы CFG (Линейные участки кода) Обратная дуга Цикл первичная генерация и частичная оптимизация Абстрактные ОПЕРАЦИИ компилятора x86 адрес соответствующей x86 операции Номер операции … … … Фаза анализа управления …… Генер. кода … Имя операции Аргументы операции … Аналитические Структуры данных …

Понятия контрольной точки и контекста. Обработка любого возникшего прерывания без его потери!!! Последующее восстановление x86 контекста!!! Невосстанавливаемый Восстанавливаемый поставить контрольную точку (интеловская память) В компиляторе: ……………… T= STDSB … [P1] (X86Addr: 0x80481f1) ……………… T= SRP... [P1] (X86Addr: 0x80481f4) cc_addr= ……………… Прерывание обработка Компенсирующий код (восстанавливает x86 контекст) В трассе (для архитектуры Эльбрус 2000): SS ipd(2) eap(0) bap(0) srp(1) … В регистре RPR хранится адрес компенсирующего кода Для проверки механизма восстановления x86 контекста создан специальный вид интерпретатора lsim_trap, который сам генерирует псевдо - прерывания.

Dump-файл Содержит список операций промежуточного представления информацию компиляции о них и их планирование по тактам: Scheduled IRE2K of … T= ENTER (X86Addr:0x804834d) T= SETWD 0x (X86Addr: 0x ) T= SETBN 0x1778fe0 (X86Addr: 0x ) T= CTPD 6.-> C0 (X86Addr: 0x ) T= SETBP 0x1778fe0 (X86Addr: 0x ) ……………… ……………… // ТЕЛО T= MOVs Gs0 -> Rs26 (X86Addr: 0x ) T= STDSB … (X86Addr: 0x80481f1) T= SRP... (X86Addr: 0x80481f4) T= STDSW … (X86Addr: 0x80481e7) T= SRP... (X86Addr: 0x80481ea) T= ANDs Bs3 0xff -> Bs2 (X86Addr: 0x ) T= CLPAND BP1[F] BP2[F]->BP0[T](X86..:0x0.) T= BRANCH.c C0 BP3[T](X86Addr:0x ) T= END (X86Addr: 0x ) Oper2CodeInfo … T=0 U=0 1. ENTER addr= - Node 1 (loop 0) T=0 U= SETWD - s T=0 U= SETBN - s T=0 U= CTPD - s T=0 U= SETBP - s ……………… ……………… // ТЕЛО T=7 U= STDSB addr= - s T=7 U= STDSW - s T=7 U= MOVs - s T=7 U= ANDs - s T=7 U= SRP cc_addr= s T=7 U= SRP cc_addr= s T=7 U= CLPAND - s T=7 U= BRANCH - s T=7 U= END - s Дизассемблер Эльбрус 2000 Trace-файл 0000 HS 0000c d_1_region: CS c disp %ctpr1, M_a8e0 CS1 0c5fcfe0 setwd wsz = 0x60, nfx = 0x0 setbn rsz = 0x3f, rbs = 0x20, rcur = 0x3c setbp psz = 0x17 LTS c00 ……………… ……………… // ТЕЛО 0007 HS 9c : SS ct %ctpr1 ? %pred3 ipd 2 ALS0 10c0e09a adds,3 0, %g0, %r26 ALS1 0016d014 ands,2 %b[22], _f16,_lts0lo 0xff, %b[20] ALS2 2ec0d8af stdsw,2 %r47, [ _f32,_lts0 0x804a074 ] ALS5 2cc0d808 stdsb,2 %b[8], [ _f32,_lts0 0x804a016 ] PLS pass pass andp @p4 %pred0 ***** 0xa8b ***** HS 0 9c :CT %ctpr1(0xa880)t.p.%bp3 (1) SS ipd(2) eap(0) bap(0) srp(1) … ALS0 0 10c0e09a ADDs(0), %g0 (0x..)->%r26.. ALS d014 ANDs%br22 (0x..),(0x..)->%br20… ALS2 0 2ec0d8af STDSW %r47 (0x23f) ->.. ALS5 0 2c0d808 STDSB %br8 (0x57) ->.. PLS PASS %bp1 (0) (0) PASS %bp2 (1) (1) CLPAND %bp0 (0) ***** 0xa ***** HS c012 : CS c BRANCH %ctpr1 (0xa8e0) CS1 0 0c5fcfe0 SETR0 setbp(1) setbn(1) settr(0).. LTS c00 type(0) rpsz(0) wsz(0x60) nfx(0) x(0) ……………… ……………… // ТЕЛО

Анализ различий промежуточного представления компиляции и трассы исполнения (dump- и trace-файлов). В результате проведённого анализа были обнаружены следующие отличия. В трассе исполнения не хватает следующей информации о компиляции в терминах IR кода: Номеров операций в широких командах. Номеров узлов, в которых находятся широкие команды, встречаемые в трассе. (его имеет смысл ставить у команды только, если предыдущая команда находится в другом узле) У операций ненулевого x86 адреса (т.е. если операция не добавлена искусственно компилятором) соответствующих им операций Intel x86 архитектуры. Номера одной или двух операций SRP в широкой команде Номера операции, с которой связанна стоит данная SRP Адресов компенсирующих кодов, соответствующих исполнившимся операциям SRP А также информации, которую разработчику приходится находить вручную: Число итераций цикла Направление перехода в управляющем графе, т.е. номер узла, в который осуществляется переход Флага исполнения конкретной операции SRP (в трассе есть только флаг исполнения одной из операций SRP) Признака начала исполнения компенсирующего кода последней SRP

Реализация Средства dtlink. Dump-файл Информация о компиляции Промежуточное представление Trace-файл Трасса исполнения Информация о выполненных командах Выявление Причин Ошибок Сильное различие ! Разработанное Средство dtlink Новый Trace-файл Трасса исполнения Информация о выполненных командах в терминах компилятора и исполнения Программа написана на языке С и запускается с командной строки операционной системы Linux. Двоичный оптимизирующий компилятор Исполняемый код Эльбрус 2000 Исполнение Разработанное средство производит следующие действия: Разбирает выдачу компилятора Собирает информацию о компиляции Разбирает трассу исполнения кода Получает отсутствующую в трассе информацию об исполнении Вставляет в новую трассу - старую трассу - всю собранную информацию Выдаёт новую трассу

***** 0xa8b ***** [ SRP (1) (x86addr: 0x80481ea) (cc_addr: 0x8cf8 ) ] [ 921. SRP (1) (x86addr: 0x80481f4 ) (cc_addr: 0x96a8) ] HS 0 9c :CT %ctpr1(0xa880)tak.pred.%bp3 (1) Node 1 [0x ] SS ipd(2) eap(0) bap(0) srp(1) vfdi(0) … ALS0 0 10c0e09a 627. ADDs (0), %g0 (0x..) -> %r26 (0x..) [0x ] ALS d ANDs %br22 (0x..), (0x..) -> %br20 (0x..)[0x ] ALS2 0 2ec0d8af STDSW %r47 (0x23f) -> DS(..) [..] [0x80481e7] ALS5 0 2cc0d STDSB %br8 (0x57) -> DS(..) [..] [0x80481f1] PLS PASS %bp1 (0) (0) [0x ] PASS %bp2 (1) (1) CLPAND %bp0 (0) ***** 0xa ***** Node 1. 5 (1. Enter 0x804834d) HS c012 : CS c 943. BRANCH %ctpr1 (0xa8e0) [0x ] CS1 0 0c5fcfe SETR0 setbp(1) setbn(1) settr(0).. [0x ] LTS c00 type(0) rpsz(0) wsz(0x60) nfx(0) x(0) ……………… ……………… // ТЕЛО //Прерывание !!! ………………………………//Вызов компенсирующего кода Enter in COMP CODE of [ 921. SRP (x86addr: 0x80481f4) (cc_addr: 0x96a8) ] ***** 0x96a ***** ……………………….. Результат работы средства dtlink. Модифицированный trace-файл. Ошибки связанные с циклами неправильное построение условия выхода получение неправильного условия выхода в процессе итерации При сравнении трассы откомпилированного кода и трассы эталонного кода Сразу видно: - Отличие числа итераций - неправдоподобно большое число итераций

Пример 1 на падение интерпретатора lsim из-за ошибки преобразования операций. ***** 0xe ***** Node !ANDs %br3 (0x..),(0x..)->%br5 (0x..)[0x804852a] ………………………………………………………………………………… ***** 0xe ***** 31. !SUBs %br5 (0x..),(0x..)->%br3 (0x..)[0x ] ………………………………………………………………………………… ***** 0xe ***** 115.!CMPLEs %br3 (0x..), (0x...)->%bp1 (0)[0x ] ………………………………………………………………………………… ***** 0xe ***** 11.:CT %ctpr1 (0xe820) tak.pred. ~%bp1 (0) Node 3 [0x ] ………………………………………………… ***** 0xe ***** Node 3.0 ………………………………………………………………………………… 264. UDIVX %dr29 (0x..), (0x..) -> %br66 [0x ] ………………………………………………………………………………… exc_div: ( division by 0 or the quotient is too large ). Неправильная трасса кода полученного отлаживаемым компилятором Intel x86 code: a: andw $0xff00,0x804a05a : subw $0x300, 0x804a05a c: cmpw $0x3a00,0x804a05a : jle ***** 0xf5d ***** 27. ANDs %br8 (0x..),(0x..)->%br5 (0x..) [0x804852a] ………………………………………………………………………………… ***** 0xf ***** 31. SUBs %br7 (0x..),(0x..)->%br10 (0x..) [0x ] ………………………………………………………………………………… ***** 0xf ***** 34. SUBs FLH %br6 (0x..), (0x..)->%br6 (0x..) [0x804853c] ………………………………………………………………………… ***** 0xf ***** 35. CCTOLP CCTOPLE(0),%br6 (0x..)->%bp1 (1)[0x ] ………………………………………………………………………………… Правильная трасса кода полученного эталонным компилятором переход провал До c2do во фрагменте c: 27. ANDs Vs76.. -> Vs78 (X86Addr: 0x804852a) ANDs Vs78.. -> Vs79 (X86Addr: 0x ) 31. SUBs Vs79.. -> Vs81 (X86Addr: 0x ) ANDs Vs81.. -> Vs82 (X86Addr: 0x804853c) 34. SUBfh Vs82.. -> Vs83 (X86Addr: 0x804853c) 35. PLEs Vs83 -> P1 [T](X86Addr: 0x ) Формат 16 бит ! После c2do во фрагменте c: 25. LDDSH 0.. -> Vs76 (X86Addr: 0x804852a) 27. ANDs Vs76.. -> Vs78 (X86Addr: 0x804852a) 31. SUBs Vs78.. -> Vs81 (X86Addr: 0x ) 115. CMPLEs Vs81.. -> P1 [T](X86Addr: 0x ).. 11.BRANCH.c C0 BP1[F] (X86Addr:0x ) UDIVX Vs > Vs56> (X86Addr:0x ).. Формат 32 бита !

Пример 2 на не сличение контекста (lsim_trap) и перестановку местами контрольных точек Неправильная трасса кода полученного отлаживаемым компилятором Правильная трасса кода полученного эталонным компилятором ***** 0x87b ***** [ SRP (1) (x86addr: 0x80481ea) (cc_addr:0x8cf8) ] \\ SRP 1 [ 921. SRP (1) (x86addr: 0x80481f4) (cc_addr: 0x96a8) ] \\ SRP 2 HS 0 d : SS 0 0c ipd(0) eap(0) bap(0) srp(1) vfdi(1) … ALS2 0 3e93d STSSW %r24 (1) -> SS(…) […] [0x80481e7] ALS4 0 5cc MOVFI %xbr20 (…) -> %br17 (0x..) ALS5 0 2fa99e STDSD %dbr17 (0) -> DS(…) […] [0x80481f1] Псевдо прерывание ………………….. Enter in COMP CODE of [921. SRP (x86addr: 0x80481f4)(cc_addr: 0x96a8)] ***** 0x96a ***** ………………….. ***** 0x2b5b ***** HS : ALS c0e0 LDGDD GD(…) […] -> %dg13 (0x8030e7a) ………………….. ………………….. LSIM_TRAP: ОШИБКА!!! Ошибка восстановления контекста: ! context is damaged at 30048(0x7560), eip: 0x80481f4, srp_prev: 0x87b9 srp_curr: 0x87b9 ! edx(g13): prev 0x curr 0x8030e7a ***** 0x87b ***** [ 921. SRP (1) (x86addr: 0x80481f4) (cc_addr: 0x96a8) ] \\ SRP 2 [ SRP (1) (x86addr: 0x80481ea) (cc_addr:0x8cf8) ] \\ SRP 1 HS 0 d : SS 0 0c ipd(0) eap(0) bap(0) srp(1) vfdi(1) abg(0) …. ALS2 0 2fa99e STDSD %dbr17 (0) -> DS(…) […] [0x80481f1] ALS4 0 5cc MOVFI %xbr20 (…) -> %br17 (0x..) ALS5 0 3e93d STSSW %r24 (1) -> SS(…) […] [0x80481e7] Enter in COMP CODE of [ SRP (1) (x86addr: 0x80481ea) (cc_addr:0x8cf8) ] ***** 0x8cf ***** …………………………………………………………………………………………………….. ***** 0x2b ***** HS : ALS c0e0 LDGDD GD(…) […] -> %dg13 (0x ) До планирования: STDSD.. (X86Addr: 0x..) 921. SRP.. (X86Addr: 0x..) STSSW.. (X86Addr: 0x..) SRP.. (X86Addr: 0x..) После планирования: STDSD..(X86Addr: 0x..) SRP..(X86Addr: 0x..) STSSW..(X86Addr: 0x..) SRP..(X86Addr: 0x..) И окончательно (по шир. командам): STSSW addr= s SRP cc_addr= s STDSD - s SRP cc_addr= s

Результаты поведённой работы. 1. Выявлены основные различия между представлением семантики в трассе результирующего исполняемого кода микропроцессора VLIW-архитектуры Эльбрус 2000 и промежуточным представлением двоичного оптимизирующего компилятора: Intel x86 код – код Эльбрус 2000, а также важная с точки зрения анализа разработчиком при отладке результирующего кода информация из промежуточного представления компилятора, которая отсутствует в трассе исполнения. 2. По результатам анализа из предыдущего пункта разработано средство отладки двоичного оптимизирующего компилятора Intel x86 -> Эльбрус 2000, позволяющее представить результат исполнения откомпилированной программы (трассу) в терминах промежуточного представления компилятора. 3. Разработанное средство представляет из себя программу, написанную на языке С и запускаемую из командной строки в операционной системе Linux. 4. Программа обрабатывает трассу исполнения кода, полученного после компиляции любого кода платформы Intel x86, на интерпретаторах микропроцессора Эльбрус 2000 в том числе в режиме моделирования прерываний для тестирования механизма восстановления x86 контекста. Изученный материал: Особенности VLIW архитектуры Эльбрус Структура широкой команды. Структура системы двоичной оптимизирующей трансляции Стадии обработки входного кода двоичного оптимизирующего компилятора Операционная семантика промежуточного представления и граф потока управления в двоичном оптимизирующем компиляторе Понятие контрольной точки и восстановление Intel x86 контекста Режим интерпретации lsim_trap Разработанное средство используется при отладке промышленного двоичного оптимизирующего компилятора в фирме МЦСТ.