Динамическая генерация кода

Курсовая работа

По дисциплине: «Системное программирование»

На тему «Динамическая генерация кода»

2009

Оглавление

1. Введение в динамическую генерацию кода

2. Абстрактный синтаксис выражений

3. Отображение абстрактного синтаксиса выражений в CIL

3.1 Оптимизация линейных участков кода

3.2 Генерация развилок

4. Абстрактный синтаксис логических выражений

1. Введение в динамическую генерацию кода

Динамическая генерация кода - это прием программирования, заключающийся в том, что фрагменты кода порождаются и запускаются непосредственно во время выполнения программы. Этот прием был известен достаточно давно, но усложнение архитектуры компьютеров, и, что особенно важно, усложнение наборов команд процессоров привело к тому, что в последние 10-15 лет динамическая генерация кода в некоторой степени потеряла популярность.

Целью динамической генерации кода является использование информации, доступной только во время выполнения программы, для повышения качества исполняемого кода. В терминах метавычислений можно сказать, что динамическая генерация кода позволяет специализировать фрагменты программы по данным, известным во время выполнения.

В некотором смысле, любой JIT-компилятор как раз использует динамическую генерацию кода: имея некоторую программу, записанную на промежуточном языке (байт-коде), и зная, какой процессор работает в системе, JIT-компилятор динамически транслирует программу в инструкции этого процессора. При этом можно считать, что тип процессора - эта как раз та часть информации, которая становится известной только во время выполнения программы.

Естественно, не стоит чересчур увлекаться динамической генерацией кода: этот прием далеко не всегда дает ускорение программы. Можно сказать, что применение динамической генерации оправдано, если:

процесс вычислений в некотором фрагменте программы преимущественно определяется информацией, известной только во время выполнения;

запуск этого фрагмента осуществляется многократно;

выполнение фрагмента связано с существенными затратами времени процессора.

В .NET доступно два способа организации динамической генерации кода:

порождение программы на языке C# и вызов компилятора C#;

непосредственное порождение метаданных и CIL-кода.

Если сравнить эти два способа, можно придти к выводу, что порождение C#-программы несколько проще, нежели генерация CIL-кода.

Однако, наличие в библиотеке классов пространства имен System.Reflection.Emit позволяет избежать рутинных и трудоемких операций по работе с физическим представлением метаданных и CIL-кода. Кроме того, генерация CIL-кода выполняется на порядок быстрее и дает большую гибкость. Поэтому для программиста, знакомого с набором инструкций CIL, второй способ является более предпочтительным.

2. Абстрактный синтаксис выражений

Пусть наши выражения оперируют с константами, переменными и параметрами. Разрешим использование в выражениях как значений примитивных типов, так и объектов (в частности, массивов). В качестве операций мы будем использовать четыре арифметические бинарные операции, унарный минус, обращение к полю объекта, доступ к элементу массива и вызов экземплярного метода объекта.

Пусть абстрактный синтаксис для наших выражений содержит правила, приведенные в таблице 5.2.

3. Отображение абстрактного синтаксиса выражений в CIL

Определим набор функций, отображающих различные деревья абстрактного синтаксиса в соответствующие им последовательности инструкций CIL.

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

GenExpr[const c] = нужный вариант инструкции ldc;

GenExpr[local x] = ldloc x;

GenExpr[arg x] = ldarg x;

GenExpr[Expr1 index Expr2] =

GenExpr[Expr1],

GenExpr[Expr2],

ldelem.нужный тип;

GenExpr[Expr field f] =

GenExpr[Expr],

ldfld f;

GenExpr[minus Expr] =

GenExpr[Expr],

neg;

GenExpr[Expr1 BinOp Expr2] =

GenExpr[Expr1],

GenExpr[Expr2],

GenBinOp[BinOp];

GenExpr[local x assign Expr] =

GenExpr[Expr],

dup,

stloc x;

GenExpr[arg x assign Expr] =

GenExpr[Expr],

dup,

starg x;

GenExpr[Expr1 index Expr2 assign Expr3] =

GenExpr[Expr1],

