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

Обобщенный алгоритм интегрирования

Для интегрирования функций нам потребуется некое представление функции, которое бы не зависело от конкретного способа вычисления значения функции. Идеальным вариантом такого представления является абстрактный класс Function:

public abstract class Function
{
 public abstract double Eval(double x);
}

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

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

static double Integrate(Function f, double a, double b, int n)
{
  double h = (b-a)/n, sum = 0.0;
  for (int i = 0; i < n; i++)
    sum += h*f.Eval((i+0.5)*h);
  return sum;
}

Для проверки работоспособности алгоритма можно объявить тестовый класс TestFunction, реализующий вычисление функции f(x) = x * sin(x):

public class TestFunction: Function
{
 public override double Eval(double x)
  {
     return x * Math.Sin(x);
  }
}

Представление выражений

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

Детали синтаксического анализа и представления выражений мы рассматривать не будем: интересующиеся могут обратиться к полным исходным текстам примера. Скажем лишь, что анализ осуществляется методом рекурсивного спуска и транслирует выражение в дерево, в узлах которого расположены объекты, представляющие арифметические операции и их операнды. Каждый из этих объектов является экземпляром одного из четырех классов, обозначающих числовые константы, переменные, унарные и бинарные операции. Причем все эти классы наследуют от абстрактного класса Expression:

public abstract class Expression
{
 public abstract string GenerateCS();
 public abstract void GenerateCIL(ILGenerator il);
 public abstract double Evaluate(double x);
}

В классе Expression объявлены три абстрактных метода, которые каждый класс-наследник реализует по-своему. Метод Evaluate выполняет непосредственное вычисление значения выражения, метод GenerateCS транслирует выражение в фрагмент программы на C#, а метод GenerateCIL транслирует выражение в CIL-код.

Вопросы генерации кода будут обсуждаться в следующих разделах, поэтому сейчас мы только приведем пример CIL-кода, генерируемого методом GenerateCIL для дерева объектов, которые представляют выражение "2*x*x*x+3*x*x+4*x+5":

ldc.r8   2.0
ldarg.1
mul
ldarg.1
mul
ldarg.1
mul
ldc.r8   3.0
ldarg.1
mul
ldarg.1
mul
add
ldc.r8   4.0
ldarg.1
mul
add
ldc.r8   5.0
add

Метод GenerateCS фактически восстанавливает из дерева строковое представление выражения и в особых комментариях не нуждается.

Трансляция выражений в C#

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

В нашем примере динамическую генерацию сборки осуществляет статический метод CompileToCS, который получает транслируемое выражение в виде объекта класса Expression и возвращает объект Function:

static Function CompileToCS(Expression expr)
{
 ICodeCompiler compiler = new CSharpCodeProvider().CreateCompiler();
 CompilerParameters parameters = new CompilerParameters();

 parameters.ReferencedAssemblies.Add("System.dll");
 parameters.ReferencedAssemblies.Add("Integral.exe");
 parameters.GenerateInMemory = true;

  string e = expr.GenerateCS();
  string code = "public class FunctionCS: Function\n"+
    "{\n"+
    "  public override double Eval(double x)\n"+
    "  {\n"+
    "  	return "+e+";\n"+
    "  }\n"+
    "}\n";
    
 CompilerResults compilerResults =
 compiler.CompileAssemblyFromSource(parameters,code);
 Assembly assembly = compilerResults.CompiledAssembly;
 return assembly.CreateInstance("FunctionCS") as Function;
}

Классы, отвечающие за компиляцию исходного кода, относятся к пространству имен System.CodeDom.Compiler.

Основную функциональность, необходимую нам для компиляции сгенерированной C#-программы, обеспечивает класс CSharpCodeProvider. Метод CreateCompiler этого класса создает экземпляр компилятора C#, к которому можно обращаться через интерфейс ICodeCompiler.

Параметры компиляции задаются через объект класса CompilerParameters. В нашем случае это имена сборок, импортируемых генерируемой программой: System.dll и Integral.exe. Обратите внимание, что Integral.exe - это сборка, получаемая при компиляции рассматриваемого нами примера. Она импортируется по причине того, что динамически генерируемый класс FunctionCS должен наследовать от определенного в ней абстрактного класса Function.

Параметры компиляции и строка, содержащая текст программы, передаются методу CompileAssemblyFromSource экземпляра компилятора C#. Метод компилирует программу и возвращает объект класса CompilerResults, содержащий результаты компиляции. Из этого объекта мы можем получить объект рефлексии Assembly, представляющий созданную в памяти динамическую сборку. Используя данный объект, мы создаем экземпляр определенного в динамической сборке класса FunctionCS, который в дальнейшем может быть использован для вычисления значения функции в процессе интегрирования.

Трансляция выражений в CIL

Более сложный, но эффективный способ динамической генерации кода предоставляется классами, относящимися к пространству имен System.Reflection.Emit. Эти классы в нашем примере используются в статическом методе CompileToCIL, который осуществляет трансляцию выражения напрямую в CIL:

