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

метки: Генерация, Выражение, Инструкция, Операция, Starg, Динамический, Объект, Genbinop

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

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

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

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

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

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

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

• порождение программы на языке C# и вызов компилятора C#;
• непосредственное порождение метаданных и CIL-кода.

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

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

Проектирование динамического web-сайта коммерческой организации ...

... работы (ВКР) является приобретение навыков решения задачи проектирования динамического web -сайта ... программы. 10. ГОСТ 19.402-78- Документация на АСУ. Общие к выполнению ... 1. Мобильный сайт ООО “Посредник” как объект проектирования 1.1 Описание ... работе применены термины с соответствующими определениями и сокращениями, установленные как нормативными документами, так и данными методических разработок. ...

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

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

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

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

Таблица 5.2. Абстрактный синтаксис выражений
Правило	Описание
Expr ::= const c	Некоторая константа. Мы не уточняем тип константы, так как для дальнейшего изложения это несущественно. Это может быть целое число, число с плавающей запятой, строка, значение null
Expr ::= local x	Локальная переменная с именем х
Expr ::= arg x	Параметр метода с именем х
Expr ::= Expr index Expr	Доступ к элементу массива. Здесь первое выражение должно возвращать ссылку, а второе — целое число, означающее индекс элемента
Expr ::= Expr field f	Доступ к полю f объекта
Expr ::= minus Expr	Унарный минус
Expr ::= Expr BinOp Expr	Бинарная арифметическая операция
Expr ::= local ? assign Expr	Операция присваивания переменной х значения выражения
Expr ::= arg ? assign Expr	Операция присваивания параметру х значения выражения
Expr ::= Expr index Expr assign Expr	Операция присваивания элементу массива значения выражения
Expr ::= Expr field f assign Expr	Операция присваивания полю f объекта значения выражения
Expr ::= Expr call s Arglist	Вызов экземплярного метода s для некоторого объекта с передачей списка фактических параметров
Arglist ::= Expr Arglist	Непустой список фактических параметров метода
Arglist ::= пусто	Пустой список фактических параметров метода
BinaryOp ::= plus	Сложение
BinaryOp ::= minus	Вычитание
BinaryOp ::= mul	Умножение
BinaryOp ::= div	Деление

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

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

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

Таблица 5.3. Некоторые образцы и замены для peephole-оптимизации CIL-кода
Образец	Замена
stloc(starg) x ldloc(Ldarg) х	dup stloc(starg) x
ldloc(ldarg) x ldloc(ldarg) x	ldloc(ldarg) x dup
ckfinite ckfinite	ckfinite
not(neg) pop	pop
add(sub, mul, div,…) pop	pop pop
idc.i4.0 add(sub)	—
ldloca(ldarga) x initobj int32	idc.i4.0 stloc(starg) x
stloc(starg) x ldloc(ldarg) y ldloc(ldarg) x add (или любая коммутативная бинарная операция)	dup stloc(starg) x ldloc(ldarg) y add (или любая коммутативная бинарная операция)

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

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

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

При этом конструкции могут быть вложены друг в друга.

Рис. 5.2.

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

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

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

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

Таблица 1. Абстрактный синтаксис логических выражений
Правило	Описание
LogExpr ::= Expr	Вырожденный случай, когда логическое выражение не содержит ни одной логической операции или операции сравнения
LogExpr ::= LogExpr ComparisonOp LogExpr	Сравнение двух выражений
LogExpr::= LogExpr and LogExpr	Применение логического И
LogExpr::= LogExpr or LogExpr	Применение логического ИЛИ
LogExpr ::= not LogExpr	Применение логического НЕ
ComparisonOp ::= equal	Равенство
ComparisonOp ::= less	Меньше
ComparisonOp ::= greather	Больше