Внутреннее представление компилятора Типы представлений и их особенности

Архитектура транслятора языка ВУ Исходный код Парсер Синтаксическое дерево Конвертер Машинно- независимое представление Оптимизации Машинно-зависимое представление Конвертер Кодогенератор test.s Оптимизации Front EndMiddle EndBack End

Архитектура двоичного транслятор Исходный двоичный код Декодер Декодированные команды Конвертер Машинно- независимое представление Оптимизации Машинно-зависимое представление Конвертер Кодогенератор test.s Оптимизации Front EndMiddle EndBack End

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

Структура IR Граф – Деревья – DAG – Граф потока управления – Граф зависимостей Линейная последовательность команд – Код стековой машины – Трехадресный код (четверки, тройки)

Древовидное представление z = x – 2 * y Абстрактное синтаксическое дерево: z x 2 - * y = Абстракция на уровне исходного кода + num 12 - write Val sp + Val sp read Num 4 * Num 2 + Val sp read Num 8 Явно выраженные вычисления адресов переменных, чтения и записи в память

Направленный ациклический граф (DAG) z = 2 * y – 2 * y * x Абстрактное синтаксическое дерево: z 2 - * y = * 2 * y x Направленный ациклический граф (DAG): z - = * 2 * y x

Линейные последовательности команд Operation L0: Operation Cond jump L1 Operation Uncond jump L0 L1: Operation Используемые операции зависят от уровня абстрактности и входного выходного языка Для полного представления исходного кода требуются операции передачи управления Популярные виды представления: 1. Код (абстрактной) стековой машины 2. Трехадресный код a.Четверки b.Тройки

Код стековой машины Использует соглашение о нахождении операндов в стеке Операции читают операнды из стека, удаляют их и записывают результат на стек + Очень компактное представление - Результаты и аргументы не выраженны явно в представленнии z = x – 2 * y push 2 push y mul push x sub pop z

Трехадресный код Совокупность оператора и трех адресов (операндов): двух аргументов и результата На практике в представлении могут встречаться команды – Без результата, одного или двух аргументов – С большим количеством аргументов – Количество таких команд мало Можно рассматривать как код абстрактной RISC-машины z = x – 2 * y t1 = 2 t2 = y t3 = t1 * t2 t4 = x t5 = t4 – t3 z = t5

Реализация в виде четверок (quadruples) Напрямую представлены имя операции, результат и аргументы z = x – 2 * y t1 = 2 t2 = y t3 = t1 * t2 t4 = x t5 = t4 – t3 z = t5 oparg1arg2res move2NULLt1 moveyNULLt2 mult1t2t3 subt4t3t5 movext4 movet5z NULL

Реализация в виде троек (triples) Временные переменные полностью замещаются ссылкой на производящую операцию z = x – 2 * y t1 = 2 t2 = y t3 = t1 * t2 t4 = x t5 = t4 – t3 z = t5 oparg1arg2 move2NULL loadyNULL mulOp 1Op 2 subOp 4Op 3 loadx save Op5 NULL z

Линейное представление (на примере LLVM) int func( int a, int b) { int c; if ( a > b) { c = a + 1; } else { c = a + b; } return c; } %cmp.res = icmp %a, %b br %cmp.res, label %if.then, label %if.else if.then: %c.0 = add %a, 1 br label %if.end if.else: %c.1 = add %a, %b br label %if.end if.end: %c.2 = phi [%c.0, %if.then], [%c.1, %if.else] ret %c.2

Граф потока управления %cmp.res = icmp %a, %b br %cmp.res, label %true, label %false true: %c.0 = add %a, 1 br label %end false: %c.1 = add %a, %b br label %end end: %c.2 = phi [%c.0, %true], [%c.1, %false] ret %c.2

Комбинированные представления Граф управления в вершинах которого находятся: – Линейные цепочки операций – Список корневых вершин деревьев Граф зависимостей, вершинами которого являются отдельные операции – Управление также может быть представлено в виде зависимостей

Аналитические структуры данных Строятся при помощи анализа основной части представления Могут быть временными (внутри фазы) или постоянными (сохраняются между фазами) Корректируются либо перестраиваются при преобразованиях представления

Примеры аналитических структур Граф потока управления – Классификация дуг – Циклы, дерево циклов – Доминаторы/Постдоминаторы Граф потока данных Граф зависимостей