static Function CompileToCIL(Expression expr)

Метод начинается с создания заготовки для будущей динамической сборки. Сборка будет выполняться в том же домене приложений, что и основная программа, поэтому объектную ссылку на домен приложений мы получаем путем вызова статического метода Thread.GetDomain. Затем вызываем метод DefineDynamicAssembly домена приложений и получаем объект класса AssemblyBuilder, позволяющий строить динамическую сборку:

AppDomain appDomain = Thread.GetDomain();
AssemblyName assemblyName = new AssemblyName();
assemblyName.Name = "f";
AssemblyBuilder assembly = 
   appDomain.DefineDynamicAssembly(
    assemblyName, 
    AssemblyBuilderAccess.RunAndSave
  );

Теперь мы можем создать в сборке модуль и добавить в него класс FunctionCIL, наследующий от класса Function. Обратите внимание, что при генерации кода через классы пространства имен System.Reflection.Emit явно прописывать импортируемые сборки не надо (например, не надо прописывать сборку Integral.exe, из которой импортируется класс Function ), так как это выполняется автоматически:

ModuleBuilder module = 
  assembly.DefineDynamicModule("f.dll", "f.dll");
TypeBuilder typeBuilder = 
  module.DefineType(
    "FunctionCIL",
    TypeAttributes.Public | TypeAttributes.Class,
    typeof(Function)
  );

В каждом классе должен быть конструктор. Компилятор C# создает конструкторы без параметров по умолчанию, поэтому при генерации C#-кода нам не надо было явно объявлять конструктор в классе FunctionCS. Однако, при генерации динамической сборки через классы пространства имен System.Reflection.Emit конструкторы автоматически не добавляются, и нам придется сделать это самостоятельно:

ConstructorBuilder cons =
  typeBuilder.DefineConstructor(
    MethodAttributes.Public,
    CallingConventions.Standard,
    new Type[] { }
  );
ILGenerator consIl = cons.GetILGenerator();
consIl.Emit(OpCodes.Ldarg_0);
consIl.Emit(OpCodes.Call,
  typeof(object).GetConstructor(new Type[0]));
consIl.Emit(OpCodes.Ret);

Разобравшись с конструктором, переходим к методу Eval. Как уже говорилось, код этого метода почти полностью генерируется в методе GenerateCIL выражения, остается лишь добавить в конец инструкцию ret:

MethodBuilder evalMethod =
  typeBuilder.DefineMethod(
    "Eval",
    MethodAttributes.Public | MethodAttributes.Virtual,
    typeof(double),
    new Type[] { typeof(double) }
  );

ILGenerator il = evalMethod.GetILGenerator();
expr.GenerateCIL(il);
il.Emit(OpCodes.Ret);

Итак, мы закончили формирование класса FunctionCIL. Осталось создать для него объект рефлексии и через этот объект вызвать конструктор:

Type type = typeBuilder.CreateType();
ConstructorInfo ctor = type.GetConstructor(new Type[0]);
return ctor.Invoke(null) as Function;

Таким образом, получается объект класса FunctionCIL, который в дальнейшем можно использовать для вычисления значения функции в процессе интегрирования.

Сравнение эффективности трех способов вычисления выражений

Давайте оценим эффективность рассмотренных способов вычисления выражений при интегрировании. Для этого будем интегрировать функцию "2*x*x*x+3*x*x+4*x+5" от 0.0 до 10.0 с 10000000 разбиений.

В таблице 5.1 представлены результаты измерений, проведенных на компьютере с процессором Intel Pentium 4 с тактовой частотой 3000 МГц и 1 Гб оперативной памяти.

Результаты показывают, что динамическая генерация кода может на два порядка уменьшить время работы программы.

Генерация линейных участков кода для стековой машины

В этом разделе мы рассмотрим специфику генерации линейных участков кода на языке CIL.

Линейными участками мы будем называть участки кода, не содержащие развилок и защищенных блоков.

Генерация кода для выражений

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

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

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

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

Отображение абстрактного синтаксиса выражений в 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;

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

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

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

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

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

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

В таблице 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 (или любая коммутативная бинарная операция)

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

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

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

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

Генерация кода для логических выражений

Логические выражения отличаются от рассмотренных ранее в этой главе арифметических выражений тем, что могут вычисляться не полностью. Например, в выражении

(a = 10) and (sin(x) = 0.5)

второе равенство имеет смысл вычислять, только если первое равенство истинно (то есть если значение переменной a равно 10).

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

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

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

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

LogExpr ::= Expr

LogExpr ::= LogExpr
 ComparisonOp LogExpr

LogExpr ::= LogExpr
 and LogExpr

LogExpr ::= LogExpr
 or LogExpr

LogExpr ::= not LogExpr

ComparisonOp ::= equal

ComparisonOp ::= less

