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

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

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

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

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

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

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

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

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

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

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

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

18 стр., 8505 слов

Проектирование динамического 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

Больше