GenExpr[Expr2],

GenExpr[Expr3],

dup,

stloc временная переменная,

stelem.нужный тип,

ldloc временная переменная;

GenExpr[Expr1 field f assign Expr2] =

GenExpr[Expr1],

GenExpr[Expr2],

dup,

stloc временная переменная,

stfld f,

ldloc временная переменная;

GenExpr[Expr call s ArgList] =

GenExpr[Expr],

GenArgList[ArgList],

call(callvirt) s;

GenArgList[Expr ArgList] =

GenExpr[Expr],

GenArgList[ArgList];

GenArgList[пусто] = ;

GenBinOp[plus] = add;

GenBinOp[minus] = sub;

GenBinOp[mul] = mul;

GenBinOp[div] = div;

3.1 Оптимизация линейных участков кода

Рис. 5.1.  Peephole-оптимизация

Зачастую бывает удобно разделить фазы генерации и оптимизации кода. Это позволяет существенно упростить генератор, сделать его независимым от оптимизатора и, кроме того, повторно использовать оптимизатор с другими генераторами.

Существует большое количество методов оптимизации, но в контексте динамической генерации кода, требующей быстрой работы оптимизатора, не все эти методы применимы. Поэтому мы рассмотрим один из самых простых методов - так называемую peephole-оптимизацию.

Суть peephole-оптимизации заключается в том, что оптимизатор ищет в коде метода сравнительно короткую последовательность инструкций, удовлетворяющую некоторому образцу, и заменяет ее более эффективной последовательностью инструкций.

Алгоритм peephole-оптимизации использует понятие фрейма. Фрейм можно представить как окошко, двигающееся по коду метода. Содержимое фрейма сравнивается с образцом, и в случае совпадения выполняется преобразование (см. рис. 5.1).

Peephole-оптимизация линейного участка кода должна выполняться многократно до тех пор, пока на очередном проходе фрейма по этому участку кода не будет найдено ни одного образца. С другой стороны, алгоритм peephole-оптимизации может быть остановлен в любой момент, что позволяет добиться требуемой скорости работы оптимизатора.

В таблице 5.3 приведен список некоторых образцов и замен, которые можно использовать для peephole-оптимизации CIL-кода.

3.2 Генерация развилок

Генерация кода, содержащего инструкции переходов, представляет некоторую сложность по сравнению с генерацией линейного кода. Дело в том, что появляются переходы вперед по коду, то есть переходы на инструкции, которые еще не были сгенерированы. Общий метод решения этой проблемы заключается в том, что такие инструкции переходов генерируются частично, то есть сначала вместо них в код вставляются заглушки, в которых не прописаны адреса переходов, а затем, когда адрес становится известен, заглушки заменяются на настоящие инструкции переходов.

Интересен факт, что генерация развилок существенно упрощается, если в процессе генерации придерживаться определенных требований структурированной парадигмы в программировании. Эти требования заключаются в том, что в генерируемой программе используются только пять структурных конструкций, а именно: последовательность (рис. 5.2a), выбор (рис. 5.2b), множественный выбор (рис. 5.2c), цикл с предусловием (рис. 5.2d) и цикл с постусловием (рис. 5.2e). При этом конструкции могут быть вложены друг в друга.

Рис. 5.2.  Peephole-оптимизация

Структурные конструкции удобны тем, что имеют ровно один вход и ровно один выход. Этот факт в сочетании с тем, что они вкладываются друг в друга, позволяет использовать для их порождения рекурсивные алгоритмы. В данном разделе мы предложим как раз рекурсивный вариант генерации структурных конструкций.

4. Абстрактный синтаксис логических выражений

Будем рассматривать логические выражения, которые содержат арифметические выражения, рассмотренные ранее, в качестве подвыражений. Пусть также логические выражения содержат операции сравнения (равно, меньше, больше) и логические операции (логическое И, логическое ИЛИ, логическое НЕ).

Дополним абстрактный синтаксис выражений, приведенный ранее в данной главе, новым нетерминалом LogExpr. Правила для этого нетерминала приведены в таблице 1.