ComparisonOp ::=  greather

Отображение абстрактного синтаксиса логических выражений в CIL

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

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

GenLogExpr[Expr] = GenExpr[Expr];
GenLogExpr[LogExpr1 ComparisonOp LogExpr2] =
  GenLogExpr[LogExpr1],
  GenLogExpr[LogExpr2],
  GenComparisonOp[ComparisonOp];
GenLogExpr[LogExpr1 and LogExpr2] =
  GenLogExpr[LogExpr1],
  dup,
  brfalse LABEL,
  GenLogExpr[LogExpr2],
  and,
  LABEL: ;
GenLogExpr[LogExpr1 or LogExpr2] =
  GenLogExpr[LogExpr1],
  dup,
  brtrue LABEL,
  GenLogExpr[LogExpr2],
  or,
  LABEL: ;
GenLogExpr[not LogExpr] =
  GenLogExpr[LogExpr],
  not;
ComparisonOp[equal] = ceq;
ComparisonOp[less] = нужный вариант инструкции clt;
ComparisonOp[greater] = нужный вариант инструкции cgt;

Генерация кода для управляющих конструкций

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

Абстрактный синтаксис управляющих конструкций

В таблице 5.5 приведен абстрактный синтаксис для последовательности, выбора и циклов с предусловием и постусловием. При записи абстрактного синтаксиса используется определенный ранее нетерминал LogExpr для представления условий выбора и циклов.

Statement ::= Expr

Statement ::= if LogExpr
  StatementList else
  StatementList

Statement ::= while
 LogExpr StatementList

Statement ::= do
 StatementList
 while LogExpr

Statement ::=
 Statement StatementList

StatementList ::= пусто

Отображение абстрактного синтаксиса управляющих конструкций в CIL

Как уже говорилось, структурные управляющие конструкции допускают рекурсивный алгоритм генерации. Поэтому мы можем определить набор функций GenStatement, транслирующих деревья абстрактного синтаксиса в последовательности инструкций.

GenStatement[Expr] =
  GenExpr[Expr],
  pop;
GenStatement[if LogExpr StatementList1 else StatementList2] =
  GenLogExpr[LogExpr],
  brfalse LABEL1,
  GenStatementList[StatementList1],
  br LABEL2,
  LABEL1: GenStatementList[StatementList2],
  LABEL2: ;
GenStatement[while LogExpr StatementList] =
  LABEL1: GenLogExpr[LogExpr],
  brfalse LABEL2,
  GenStatementList[StatementList],
  br LABEL1,
  LABEL2: ;
GenStatement[do StatementList while LogExpr] =
  LABEL: GenStatementList[StatementList],
  GenLogExpr[LogExpr],
  brtrue LABEL;
GenStatementList[Statement StatementList] =
  GenStatement[Statement],
  GenStatementList[StatementList];
GenStatementList[пусто] = ;

Оптимизация кода, содержащего развилки

Рассмотрим несколько простых методов оптимизации кода, содержащего развилки, а именно:

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

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

Это преобразование уменьшает количество присваиваний. Оно осуществляется только для переменных, адреса которых не используются. Под переменными мы будем понимать как локальные переменные, так и параметры методов.

Другими словами, избыточные инструкции stloc и starg удаляются только для переменных, не использующихся в инструкциях ldloca и ldarga.

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

Инструкции ldloc(ldarg) X и stloc(starg) X будем называть инструкциями использования переменной X.

Мы будем говорить, что в графе потока управления инструкция использования B следует за инструкцией использования A на пути w, если:

Граф использования переменной X - это ориентированный граф, в узлах которого находятся инструкции использования переменной X, а дуги задают отношение следования для этих инструкций. То есть, если инструкция B следует за инструкцией A на каком-либо пути в графе потока управления, то в графе использования переменной X имеется дуга от инструкции A к инструкции B.

Анализ графа использования переменной заключается в нахождении таких инструкций stloc(starg), за которыми не следует ни одной инструкции ldloc(ldarg). Эти инструкции являются избыточными и заменяются инструкциями pop.

На рисунке 5.3 изображен пример графа использования переменной. Серым цветом обозначены избыточные инструкции stloc.

Удаление псевдонимов переменных

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

Переменная Y является псевдонимом переменной X тогда и только тогда, когда:

Схема удаления псевдонима Y переменной X показана на рис. 5.4. При удалении осуществляются два действия:

Воспроизведение констант

Это преобразование позволяет избавиться от переменных, имеющих константное значение.

Переменная Y имеет константное значение C тогда и только тогда, когда:

Схема воспроизведения константы C, являющейся значением переменной Y, показана на рисунке 5.5. При воспроизведении осуществляются два действия:

Удаление неиспользуемых переменных

Если некоторая переменная не используется в графе метода или встречается только в инструкциях stloc(starg), то она удаляется. При этом все инструкции stloc(starg), использующие эту переменную, заменяются инструкциями pop.